Возможная эвристическая функция для Word Ladder

Question

Эй, я думаю об использовании A * для поиска и оптимального решения проблемы Word Ladder, но я немного затруднен думать о подходящих g (x) и h (x) , Для этой конкретной задачи может ли g (x) быть число переходов из начальной вершины, а h (x) - количество разных символов из целевого слова? Я советую оказать большую помощь.

Answer 1

Я никогда не был поклонником обозначений A * f(x) = g(x) + h(x), потому что это упрощает алгоритм. A * основан на двух эвристиках; часто обозначается g(x) + h(x).

У вас уже есть большинство из них; для Djikstra's/g(x), вы хотите вернуть количество перелетов. Для Greedy/h(x) вы хотите проверить, сколько символов ошибочно; вы попадаете в цель, когда h(x) = 0.

Объединив эти два значения, у вас есть эвристика A *, которая, по сути, говорит о расширении лучших узлов вдоль кратчайшего пути. В других проектах вы можете добавить эвристику к A *, чтобы получить поведение, подобное избеганию врагов (поэтому я предпочитаю не думать A* = g+h).

EDIT: Не забудьте проверить каждого кандидата, используя файл словаря; словарная лестница требует, чтобы промежуточные слова были реальными словами.