42

そのため、深さ優先検索を使用して解決したい問題があり、DFS が見つけた最初のパスを返します。これが私の（不完全な）DFS関数です：

    start = problem.getStartState()
    stack = Stack()
    visited = []
    stack.push(start)
    if problem.isGoalState(problem.getStartState):
        return something
    while stack:
        parent = stack.pop()
        if parent in visited: continue
        if problem.isGoalState(parent):
            return something
        visited.append(parent)
        children = problem.getSuccessors(parent)
        for child in children:
            stack.push(child[0])

startState 変数と goalState 変数は、単純に x、y 座標のタプルです。問題は、さまざまなメソッドを持つクラスです。ここで重要なのは getSuccessors (これは、3 つの項目タプルのリストの形式で特定の状態の子を返します。ただし、問題のこの部分では、タプルの最初の要素 (child[0]) のみです)。子の状態を x、y 座標で返します。これが重要です) および isGoalState (ゴール状態の x、y 座標を提供します)。

したがって、この関数は、他のすべてが適切に実装されていれば、目標状態に達すると戻ると思います (この時点でテストするのは難しい)。何か不足している場合はお知らせください。ただし、私の最大の問題は、何を返すかです。目的の状態に到達するまでに必要なすべての状態のリストを、最初から最後まで順番に出力したいと考えています。スタックには多くの未訪問の子が含まれるため、単にスタックを返すだけではうまくいかないようです。また、行き止まりに達し、後戻りしなければならない可能性があるため、行き止まりのタプルが訪問済みリストに残っている可能性があるため、訪問済みリストは有用なものを何も生成しません。希望するリストを取得するにはどうすればよいですか?

4

4 に答える 4

52

その通りです。単にスタックを返すことはできません。実際には、未訪問のノードが多数含まれています。

ただし、マップ (辞書): を維持するmap:Vertex->VertexことparentMap[v] = the vertex we used to discover vで、パスを取得できます。

必要な変更は、ほとんど for ループにあります。

    for child in children:
        stack.push(child[0])
        parentMap[child] = parent #this line was added

後でターゲットが見つかったら、ソースからターゲットへのパスを取得できます (疑似コード)。

curr = target
while (curr != None):
  print curr
  curr = parentMap[curr]

順序が逆になることに注意してください。すべての要素をスタックにプッシュしてから印刷することで解決できます。

私はかつて、このスレッドで BFS の実際のパスを見つけることに関して、同様の (同一の IMO ではありませんが) 質問に答えました。

もう 1 つの解決策は、反復 + スタックではなく DFS の再帰バージョンを使用することです。ターゲットが見つかったらcurrent、再帰内のすべてのノードをバックアップして出力しますが、この解決策ではアルゴリズムを再帰アルゴリズムに再設計する必要があります。

visitedPSグラフに無限分岐が含まれている場合、 DFSは（セットを維持していても）ターゲットへのパスを見つけることができない場合があることに注意してください。
完全な (存在する場合は常に解決策を見つける) 最適な (最短パスを見つける) アルゴリズムが必要な場合は、BFSまたは反復深化 DFSを使用するか、ヒューリスティック関数がある場合はA* アルゴリズムを使用することもできます。

于 2012-10-12T17:25:32.843 に答える
26

問題に固有のものではありませんが、このコードを微調整してさまざまなシナリオに適用できます。実際、スタックにパスを保持させることもできます。

例：

     A
   /    \
  C      B
  \     / \
   \    D E
    \    /
       F
       

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path + [neighbor]))

print (dfs_paths(graph, 'A', 'F'))   #['A', 'B', 'E', 'F']
于 2016-09-07T17:40:42.403 に答える
4

このリンクはあなたを大いに助けるはずです...それはパスを返すDFS検索について広範囲に話している長い記事です...そして私や他の誰もが投稿できるどんな答えよりも良いと思います

http://www.python.org/doc/essays/graphs/

于 2012-10-12T17:17:06.467 に答える