3

(おそらく) 単純なグラフ トラバーサルの質問があります。私はグラフのデータ構造として networkx を使用するグラフ初心者です。私のグラフは常に次のようになります。

             0
      1              8
   2     3       9      10
 4  5   6 7    11 12  13  14

ルート ノードから特定のノードへのパスを返す必要があります (例: を返す必要がありますpath(0, 11)) [0, 8, 9, 11]。

ツリーをトラバースするときにパスがどのように見えるかを追跡するために拡大および縮小するリストを渡すことで機能するソリューションがあり、最終的にターゲットノードが見つかったときに返されます。

def VisitNode(self, node, target, path):
    path.append(node)
    # Base case. If we found the target, then notify the stack that we're done.
    if node == target:
        return True
    else:
        # If we're at a leaf and it isn't the target, then pop the leaf off
        # our path (backtrack) and notify the stack that we're still looking
        if len(self.neighbors(node)) == 0:
            path.pop()
            return False
        else:
            # Sniff down the next available neighboring node
            for i in self.neighbors_iter(node):
                # If this next node is the target, then return the path 
                # we've constructed so far
                if self.VisitNode(i, target, path):
                    return path
            # If we've gotten this far without finding the target, 
            # then this whole branch is a dud. Backtrack
            path.pop()

この「パス」リストを渡す必要がないことを骨の髄まで感じています...コールスタックを使用してその情報を追跡できるはずですが、方法がわかりません...誰かが啓発できますかパスを追跡するためにスタックを使用してこの問題を再帰的に解決する方法について教えてください。

4

3 に答える 3

3

None失敗した場合に戻り、成功した場合に部分的なパスを返すことで、パスを回避することができます。この方法では、ルートから現在のノードまでのある種の「ブレッドクラム トレイル」を保持しませんが、ルートが見つかった場合にのみ、ターゲットからルートに戻るパスを構築します。テストされていないコード:

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]

    # If we're at a leaf and it isn't the target, return None 
    if len(self.neighbors(node)) == 0:
        return None

    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None #none of the children contains target

あなたが使用しているグラフライブラリはわかりませんが、リーフにneighbours_iterもメソッドが含まれていると思いますが、明らかにリーフの子を生成してはいけません。この場合、葉の明示的なチェックを省略して、少し短くすることができます。

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]
    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None # leaf node or none of the child contains target

elseの真の部分の中でif関数から返されているため、いくつかのステートメントも削除しました。これは一般的なリファクタリング パターンです(一部の古風な人々はこれを好みません)。これにより、不要なインデントが削除されます。

于 2013-09-28T21:27:25.893 に答える
1

メソッドの本体でパスが初期化されているパス引数をまったく避けることができます。フルパスを見つける前にメソッドが戻ると、空のリストが返されることがあります。

しかし、あなたの質問は、深さ優先検索の実装でリストの代わりにスタックを使用することについてでもありますよね? ここでフレーバーを取得します: http://en.literateprograms.org/Depth-first_search_%28Python%29。

一言で言えば、あなたは

def depthFirstSearch(start, isGoal, result):
    ###ensure we're not stuck in a cycle

    result.append(start)

    ###check if we've found the goal
    ###expand each child node in order, returning if we find the goal

    # No path was found
    result.pop()
    return False

と

###<<expand each child node in order, returning if we find the goal>>=
for v in start.successors:
    if depthFirstSearch(v, isGoal, result):
        return True

と

###<<check if we've found the goal>>=
if isGoal(start):
    return True
于 2013-09-28T22:13:04.353 に答える
0

networkx を直接使用します。

all_simple_paths(G、ソース、ターゲット、カットオフ=なし)

于 2013-10-06T11:18:38.657 に答える