Что лучший алгоритм должен найти копией / лестничная структура слова?

Согласно вашей странице Wikipedia, есть эти правила:

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

Это может помочь сломать его в эти 4 подпруты.

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

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

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

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

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

Также вы просто хотите найти решение или лучшее решение?

Редактировать

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

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

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

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

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

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

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

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

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

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

http://en.wikipedia.org/wiki/a * _Search_algorithm

Стороны:

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

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

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

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