Как вычислить «кратчайшее расстояние» между двумя словами?

Question

Недавно у меня было интервью, и меня попросили написать алгоритм, чтобы найти минимальное количество изменений в 1 письмо, чтобы получить от определенного слова к данному слову, т. Е. Cat-> Cot-> Cog-> Dog

Я не хочу, чтобы решение проблемы просто подсказывало мне, как я могу использовать BFS в этом алгоритме?

Answer 1

согласно этому царапают списке, самый короткий путь между кошкой и собакой: [ 'CAT', 'СОТ', 'НГК', 'DOG']

from urllib import urlopen 

def get_words(): 
    try: 
     html = open('three_letter_words.txt').read() 
    except IOError: 
     html = urlopen('http://www.yak.net/kablooey/scrabble/3letterwords.html').read() 
     with open('three_letter_words.txt', 'w') as f: 
      f.write(html) 

    b = html.find('<PRE>') #ignore the html before the <pre> 
    while True: 
     a = html.find("<B>", b) + 3 
     b = html.find("</B>", a) 
     word = html[a: b] 
     if word == "ZZZ": 
      break 
     assert(len(word) == 3) 
     yield word 

words = list(get_words()) 

def get_template(word): 
    c1, c2, c3 = word[0], word[1], word[2] 
    t1 = 1, c1, c2 
    t2 = 2, c1, c3 
    t3 = 3, c2, c3 
    return t1, t2, t3 

d = {} 
for word in words: 
    template = get_template(word) 
    for ti in template: 
     d[ti] = d.get(ti, []) + [word] #add the word to the set of words with that template 

for ti in get_template('COG'): 
    print d[ti] 
#['COB', 'COD', 'COG', 'COL', 'CON', 'COO', 'COO', 'COP', 'COR', 'COS', 'COT', 'COW', 'COX', 'COY', 'COZ'] 
#['CIG', 'COG'] 
# ['BOG', 'COG', 'DOG', 'FOG', 'HOG', 'JOG', 'LOG', 'MOG', 'NOG', 'TOG', 'WOG'] 

import networkx 
G = networkx.Graph() 

for word_list in d.values(): 
    for word1 in word_list: 
     for word2 in word_list: 
      if word1 != word2: 
       G.add_edge(word1, word2) 

print G['COG'] 
#{'COP': {}, 'COS': {}, 'COR': {}, 'CIG': {}, 'COT': {}, 'COW': {}, 'COY': {}, 'COX': {}, 'COZ': {}, 'DOG': {}, 'CON': {}, 'COB': {}, 'COD': {}, 'COL': {}, 'COO': {}, 'LOG': {}, 'TOG': {}, 'JOG': {}, 'BOG': {}, 'HOG': {}, 'FOG': {}, 'WOG': {}, 'NOG': {}, 'MOG': {}} 

print networkx.shortest_path(G, 'CAT', 'DOG') 
['CAT', 'OCA', 'DOC', 'DOG'] 

в качестве бонуса мы можем получить дальние:

print max(networkx.all_pairs_shortest_path(G, 'CAT')['CAT'].values(), key=len) 
#['CAT', 'CAP', 'YAP', 'YUP', 'YUK'] 

Answer 2

На первый взгляд, я промахнулся около Levenshtein distance, но вам нужно использовать BFS. Поэтому я думаю, что вы должны начать с создания дерева. Данное слово должно быть root, а затем следующие узлы - это слова с измененной первой буквой. Следующие последующие узлы изменили вторую букву. Когда вы строите граф, вы используете BFS, и когда вы нашли новое слово, сохраните длину пути. В конце алгоритма выберите минимальное расстояние.

Answer 3

1. Начните с только стартового слова в вашем наборе путей.

2. Если конечное слово любого пути в вашем наборе путей является искомым словом, остановитесь, этот путь является желаемым путем.

3. Замените каждый путь в своем пути множеством с любым возможным путем, начинающимся с этого пути, но на одно слово дольше.

4. Перейти к шагу 2.

Answer 4

Если мы начнем строить ориентированный ациклический граф сюда m слова назначения в исходное слово, по ширине, и мы выполняем поиск в словаре, чтобы проверить, видели ли мы ранее слово в дереве при добавлении слова, затем первое вхождение исходного слова, должен дать кратчайший путь в обратном направлении от «целевого слова» до «исходного слова».

Из этого мы можем напечатать путь от «источника» к «целям»