Как эвристический эффект повлияет на алгоритм Дикстры, чтобы сделать его алгоритмом A *

Question

Я занимаюсь разработкой алгоритма A *, который должен решить проблему миссионеров и каннибалов.Что я не понимаю, так это то, что делает эвристика, чтобы сделать поиск меньшим количеством узлов, чем алгоритм Дикштраса.

Я понимаю, что программа будет искать сначала на основе лучших, используя эвристическое значение + текущее значение, чтобы определить возможныезначение, но как алгоритм узнает, когда следует прекратить поиск и не переходить в другие узлы?

Answer 1

Эвристика должна гарантировать, что она никогда не будет слишком высокой (при условии, что вы ищете самое маленькое решение).Поэтому, как только вы нашли полное решение, вы знаете, что оно должно быть лучшим.Любое неполное решение (которое уже имеет более высокое значение, чем текущее, в противном случае вы бы изучили его дальше), может быть даже еще выше после его завершения.