Кратчайший путь в попытке

Для проекта Data Structures я должен найти кратчайший путь между двумя словами, такими как «кошка» и «собака», но мне разрешено менять только одну букву за раз. Я пытаюсь сделать это, реализуя три и могу похоже, не может реализовать поиск кратчайшего пути.

кошка -> детская кроватка -> шестеренка -> собака

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

Я думаю, что на самом деле невозможно использовать три, но кто-нибудь знает?


c++ algorithm data-structures shortest-path trie
person David Chavez    schedule 08.03.2013    source источник
comment
Обратите внимание, что кратчайшее прошедшее время в виде дерева, которое вы обычно составляете из словаря, не является хорошей метрикой сходства! Например, груша и медведь очень похожи, но потребуют пройти весь путь до корня и снова спуститься в стандартном дереве.   -  person us2012    schedule 08.03.2013

Ответы (3)


arrow_upward
5
arrow_downward

Вы хотите использовать VP-Tree, и алгоритм называется Расстояние Левенштейна Реализацию AC можно найти здесь, код слишком длинный, чтобы публиковать его в качестве ответа:
C VP-Tree

person Woot4Moo    schedule 08.03.2013

arrow_upward
1
arrow_downward

Лучшей структурой данных для такого рода задач является граф. Это называется лестницей слов, и вы можете найти ее здесь: http://en.wikipedia.org/wiki/Word_ladder. .

person Ola M    schedule 08.03.2013

arrow_upward
-2
arrow_downward

То, что вы ищете, это простой BFS. Каждое слово является вершиной графа, но граф даже строить не нужно, его можно решить с помощью массива слов:

words = {"cat", "dog", "dot", "cot"}
mark = {0, 0, 0, 0}
distance = {0, 0, 0, 0}
queue Q
start_word_index = 0; // words[0] -> "cat"
destination_word_index = 1; // words[1] -> "dog"
Q.push(start_word_index)
while(Q is not empty) {
    word_index = Q.pop()
    for each `words[j]` {
        if (difference between `words[word_index]` and `words[j]` is only 1 character) AND
           (`mark[j]` is not 1) {
            mark[j] = 1
            Q.push(j)
            distance[j] = distance[word_index] + 1
        }
    }
}

if mark[destination_word_index] is 0 {
    print "Not reachable"
} else {
    print "Distance is ", distance[destination_word_index]
}
person artahian    schedule 08.03.2013