Проблема алгоритма: преобразование слова из данного слова в другое с использованием только слов в данном слове

Question

Подробное описание проблемы выглядит следующим образом:

Учитывая два слова (beginWord и endWord) и список слов в словаре, найдите, есть ли последовательность преобразования из beginWord в endWord, такая что:

1. За один раз можно изменить только одну букву
2. Каждое преобразованное слово должно существовать в списке слов.Обратите внимание, что beginWord не является преобразованным словом.

Я знаю, что это слово можно найти с помощью поиска в ширину.После того, как я предложил нормальное решение BFS, интервьюер спросил меня, могу ли я сделать это быстрее.Я не нашел способ ускорить.И интервьюер сказал мне, что я должен вместо этого использовать PriorityQueue, чтобы выполнить «поиск в первую очередь».И приоритет отдается расстоянию Хэмминга между текущим словом и целью.

Я не совсем понимаю, почему это может ускорить поиск.Я чувствую, что с помощью priorityQueue мы пытаемся найти путь, по которому идет прогресс (т. Е. Сократить расстояние Хэмминга).

Кажется, это жадный метод.Мои вопросы:

Почему это решение быстрее, чем решение поиска в ширину?Я чувствую, что реальный путь может быть таким: сначала не делать никакого прогресса или даже увеличивать расстояние Хемминга, но после достижения слова расстояние Хемминга постепенно уменьшается.В этом сценарии, я думаю, решение приоритетной очереди будет медленнее.

Любые предложения будут оценены!Спасибо

Answer 1

Во-первых, я бы порекомендовал немного прочитать алгоритмы поиска в графе, которые объяснят вопрос до любой детали, которую вы хотите (и далеко за ее пределами).

TL; DR:

Ваш интервьюер порекомендовал что-то близкое к алгоритму A *.

Это отличается от BFS в одном аспекте: какой узел расширять первым.В нем используется понятие оценки расстояния, состоящее из двух элементов:

• В узле X мы уже «преодолели» расстояние, заданное числом преобразований.
• Дочтобы достичь цели из X, нам все еще нужно пройти еще, по крайней мере, N шагов, где N - количество символов, различающихся между узлом и целью.

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

A * говорит нам: обо всех открытых (нерасширенных) узлах,Попробуйте сначала тот, который потенциально дает кратчайший путь решения, то есть тот, который имеет наименьший балл.И чтобы реализовать это, приоритетная очередь подходит.

Во многих случаях A * может значительно сократить пространство поиска (по сравнению с BFS), и все же гарантирует найти лучшее решение.

A * НЕ жадный алгоритм.В конечном итоге он будет исследовать все пространство поиска, только в гораздо лучшем порядке, чем слепая BFS.