Кратчайший путь для преобразования одного слова в другого

Для словарей оптимальна BFS, но необходимое время работы пропорционально его размеру (V + E). С n буквами словарь может содержать ~ a ^ n, где a - размер алфавита. Если словарь содержит все слова, кроме того, которое должно быть в конце цепочки, вы пройдете по всем возможным словам, но ничего не найдете. Это обход графа, но его размер может быть экспоненциально большим.

Вы можете задаться вопросом, можно ли сделать это быстрее - просматривать структуру «разумно» и делать это за полиномиальное время. Ответ, я думаю, нет.

Проблема:

Вам предоставляется быстрый (линейный) способ проверить, есть ли слово в словаре, два слова u, v и проверить, есть ли последовательность u -> a ₁ -> a ₂ -> ... -> a _n -> v.

является NP-сложной задачей.

Доказательство: возьмите какой-нибудь экземпляр 3SAT, например

(p или q или не r) и (p или не q или r)

Вы начнете с 0 000 00 и должны проверить, возможно ли перейти к 2 222 22.

Первым символом будет «мы закончили», три следующих бита будут управлять p, q, r, а два следующих будут управлять предложениями.

Разрешено следующие слова:

• Все, что начинается с 0 и содержит только 0 и 1
• Все, что начинается с 2 и является допустимым. Это означает, что он состоит из нулей и единиц (за исключением того, что первый символ - 2, все биты предложений правильно установлены в соответствии с битами переменных, и они установлены в 1 (так что это показывает, что формула удовлетворительна).
• Все, что начинается как минимум с двух двоек, а затем состоит из нулей и единиц (регулярное выражение: 222 * (0 + 1) *, как 22221101, но не 2212001

Чтобы получить 2 222 22 из 0 000 00, вы должны сделать это следующим образом:

(1) Переверните соответствующие биты - например, 0 100 111 в четыре этапа. Для этого требуется найти решение 3SAT.

(2) Измените первый бит на 2: 2 100 111. Здесь вы убедитесь, что это действительно решение 3SAT.

(3) Замените 2 100 111 -> 2 200 111 -> 2 220 111 -> 2 222 111 -> 2 222 211 -> 2 222 221 -> 2 222 222.

Эти правила предписывают, что вы не можете обмануть (проверить). Переход к 2 222 22 возможен только в том случае, если формула удовлетворительна, и проверка этого NP-трудна. Я думаю, что это может быть еще сложнее (возможно, #P или FNP), но я думаю, что для этой цели достаточно NP-жесткости.

Изменить : Вас может заинтересовать несвязанная структура данных . Это займет ваш словарь и сгруппирует слова, до которых можно добраться друг от друга. Вы также можете сохранить путь от каждой вершины до корня или какой-либо другой вершины. Это укажет вам путь, не обязательно самый короткий.

Это типичная проблема динамического программирования . Проверьте наличие проблемы с редактированием расстояния.

Там являются методами разной эффективности для поиска ссылок - вы можете построить полный график для каждой длины слова или, например, вы можете построить BK-дерево , но ваш друг прав - BFS - наиболее эффективный алгоритм.

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

То, что вы ищете, называется расстоянием редактирования. Есть много разных типов.

Из ( http://en.wikipedia.org/wiki/Edit_distance ): «В теории информации и информатике расстояние редактирования между двумя строками символов равно количество операций, необходимых для преобразования одного из них в другой ».

В этой статье о Jazzy (API проверки орфографии Java) есть хороший обзор такого рода сравнений (аналогичная проблема - предоставление предлагаемых исправлений) http://www.ibm.com/developerworks/java/library/j-jazzy/

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

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