2

隣接グラフと BFS アルゴリズムを使用して 2 点間のパスを見つけるスクリプトがあります。グラフには約 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')

このアルゴリズムは小さな隣接グラフで機能するため、Python がこのサイズのグラフを処理するには非常に長い時間がかかると思います。私の目標は最短経路を見つけることですが、経路が 1 つでも見つからない場合、それは現在問題外です。大きな隣接グラフを使用してパス検索を処理するための Python ソリューションはありますか? もしそうなら、私は例を得ることができますか？

4

1 に答える 1

1

訪問したノードを追跡していないため、グラフが有向非巡回グラフでない場合、多くの無駄な時間が発生する可能性があります。たとえば、グラフが

{'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']}

アルゴリズムを使用して呼び出すbfs(graph, 'A', 'Z')と、最終的にZに到達する前に、「A」、「B」、「C」、および「D」を不必要に循環します。一方、訪問したノードを追跡する場合は、「A」、「B」のネイバーのみを追加します。 、「C」および「D」をそれぞれ1回キューに追加します。

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ループの上部にあるキューと訪問済みセットは次のようになります。

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

これは、のようなパスを追加するよりもはるかに少ない作業です['A', 'B', 'A', 'B', 'A', 'B', ...]。

于 2012-12-04T12:27:35.147 に答える