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

Question

Я уверен, что вы все слышали об «игре в слова», где вы пытаетесь изменить одно слово на другое, меняя одну букву за раз и пропуская только действительные английские слова. Я пытаюсь реализовать алгоритм A * для его решения (просто для того, чтобы конкретизировать мое понимание A *), и одна из вещей, которая необходима, - это эвристика минимального расстояния.

То есть минимальное количество одной из этих трех мутаций, которые могут превратить произвольную строку a в другую строку b: 1) Поменять одну букву на другую 2) Добавить одну букву в месте до или после любой буквы 3) Удалить любую букву

Примеры

aabca => abaca:
aabca
abca
abaca
= 2

abcdebf => bgabf:
abcdebf
bcdebf
bcdbf
bgdbf
bgabf
= 4

Я перепробовал много алгоритмов; Я не могу найти тот, который дает фактический ответ каждый раз. На самом деле, иногда я не уверен, что даже мои человеческие рассуждения находят лучший ответ.

Кто-нибудь знает какой-либо алгоритм для такой цели? Или, может быть, может помочь мне найти один?

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

Answer 1

Вы хотите минимальное расстояние редактирования (или расстояние Левенштейна) :

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

И один алгоритм для определения последовательности редактирования находится на той же странице здесь .

Answer 2

Отличным справочником по «Редактированию расстояния» является раздел 6.3 учебника «Алгоритмы» С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани, черновик которого можно свободно получить здесь .

Answer 3

Если у вас небольшой (небольшой) словарь, поиск по дереву в ширину может сработать.

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

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