BFS에서 가장 긴 경로 찾기

Question

나는 794 개의 3 글자 긴 단어가있는 목록이 있습니다. 내 임무는 주어진 단어에 대한 가장 긴 경로를 가진 단어를 찾는 것이다.

정의 (어린이) : 부모 단어
아이들은 부모 한 단어 교체 하나의 편지입니다.

예 :
'수'(그 단어가 목록에 있는지 주어진) 단어 '실행'에 자녀 등등 '실행', '랩'.

정의 (경로)
경로는 각각의 워드는 이전에 단일 문자를 교환함으로써 생성되는 일련의 단어이다.

#Pseudo code 
Given a word 
    Put the word in a queue 
    Keep a list with all visited words 
    As long as the queue is not empty 
     Get the first word in the queue 
     Generate a list with all the children to this word 
     For every children in that list 
      If the child is not in the list of visited words 
       Append the child to the list of visited words 
       Put the child in the queue 
    Print the path to the last grandchild. 

내 생각은 우리가 (이미 방문한되지 않은 즉, 어린이) 가능한 어린이의 부족까지 새로운 아이를 계속 생성하기 때문에이 가장 긴 경로를 제공하는 것입니다.

질문 :
내 아이디어가 유효합니까? 실제로 작동하는지 어떻게 테스트 할 수 있습니까?

---

실제 코드

아래 볼 수 있지만 코멘트를하지 않고 이해가되지 않을 수도 있습니다.

편집
나무와 목록이 약간 느릴 수 있으므로 세트로 교체했습니다.

from Queue import Queuenode; import Bintree 
with open('word3',encoding='utf-8') as f: 
    lista=f.readlines() 
    lista=[x.strip('\n') for x in lista] 
alfabet='abcdefghijklmnopqrstuvwxyzåäö' 
class Word: 
    def __init__(self, w, f = None): 
     self.word = w 
     self.parent = f 
children=Bintree.Bintree() 
for i in lista: 
    children.put(i) 
def barn(far): 
    barnlista=[] 
    for i in range(3): 
     for j in range(29): 
      empty='' 
      empty+=far[0:i]+alfabet[j]+far[i+1:] 
      if empty!=far and children._exists(empty): 
       barnlista+=[empty] 
    return barnlista 
ko=Queuenode() 
def vag(item): 
    start=item 
    counter=0 
    while start!=None: 
     counter+=1 
     print(start.word) 
     start=start.parent 
    print(counter) 
def bfsx(startord): 
    ko.put(Word(startord)) 
    besokta=[startord] 
    while not ko.isempty(): 
     first=ko.get() 
     lista=barn(first.word) 
     for child in lista: 
      if child not in besokta: 
       besokta+=[child] 
       ko.put(Word(child,first)) 
    vag(first) 

Answer 1

IIUC,이은 (그렇지 않은 경우 사실, 당신이 사례를 구축 할 수 있습니다) 작동하지 않을 수 있습니다.

노드 에서 시작하여; 직접 경로가있다 → b; 직접 경로 → c 및 간접 경로 c ⇒b도 있습니다.

당신이의 자식들에 대해 반복 할 때, 당신은 C 전에 B가 발생한다고 가정하자. b을 방문하여 방문한 것으로 표시합니다. 나중에 어느 시점에 c이 발생하고 결국 b을 다시 생각해보십시오. 알고리즘은 더 이상 하나의 → C ⇒ B보다는 짧은 서브 패스 → B을 고려할 것입니다 그래서 그 시점에서, 그러나, B는 이미 방문 간주됩니다.

그래프 뒤에있는 이야기는 DAG가 아니므로 "방문한"표시도 제거 할 수 없습니다. "방문한"논리를 제거하면 무한 루프가 발생합니다.