경로 찾기 중에 파이썬이 멈 춥니 다

Question

인접 그래프와 BFS 알고리즘을 사용하여 두 지점 사이의 경로를 찾는 스크립트가 있습니다. 그래프는 약 10,000 정점을 가지고 있으며, 스크립트는 다음과 같이 설정 :이 알고리즘은 작은 인접 그래프에서 작동

graph = {... 
     '9660': ['9661', '9662', '9659'], 
     '9661': ['9654', '9660'], 
     '9662': ['9660', '9663'], 
     '9663': ['9664', '9662'], 
     '9664': ['9665', '9663'], 
           ...} 


def bfs(graph, start, end): 
# maintain a queue of paths 
queue = [] 
# push the first path into the queue 
queue.append([start]) 
while queue: 
    # get the first path from the queue 
    path = queue.pop(0) 
    # get the last node from the path 
    node = path[-1] 
    # path found 
    if node == end: 
     return path 
    # enumerate all adjacent nodes, construct a new path and push it into the queue 
    for adjacent in graph.get(node, []): 
     new_path = list(path) 
     new_path.append(adjacent) 
     queue.append(new_path) 

print bfs(graph, '50', '8659') 

때문에, 내가 추측하고있어 파이썬은 그래프이 크기를 처리하는 데 정말 오랜 시간이 걸립니다. 내 목표는 최단 경로를 찾는 것이지만, 한 경로를 찾을 수 없다면 현재 의문입니다. 큰 인접 그래프를 사용하여 경로 찾기를 처리하는 비단뱀 해결책이 있습니까? 그렇다면 예제를 얻을 수 있습니까?

Answer 1

방문한 노드를 추적하지 않아 그래프가 비순환 식 그래프가 아닌 경우 많은 시간 낭비를 초래할 수 있습니다. 예를 들어, 그래프는 불필요하게 'A', 'B', 'C'와 'D'를 통해 알고리즘 것주기 bfs(graph, 'A', 'Z')를 호출

{'A': ['B', 'C', 'D', 'E'], 
'B': ['A', 'C', 'D'], 
'C': ['A', 'B', 'D'], 
'D': ['A', 'B', 'C'], 
'E': ['F'], 
'F': ['G'], 
'G': ['H'], 
... 
'W': ['X'], 
'X': ['Y'], 
'Y': ['Z']} 

경우 당신이 방문을 추적 할 경우 반면에 마지막으로 Z.에 도달하기 전에 노드의 경우 'A', 'B', 'C'및 'D'의 이웃 노드를 각각 큐에 한 번만 추가합니다.

queue = [ ['A'] ] 
visited = {} 

queue = [ ['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'] ] 
visited = {'A'} 

queue = [ ['A', 'C'], ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], 
      ['A', 'B', 'D'] ] 
visited = {'A', 'B'} 

queue = [ ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], 
      ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C'} 

queue = [ ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C', 'D'} 

queue = [ ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'E', 'F', 'G'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F'} 

queue = [ ['A', 'E', 'F', 'G', 'H'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'} 

... 
... 

queue = [ ['A', 'E', 'F', 'G', 'H', ..., 'X', 'Y', 'Z'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G', ..., 'X', 'Y'} 

# at this point the algorithm will pop off the path, 
# see that it reaches the goal, and return 

이 많이 : 알고리즘의 버전과 알파벳 그래프를 사용

는

def bfs(graph, start, end): 
    # maintain a queue of paths 
    queue = [] 

    # push the first path into the queue 
    queue.append([start]) 

    # already visited nodes 
    visited = set() 

    while queue: 
     # get the first path from the queue 
     path = queue.pop(0) 

     # get the last node from the path 
     node = path[-1] 

     # if node has already been visited 
     if node in visited: 
      continue 

     # path found 
     if node == end: 
      return path 
     # enumerate all adjacent nodes, construct a new path and push it into the queue 
     else: 
      for adjacent in graph.get(node, []): 
       # add the path only if it's end node hasn't already been visited 
       if adjacent not in visited 
        new_path = list(path) 
        new_path.append(adjacent) 
        queue.append(new_path) 

      # add node to visited set 
      visited.add(node) 

, 여기에 대기열 및 방문 세트가 전체 알고리즘을 통해 while 루프의 상단과 같을 것이다 무엇 ['A', 'B', 'A', 'B', 'A', 'B', ...]과 같은 경로를 추가하는 것보다 작업이 적습니다.