Самый короткий путь для преобразования одного слова в другое

Question

Для проекта Data Structures я должен найти кратчайший путь между двумя словами (например, и "dog"), меняя только одну букву за раз. Нам предоставляется список слов Scrabble для поиска нашего пути. Например:

cat -> bat -> bet -> bot -> bog -> dog 

Я решил проблему, используя ширину первого поиска, но я в поисках чего-то лучшего (я представлял словарь с синтаксического дерева).

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

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

Мы должны перейти от слова к слову. Мы не можем пойти cat -> dat -> dag -> dog. Мы также должны распечатать обход.

Answer 1

НОВЫЙ ОТВЕТ

Учитывая недавнее обновление, вы можете попробовать A * с расстояния Хемминга в качестве эвристики. Это допустимо эвристический, поскольку он не собирается переоценивайте расстояние

OLD ОТВЕТ

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

EDIT: Если существует постоянное число строк, проблема разрешима в полиномиальное время. Else, это NP-hard (все это в Википедии). Предполагая, что ваш друг говорит о проблеме NP-hard.

EDIT: Если ваши строки имеют одинаковую длину, вы можете использовать Hamming distance.

Answer 2

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

Answer 3

Это типичная проблема dynamic programming. Проверьте проблему «Изменить расстояние».

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Проблема:

Вам дают быстрый (линейный) способ проверить, если слово в словаре, два слова U, V и должны проверить, есть ли последовательность и -> а -> а -> ... -> а _п. -> v

является NP-трудной.

Доказательство: Возьмем некоторый экземпляр 3SAT, как

(р или д или нет г) и (р или не д или г)

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

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

Разрешенные слова:

• Все, что начинается с 0 и содержит только 0 и 1 в
• Все, что начинается с 2 и является законным. Это означает, что он состоит из 0 и 1 (за исключением того, что первый символ равен 2, все клаузные разряды по праву устанавливаются в соответствии с битами переменных, и они установлены в 1 (так что это показывает, что формула удовлетворительна).
• Все, что начинается с, по меньшей мере, двух 2-х, а затем, состоит из (регулярного выражения 0 и 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-твердости.

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

Answer 7

То, что вы ищете, называется Edit Distance. Существует много разных типов.

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

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

Answer 8

Вы можете сделать это немного быстрее, удалив слова во-первых, это не правильная длина. Более ограниченный словарь будет вписываться в кеш процессора. Наверное, все.

Кроме того, все сравнения strncmp (при условии, что вы сделали все в нижнем регистре) могут быть сравнениями memcmp или даже развернутыми сравнениями, которые могут быть ускорением.

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