3

ゴール ノードへの最短パスを返す DFS アルゴリズムが与えられました。引数として、グラフ (すべてのノードとそのパスを含む)、開始ノード、ゴール ノード、およびアクセスしたノードのリスト (空として初期化) を取ります。コードは次のとおりです。

def shortestPath(graph, start, end, visited = []):
    path = str(start)
    if start == end:
        return path
    shortest = None
    for node in graph.childrenOf(start):
        if str(node) not in visited:
            visited = visited + [str(node)]
            newPath = shortestPath(graph, start, end, visited)
            if newPath = None:
                continue
            if shortest == None or len(newPath) < shortest:
                shortest = newPath
    if shortest != None:
         path = path + shortest
    else:
         path = None
    return path

Depth First Search の概念は理解できますが、この再帰が頭を悩ませています。私の思考回路が軌道に乗っているかどうか、どこで脱線しているか教えてください。

したがって、基本的に、newPath に値が割り当てられたときに再帰が発生します。これはもちろん、shortestPath の呼び出しです。その時点で、再帰は、子を持たないノードまたはゴール ノードのいずれかに到達するまで、グラフをずっと下に進みます。ゴールではない子を持たないノードに到達した場合、基本ケースは無視され、for ループ全体が無視され、値 none が返されます。その None は、単純に再帰のチェーンに渡されます。ゴールノードに到達すると、再帰の最下層が実際に値 (パス) を返し、それが再帰の最上部にバブルアップします。

その時点で、「最短」で何が起こっているのか混乱します。そのため、newPath に実際の値が返されるたびに、shortest にその値が割り当てられますが、それがパスに追加されます。しかし、目標ノードへのパスが複数あるとしましょう。最初のパスを見つけることに成功し、パスはすべての newPaths/shortests の合計に等しくなります。しかし、ゴールに到達した次の再帰では、path はさらに newPath を追加し続けるだけではありませんか? では、最終結果は、最短パスではなく、ゴール ノードに到達するためにアクセスできるすべてのパスの長いリストになるのではないでしょうか?

4

1 に答える 1

3

path変数は関数に対してローカルです。すべての再帰呼び出しには独自のスタック フレームがあり、他の呼び出しから独立しています)。つまり、次の通話が開始されると、すべてが新しくなります。

于 2012-10-10T15:26:03.980 に答える