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

Ответ 1

НОВЫЙ ОТВЕТ

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

OLD ANSWER

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

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

EDIT: если ваши строки имеют одинаковую длину, вы можете использовать расстояние Хэмминга.

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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