* алгоритм поиска в задаче головоломки

Question

Я пытаюсь реализовать решатель 4 * 4 с использованием алгоритма поиска A *.Я понимаю, что totalDistance f (n) = g (n) + h (n), где g (n) - это стоимость пути от корня до текущего узла.Тем не менее, я не совсем понимаю, как рассчитать глубину для каждого уровня при настройке общей стоимости для каждого узла.Надеюсь, кто-нибудь сможет объяснить.

Answer 1

Алгоритм A * на самом деле не имеет понятия «глубина».Вместо этого, идея состоит в том, чтобы вести учет стоимости прохождения от начала до всех посещенных узлов.При посещении нового узла стоимость перехода к новому узлу равна стоимости текущего узла + стоимость перехода от текущего к новому узлу.

Эвристика общей стоимости используется только для одной цели: выбор следующегоузел для рассмотрения.Как вы говорите, как правило, это стоимость для узла + расчетная стоимость для пункта назначения.

Что касается изменений в вашем коде, я предлагаю вам либо сохранить «оценку» в качестве стоимости для узла (игнорируя оценку) и вычислите эвристику в своем сортировочном компараторе или сохраните как стоимость, так и оценку отдельно (если вычисление оценки дорого по любой причине).