Кратчайший путь от одного слова к другому через правильные слова (без графика)

Question

Я сталкивался с этой проблемой редактирования расстояния:

Найдите кратчайший путь от одного слова к другому, например, шторм-> сила, проверяя каждое промежуточное слово с помощью функции isValidWord(). Нет другого доступа к словарю слов, и поэтому граф не может быть построен.

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

Кто-нибудь еще находит это интересным? Ждем помощи, спасибо!

Answer 1

Это головоломка от Льюиса Кэрролла, известная как Слово Лестницы . Дональд Кнут рассказывает об этом в Stanford Graphbase . Это также

Вы можете просмотреть это как поиск в ширину. Вам понадобится доступ к словарю слов, иначе пространство, которое вам придется искать, будет огромным. Если у вас есть только доступ к действительному слову, вы можете сгенерировать все варианты слов, а затем просто использовать isValidWord (), чтобы отфильтровать его (Norvig " Как написать корректор орфографии " - отличное объяснение генерации правки).

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

Мне это тоже показалось интересным, так что здесь есть реализация на Haskell здесь , которая работает достаточно хорошо. В комментариях есть ссылка на Clojure версию , в которой есть несколько действительно приятных визуализаций.

Answer 2

Вы можете искать с двух сторон одновременно. То есть измените букву в шторме и запустите ее через isValidWord (), измените букву в силе и запустите через isValidWord () Если эти два слова совпадают, вы нашли путь.