Кратчайший путь в Три
Для проекта Data Structures я должен найти кратчайший путь между двумя словами, такими как «кошка» и «собака», но мне разрешено менять только одну букву за раз. Я пытаюсь сделать это путем реализации дерева и могу кажется, не в состоянии осуществить поиск кратчайшего пути.
кот -> детская кроватка -> винтик -> собака
Все слова будут одинаковой длины, и я заполняю их из файла словаря.
Мы должны переходить от слова к слову. Таким образом, слово между ними должно быть допустимым словом.
Я думаю, что на самом деле невозможно использовать три, но у кого-нибудь есть знания?
Решение
Вы хотите использовать VP-Tree и алгоритм называется Расстояние Левенштейна
Реализация C может быть найдена здесь, код слишком длинный, чтобы публиковать в качестве ответа:
C VP-Tree
Другие решения
Лучшей структурой данных для такого рода проблем является график.
Это называется Word Ladder, и вы можете посмотреть здесь: http://en.wikipedia.org/wiki/Word_ladder.
То, что вы ищете, это простая 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]
}