Алгоритм для преобразования одного слова в другое слово путем изменения каждой буквы за итерацию, которая должна образовывать другое значащее слово?

Question

Я хочу сделать алгоритм для замены одного слова на другое.Например, данное слово - «грязь», и мне нужно преобразовать его в «КРОВАТЬ».Для каждой итерации я могу изменить один символ, но это должно сформировать другое значащее слово.Например, «MUD» можно изменить на «MAD».Таким образом, мне нужно найти кратчайший путь для преобразования «грязи» в «КРОВАТЬ».

Для поиска правильного слова предусмотрен отдельный метод.IsWord () - это метод, который даст нам логический результат независимо от того, является ли данная строка допустимой или нет.Поэтому не нужно беспокоиться об этом.

Мне также не нужно беспокоиться об эффективности или строках кода и т. Д. У кого-нибудь есть идеи, как создать этот алгоритм.Если это так, пожалуйста, помогите мне.

Заранее спасибо.

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

Answer 1

Это называется слово лестница .Прочтите сообщение Самая длинная головоломка с лестницей в истории в блоге Wolfram.

Answer 2

Вы начинаете с сортированной очереди с элементами (строками).Каждый элемент имеет рейтинг / расстояние (согласно эвристике) до целевого слова.Это может быть Расстояние Хэмминга .И отсортированная очередь использует это расстояние, чтобы выдвинуть слово, ближайшее к цели.

Вы берете свое первое слово, добавляете его в очередь.Извлеките из очереди первый элемент, раскройте все его дочерние элементы (слова, которые можно получить из него путем одного преобразования) и поместите их в очередь.Делайте это, пока элемент, который вы получаете из очереди, не является тем, который вы ищете, или очередь не станет пустой.

Answer 3

Создайте график следующим образом:

Каждое слово является узлом, и два узла связаны, если вы можете перейти от одного слова к другому за один шаг.

Теперь найдите кратчайшее расстояние и путь между исходным словом и последним словом.

См. http://en.wikipedia.org/wiki/Shortest_path_problem о том, как рассчитать кратчайший путь.

Answer 4

В каждой итерации создавайте все возможные новые слова из имеющихся у вас слов и собирайте их в список, набор или как угодно.Отфильтруйте дубликаты и слова, которые у вас уже были.Например:

1. (BED)
2. (BAD, BET, ....)
3. (MAD, BAN, ...., BUT, BOT, ....)

Вы либо получите пустой список, либо проблема не будет решена, либо искомое слово будет в списке.