7

私はこれを一週間ずっと試してきましたが、私の人生では、それを理解することはできません.

pathSoFar を再帰して返すヘルパー関数が必要であることはわかっています。再帰について頭が回らないようです。

私は非常に混乱しているので、再帰以外の問題を正確に定式化することさえできません。

助けてくれてありがとう。

編集：わかりました、少し明確にします。私を混乱させることの 1 つは、ノードに隣接ノードがない場合に返されるパスです。ゴール パスが最初に返される場合がありますが、ヘルパーがまだ再帰的であるため、行き止まりのパスが返される可能性があります。私はバックトラックについて混乱していると思います。

4

2 に答える 2

9

ウィキペディアには、深さ優先トラバーサルのための非常に優れた疑似コードがあります。これらのトラバーサル アルゴリズムは、トラバーサルに表示される順序でグラフ内のすべてのノードにラベルを付けます。代わりに、ゴールが見つかったらすぐにパスをゴールに戻す必要があります。

それでは、ウィキペディアのアルゴリズムを変更しましょう。

( INCORRECT ALGORITHM DELETED WHICH THE OP COMMENTED ON CORRECTLY BELOW )

Python の実装は次のとおりです。

g = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'E', 'F'],
    'C': ['A'],
    'D': ['B', 'F', 'G', 'H'],
    'E': ['G'],
    'F': ['A', 'F'],
    'G': ['H', 'I'],
    'H': [],
    'I': []
}

def DFS(g, v, goal, explored, path_so_far):
    """ Returns path from v to goal in g as a string (Hack) """
    explored.add(v)
    if v == goal: 
        return path_so_far + v
    for w in g[v]:
        if w not in explored:
            p = DFS(g, w, goal, explored, path_so_far + v)
            if p: 
                return p
    return ""

# Hack unit test
assert DFS(g, 'A', 'I', set(), "") == "ABEGI"
assert DFS(g, 'A', 'E', set(), "") == "ABE"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'A', 'M', set(), "") == ""
assert DFS(g, 'B', 'A', set(), "") == "BCA"
assert DFS(g, 'E', 'A', set(), "") == ""

ここでの考え方は、 からへgの経路をグラフ で見つけたいということです。 実際には の直前に終了する必要があります。vgoalpath_so_farpath_so_farv

vが目標である場合は、vこれまでのパスに追加できます。それだけです。

vそれ以外の場合は、エッジの反対側のノードをまだ探索していない、そこから発するすべてのエッジを探索する必要があります。これらのエッジのそれぞれについて、これまでのパスと現在のノードを使用して (再帰的に) 検索できます。ゴールへのパスがない場合はv、空のパスが返されます。

良い点は、再帰呼び出しに拡張パスを渡すため、再帰を使用して「自動的にバックトラック」することです。

于 2011-09-10T22:37:46.357 に答える
1

再帰とは、問題をより小さな問題のセットに縮小することです。

この場合、ノード A からノード Z へのルートを見つけようとしているとします。まず、A の近隣ノードを調べます。それらが B、C、および D であるとします。

ここで、B から Z、C から Z、D から Z へのルートを見つけるという 3 つのサブ問題があります。これらの問題のいずれかを解決できれば、A から Z へのパスを見つけるというより大きな問題も解決したことになります。 .

だから、あなたは再帰します。B、C、および D で findPath メソッドを使用し、それぞれに A を含むこれまでにアクセスしたノードのリストを与えます (逆行を防ぐため) [1]。そのうちの誰かが「私は道を見つけた」と言ったら、あなたは彼らが戻ってきたその道をたどり、その最初に A を貼り付けて、それを一日と呼びます。

再帰呼び出しでは、最終的に Z の隣のノードに到達します (A と Z が実際に接続されている場合)。それが起こったとき、あなたは問題を解決しました: そのリンクを返します. すべてのネイバーがすでに訪問されている行き止まりのノードに到達した場合は、コードを返して、呼び出し元にそれが行き止まりであり、そのノードを使用してソリューションを構築するべきではないことを知らせます。

[1] 補足: あなたが非常に賢い場合は、C の再帰呼び出しに渡すリストに B を入れ、D に渡すリストに B+C も入れます。

于 2011-09-10T22:25:17.990 に答える