2

まず、この質問をご覧いただきありがとうございます。

学校の課題では、BFSアルゴリズムを作成し、それを使用してさまざまなことを行うことになっています。これらの1つは、グラフのルートノードとゴールノードの間のすべてのパスを見つけることになっているということです。コピー/サイクルも含めずにすべての代替ルートを追跡する方法が見つからないため、これを行う方法がわかりません。

これが私のBFSコードです：

def makePath(predecessors, last):
    return makePath(predecessors, predecessors[last]) + [last] if last else []

def BFS1b(node, goal):
    Q = [node]
    predecessor = {node:None}

    while Q:
        current = Q.pop(0)
        if current[0] == goal:
            return makePath(predecessor, goal)

        for subnode in graph[current[0]][2:]:
            if subnode[0] not in predecessor:
                predecessor[subnode[0]] = current[0]
                Q.append(subnode[0])

正しい方向への概念的な推進をいただければ幸いです。

tl; dr BFSを使用して2つのノード間のすべてのパスを見つけるにはどうすればよいですか？

ジェフ・マルカドの質問に答える方法がわからないので、これがグラフです。 

graph = {   'A':[366, 3,    ('Z',   75 ), ('T', 118), ('S', 140)],
            'Z':[374, 2,    ('A',   75 ), ('O', 71 )],
            'T':[329, 2,    ('A',   118), ('L', 111)],
            'L':[244, 2,    ('T',   111), ('M', 70 )],
            'M':[241, 2,    ('L',   70 ), ('D', 75 )],
            'D':[242, 2,    ('M',   75 ), ('C', 120)],
            'C':[160, 3,    ('D',   120), ('R', 146), ('P', 138)],
            'R':[193, 3,    ('C',   146), ('P', 97 ), ('S', 80 )],
            'S':[253, 4,    ('R',   80 ), ('F', 99 ), ('O', 151), ('A', 140)],
            'O':[380, 2,    ('S',   151), ('Z', 71 )],
            'P':[100, 3,    ('C',   138), ('R', 97 ), ('B', 101)],
            'F':[176, 2,    ('S',   99 ), ('B', 211)],
            'B':[  0, 4,    ('P',   101), ('F', 211), ('G', 90 ), ('U', 85 )],
            'G':[ 77, 1,    ('B',   90 )],
            'U':[ 80, 3,    ('B',   85 ), ('H', 98 ), ('V', 142)],
            'H':[151, 2,    ('U',   98 ), ('E', 86 )],
            'E':[161, 1,    ('H',   86 )],
            'V':[199, 2,    ('U',   142), ('I', 92 )],
            'I':[226, 2,    ('V',   92 ), ('N', 87 )],
            'N':[243, 1,    ('I',   87 )],
            'W':[400, 1,    ('X',   100)],
            'X':[400, 1,    ('W',   100)],}
4

1 に答える 1

2

まず、ゴールノードに到達したときにアルゴリズムが戻らないようにする必要があります。そうしないと、解決策が1つだけになります。代わりに、リストを使用してさまざまなソリューションを保存する必要があります。

アルゴリズムのコアに関しては、BFS検索では一度に1つのパスではなく、すべてのパスが探索されることに注意してください。したがって、キューに1つのノードを格納するだけでなく、パスを格納することもできます。

次に、次のノードが現在のパスにまだ存在しないかどうかを確認して、サイクルを回避します。現在のパスの最後のノードが目標ノードである場合は、それをソリューションリストに追加します。

最後に、キューに不完全なパスがなくなったら（==キューが空の場合）、ソリューションリストを返します。

于 2012-11-01T09:21:59.147 に答える