정의되지 않은 오류가 계속 발생하는 이유는 무엇입니까?

Question

이것은 루마니아 도시를 탐색하는 파이썬의 검색 알고리즘입니다.

class GraphTree: 

    graph = { 
    'Oradea': set(['Zerind','Sibiu']), 
    'Zerind': set(['Arad','Oradea']), 
    'Sibiu': set(['Arad','Rimnicu Vilcea','Fagaras','Oradea']), 
    'Arad': set(['Timisoara','Zerind','Sibiu']), 
    'Timisoara': set(['Lugoj']), 
    'Lugoj': set(['Mehadia']), 
    'Mehadia': set(['Drobeta']), 
    'Drobeta': set(['Craiova']), 
    'Rimnicu Vilcea': set(['Craiova','Pitesti','Sibiu']), 
    'Craiova': set(['Drobeta','Rimnicu Vilcea']), 
    'Fagaras': set(['Bucharest','Sibiu']), 
    'Pitesti': set(['Bucharest','Rimnicu Vilcea']), 
    'Bucharest': set(['Giurgiu','Urziceni','Pitesti','Fagaras']), 
    'Giurgiu': set(['Bucharest']), 
    'Urziceni': set(['Hirsova','Vaslui','Bucharest']), 
    'Hirsova': set(['Eforia','Urziceni']), 
    'Eforia': set(['Hirsova']), 
    'Vaslui': set(['Iasi','Urziceni']), 
    'Iasi': set(['Neamt','Vaslui']), 
    'Neamt': set(['Iasi'])} 

def bfs(graph, start, end): 
    queue = [(start, [start])] 
    while queue: 
     (vertex, path) = queue.pop(0) 
     for next in graph[vertex] - set(path): 
      if next == end: 
       yield path + [next] 
      else: 
       queue.append((next, path + [next]))   

def dfs(graph, start, goal): 
    queue = [] 
    queue.append([start]) 
    while queue: 
     path = queue.pop(0) 
     node = path[-1] 
     if node == end: 
      return path 
     for adjacent in graph.get(node,[]): 
      new_path = list(path) 
      new_path.append(adjacent) 
      queue.append(new_path) 

print('bfs') 
bfs(graph, 'Oradea', 'Neamt') 
print('dfs') 
dfs(graph, 'Oradea', 'Neamt') 

내가 알고리즘을 실행할 때이 오류가 점점 계속 :

---> 1 class GraphTree: 
     2 
     3  graph = { 
     4   'Oradea': set(['Zerind','Sibiu']), 
     5   'Zerind': set(['Arad','Oradea']), 

에서 또 다른 하나 49 BFS (그래프, '오라', '암츠') (50) 인쇄 ('DFS') -> 51 DFS (그래프 '오라', '암츠')

그리고 마지막 :

39    path = queue.pop(0) 
40    node = path[-1] 

,745,151 5,

-> 41의 경우 노드 == 단부 : graph.get 인접위한 42 복로 43 (노드 [])

NameError: name 'end' is not defined

알고리즘이 확인을 조건으로 선언 정확한 논리적으로 보인다. 이 검색 알고리즘이 작동하지 않는 이유는 무엇입니까?

The algorithm should be able to navigate the map going from one city to the other and returning the path using both breadth first (bfs) and depth first (dfs) searches.

Answer 1

당신은 당신의 코드에

bfs(graph, start, end) 

및

dfs(graph, start, goal) 
        ^^^^ 

다른 어떤 메모를했다 : 당신은 당신의 검색 결과를 인쇄하지 않을

• 하지만, 네가 그 일을하려는 것처럼 보였다.
• 클래스로 모두 래핑했지만 코드에서 실제로 필요한 모든 작업을 수행하지 않았습니다. 나는이 프로그램을 실행할 때

  graph = {                                                   
      'Oradea': set(['Zerind','Sibiu']),                                            
      'Zerind': set(['Arad','Oradea']),                                            
      'Sibiu': set(['Arad','Rimnicu Vilcea','Fagaras','Oradea']),                                      
      'Arad': set(['Timisoara','Zerind','Sibiu']),                                         
      'Timisoara': set(['Lugoj']),                                             
      'Lugoj': set(['Mehadia']),                                              
      'Mehadia': set(['Drobeta']),                                             
      'Drobeta': set(['Craiova']),                                             
      'Rimnicu Vilcea': set(['Craiova','Pitesti','Sibiu']),                                       
      'Craiova': set(['Drobeta','Rimnicu Vilcea']),                                         
      'Fagaras': set(['Bucharest','Sibiu']),                                           
      'Pitesti': set(['Bucharest','Rimnicu Vilcea']),                                         
      'Bucharest': set(['Giurgiu','Urziceni','Pitesti','Fagaras']),                                     
      'Giurgiu': set(['Bucharest']),                                             
      'Urziceni': set(['Hirsova','Vaslui','Bucharest']),                                        
      'Hirsova': set(['Eforia','Urziceni']),                                           
      'Eforia': set(['Hirsova']),                                              
      'Vaslui': set(['Iasi','Urziceni']),                                            
      'Iasi': set(['Neamt','Vaslui']),                                            
      'Neamt': set(['Iasi'])}                                               
  
  def bfs(graph, start, end):                                               
      queue = [(start, [start])]                                              
      while queue:                                                 
       (vertex, path) = queue.pop(0)                                            
       for next in graph[vertex] - set(path):                                          
        if next == end:                                               
         yield path + [next]                                             
        else:                                                 
         queue.append((next, path + [next]))                                         
  
  def dfs(graph, start, end):                                               
      queue = []                                                  
      queue.append([start])                                               
      while queue:                                                 
       path = queue.pop(0)                                               
       node = path[-1]                                                
       if node == end:                                                
        return path                                                
       for adjacent in graph.get(node,[]):                                           
        new_path = list(path)                                             
        new_path.append(adjacent)                                            
        queue.append(new_path)                                             
  
  print('bfs')                                                  
  print(list(bfs(graph, 'Oradea', 'Neamt')))                                           
  print('dfs')                                                  
  print(dfs(graph, 'Oradea', 'Neamt'))  
  

  , 출력은 다음과 같습니다 : 마음에이 모든으로

, 여기에 또 다른 버전에서

bfs 
[['Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Sibiu', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt']] 
dfs 
['Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt']