Каков наилучший алгоритм, чтобы найти двойную / словесную лестницу?

Question

Есть ли эффективный алгоритм для поиска дуплет / слово лестница?Это можно сделать грубой силой, но должен быть лучший способ сделать это.Как?

http://en.wikipedia.org/wiki/Word_Ladder

Answer 1

Если вы считаете это проблемой поиска пути, вы можете попробовать алгоритм A *.

(Эвристический поиск пространства ответов.)

Кроме того, вы просто хотите найти решение или лучшее решение?

EDIT

Мне не хочется менять это, но я вижу, что мой пример плохой, поскольку один шаг решает его. Игнорируйте эту проблему при рассмотрении примера.

Быстрый обзор того, как работает A * (и немного относится к этой проблеме)

Чтобы использовать A *, вам нужна функция, которая оценивает данное состояние (завершения). Вы хотите более высокое значение для состояний, которые ближе к цели.

Для этой задачи две примерные функции

• (каждая буква правильная * 1) - (количество букв отличается от цели * 10)
• (каждая правильная буква * 100) - (количество букв, отличных от цели)

Как вы можете видеть, первый размер слова одобрения близок к правильным буквам 2-ые правильные буквы правильные.

Не уверен, что лучше - ты мог бы сделать сбалансированную формулу тоже.

Допустим, мы пытаемся получить от бота -> лодка

Затем вы оцените все возможные изменения мальчика, давайте воспользуемся первой функцией. два примера, которые вы бы оценили, это boot и bat (и другие). boot имеет значение 3, а bat имеет значение -7. Загрузка лучше (в соответствии с этой функцией), поэтому мы бы оценили все возможные изменения загрузки (прежде чем другие) и нашли решение.

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

http://en.wikipedia.org/wiki/A*_search_algorithm

Примечания стороны:

• A * найдет наилучшее решение, если функция спроектирована правильно, если такая функция существует для данной задачи. Это аккуратная особенность A *.

• Улучшение A * - это короткое замыкание при взгляде на состояния (например, в приведенном выше случае - положительное значение 3 - очень хорошее значение (4 - максимальное значение), поэтому ваш алгоритм может перестать смотреть на другие состояния и перейти к тому, который очень близко.

• Две трудные части A *: 1) поиск правильной функции и 2) возможность перечисления всех возможных состояний. Я думаю, что 2 не так сложно сделать с хорошим файлом словаря и некоторыми функциями быстрого хеширования / поиска.

Answer 2

Согласно вашей странице в Википедии, существуют следующие правила:

1. Добавить письмо
2. Удалить письмо
3. Изменить букву
4. Используйте одни и те же буквы в другом порядке (анаграмма)

Это может помочь разбить его на эти 4 подзадачи.

Для анаграмм существует очень простой алгоритм. Создайте хеш-таблицу, в которой каждое каждое слово хранится в длинной строке с буквами, отсортированными по алфавиту. Так, например, если у вас есть слово races, оно превратится в acers, а затем совпадет с анаграммой для cares, что также acers. Они, как правило, работают довольно быстро.

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

Если вы придерживаетесь одного и того же патча, смена буквы кажется наиболее трудной просто потому, что от нее так много ветвей.

Answer 3

В чистой версии игры вы можете выполнить только 1 операцию: заменить букву другой.

Это делает построение графика для поиска довольно простым, но медленным, учитывая слово общей длины, например 4 или 5 ...

Начните с корневого слова и проверьте наличие соседних слов, определив, отличаются ли слова только на 1 букву, где положение букв является значимым.

Я думаю, что Поиск в ширину , где вы строите дерево поиска по ходу, было бы хорошим началом. Проблема в том, что вы получаете слова, которые никогда не могут соединиться, но проведут вас через большую часть графика, прежде чем вы сможете быть уверены, что они не могут соединиться. Поиск в ширину гарантированно даст вам кратчайший путь от корневого слова до целевого слова. Обратите внимание, что самый короткий путь не обязательно самый быстрый для поиска.

Answer 4

Расстояние Левенштейна кажется хорошим местом для начала. Шаги, разрешенные при расчете расстояния Левенштейна, очень близки к тем, которые допускаются в словарных лестницах, за исключением анаграммирования. Вы могли бы, вероятно, придумать хорошую эвристику для использования с A * на основе L.D.