5

重複の可能性：
[python]：2つのノード間のパス

誰かがこれを行う方法に関するいくつかのリソースを私に指摘できますか？私はnetworkxPythonライブラリとして使用しています。

ありがとう！

4

3 に答える 3

6

これはAlexMartelliの回答に基づいていますが、機能するはずです。source_node.childrenこれは、のすべての子を反復処理する反復可能を生成する式に依存しsource_nodeます。==また、オペレーターが2つのノードを比較して、それらが同じであるかどうかを確認するための実用的な方法があることにも依存しています。使用isする方が良い選択かもしれません。どうやら、使用しているライブラリでは、すべての子に対して反復可能にするための構文はgraph[source_node]であるため、それに応じてコードを調整する必要があります。

def allpaths(source_node, sink_node):
    if source_node == sink_node: # Handle trivial case
        return frozenset([(source_node,)])
    else:
        result = set()
        for new_source in source_node.children:
            paths = allpaths(new_source, sink_node, memo_dict)
            for path in paths:
                path = (source_node,) + path
                result.add(path)
        result = frozenset(result)
        return result

私の主な懸念は、これが深さ優先探索を行うことです。ソースから、孫、曽孫など、すべてのソースであるが、必ずしもシンクの親ではないノードへのパスがいくつかある場合、労力が無駄になります。特定のソースノードとシンクノードの回答をメモ化すると、余分な労力を回避できます。

これがどのように機能するかの例です：

def allpaths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong 
        memo_dict = dict()

    if source_node == sink_node: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = set()
            for new_source in source_node.children:
                paths = allpaths(new_source, sink_node, memo_dict)
                for path in paths:
                    path = (source_node,) + path
                    result.add(path)
            result = frozenset(result)
            # Memoize answer
            memo_dict[(source_node, sink_node)] = result
            return result

これにより、呼び出しの間にメモ化ディクショナリを保存できるため、複数のソースノードとシンクノードの回答を計算する必要がある場合は、多くの余分な労力を回避できます。

于 2010-07-19T05:06:52.607 に答える
2

これは実際にはnetworkxで機能し、再帰的ではないため、大きなグラフに適している場合があります。

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths
于 2011-04-16T00:07:09.590 に答える
1

利用可能な特別な最適化があるかどうかはわかりません-それらのいずれかを探す前に、次のような単純な再帰的ソリューションを実行します（networkxを使用すると、ノードによってグラフにインデックスを付ける機能のみを使用して、隣接ノード[[networkxの場合はdictですが、特にそれを利用していません]]）...：

def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()):
  set_of_result_paths = set()
  for n in source_nodes:
    next_from_n = []
    for an in G[n]:
      if an in set_of_sink_nodes:
        set_of_result_paths.add(path_prefix + (n, an))
      else:
        next_from_n.append(an)
    if next_from_n:
      set_of_result_paths.update(
          allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,)))
  return set_of_result_paths

これは確かに正しいはずです（しかし、非常に遅く、疲れていて頭がおかしいので、証明はしません;-)そしてさらなる最適化を検証するために使用できます;-)。

私が試みる最初の最適化は、ある種の簡単なメモ化です。ノードNから任意のゴールノードへのパスのセットをすでに計算している場合（その計算を行ったときにNにつながるプレフィックスが何であれ）、隠しておくことができますキーNの下の辞書でそれを取り除き、別のルートで再びNに到達した場合は、それ以上の再計算を避けます;-)。

于 2010-07-19T06:17:50.593 に答える