파이썬에서 폭스 우선 검색 알고리즘을 만들었습니다. 솔루션을 반환하는 방법을 모르겠다

Question

나는 폭 우선으로 확장하고, 노드를 다시 방문하지 않으며, 목표 노드를 찾았는지 여부를 감지하는 경로 찾기 알고리즘을 작성해야한다. 그러나 내가 고민하는 주요한 점은 시작 노드에서 목표 노드까지의 실제 경로 인 솔루션을 찾는 것입니다. 기본적으로 모든 것이 완벽하게 작동하지만 시작 노드에서 목표 노드로 실제 경로를 반환하는 방법을 모르겠습니다.

그건 그렇고, 궁금한 점이 있으면, 이것은 과제가 아닙니다. 나는 스스로 길 찾기 알고리즘 (그리고 인공 지능)을 스스로 가르치고 있으며 너비 우선 탐색 알고리즘을 다시 만들려고 노력하고있다. 따라서 나는 의사 코드 (psuedocode)를 환영한다. (내가하고 싶은 것을 말해주기 때문에 코드를 많이 배우기 위해 직접 코드를 만들 수있다.)

솔루션 내 알고리즘으로 시작 노드에서 끝 노드로)? 내 전체 알고리즘을 다시 작성해야 또는 내 폭 우선 탐색 알고리즘 모두의

import collections 

def bfs(graph,start, end): 
    path = collections.deque() 
    trail = collections.deque() 
    solution = collections.deque() 


    path.append(start) 

    # A series of visited nodes 
    trail.append(start) 

    if start == end: 
     return path 
    while True: 
     for node in graph[start]: 
      print node 

      # Adds node to path if it is not visited already 
      if node not in trail: 
       path.append(node) 
       trail.append(node) 
       print path   

     #Removes parent node after all children added to path (by removing the left of the path) 
     path.popleft() 
     start = path.popleft() 
     path.appendleft(start) 
     print "****Node Scan Completed:****" 
     print path 

     # If goal node is reached 
     if start == end: 
      print "----------------------Final Results:----------------------" 
      print trail 
      print path 
      return solution 
    print "Final Results:" 
    print trail 
    print path 
    return None 


graph = { "a" : [], 
      "b" : ["a"], 
      "c" : ["a"], 
      "d" : ["b","c","e"], 
      "e" : ["h","r"], 
      "f" : ["c","g"], 
      "g" : [], 
      "h" : ["p","q"], 
      "p" : ["q"], 
      "q" : [], 
      "r" : ["f"], 
      "s" : ["d","e","p"] 
     } 

print bfs(graph,'s','g') 

Answer 1

처음부터 경로를 반환 코드의 조각이 있습니까, 스스로 일을 배울 수있는 시간을내어 당신에게 칭찬.

알고리즘은 하나의 중요한 부분을 잃어 버렸습니다. 이미 알았 듯이 시작 노드에서 끝 노드까지의 경로 정보는 저장하지 않습니다. 방문한 노드 (trail 변수)와 방문 할 노드 (path) 만 저장하고 있습니다. 해결책은 매우 간단합니다. map 개의 상위 노드를 추가하기 만하면 노드를 방문 할 때마다 어느 노드에서 왔는지 알 수 있습니다. 끝 노드에 도달하면 부모 노드의이 맵을 확인하여 시작 노드에 도착할 때까지 솔루션 경로를 빌드 할 수 있습니다.

path = collections.deque() 
trail = collections.deque() 
parents = {} # New line 

다음, 루프 내에서이지도를 채우기 위해 코드를 추가합니다 :

코드에서 바로 맨 위에 새로운 parents 맵을 추가

 # Adds node to path if it is not visited already 
     if node not in trail: 
      parents[node] = start # New line 
      path.append(node) 
      trail.append(node) 

을 마지막으로 코드를 추가 함수의 맨 아래에 솔루션을 만들고 반환하십시오.

# If goal node is reached 
    if start == end: 
     print "----------------------Final Results:----------------------" 
     print trail 
     print path 

     solution = [end] # New code from here down 
     n = end 
     while n in parents and parents[n]: 
      solution.append(parents[n]) 
      n = parents[n] 

     return solution[::-1] 

entire code here.