2

あるポイントAからあるポイントDまでのパスを見つけるために再帰を使用しています。パスを見つけるためにグラフを横断しています。

まあ言ってみれば：

グラフ={'A'：['route1'、'route2']、'B'：['route1'、'route2'、'route3'、'route4']、'C'：['route3'、'route4 ']、' D'：[' route4']}

アクセス可能：

A-> route1、route2

B->ルート2、ルート3、ルート4

C-> route3、route4

A-> Dからのこのパスには、2つの解決策があります。

route1-> route2-> route4

route1-> route2-> route3-> route4

ポイントBとポイントAにはルート1とルート2の両方があるため、無限ループがあるため、ノードにアクセスするたびにチェックを追加します（0または1の値）。

ただし、チェックすると、1つの解決策しか返されません：route1-> route2-> route4であり、他の可能な解決策はありません。

実際のコーディングは次のとおりです。ルートはリアクションに置き換えられます。

def find_all_paths(graph,start, end, addReaction, passed = {}, reaction = [] ,path=[]):

    passOver =  passed 

    path = path + [start]   
    reaction = reaction + [addReaction]
    if start == end:
        return [reaction] 
    if not graph.has_key(start):
        return []

    paths=[]
    reactions=[]

    for x in range (len(graph[start])):    
        for y in range (len(graph)):
            for z in range (len(graph.values()[y])):
                if (graph[start][x] == graph.values()[y][z]): 
                    if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1
                            if (graph.keys()[y] not in path):
                                newpaths = find_all_paths(graph, (graph.keys()[y]), end, graph.values()[y][z], passOver , reaction, path)
                            for newpath in newpaths:
                                reactions.append(newpath)
    return reactions

メソッド呼び出しは次のとおりです。dic_passOverは、ノードにアクセスしたかどうかを追跡する辞書です。

solution = (find_all_paths( graph, "M_glc_DASH_D_c', 'M_pyr_c', 'begin', dic_passOver ))

私の問題は、一度ルートにアクセスするとアクセスできなくなるため、他の可能な解決策が不可能であるということのようです。これを説明するために、161に最大量の再帰を追加しました。ここで、特定のコードに対して可能なすべてのルートが見つかります。

if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1

ただし、これは非常に非効率的であるように思われ、私のデータのほとんどは、数千のインデックスを持つグラフになります。さらに、すべてのルートを見つけるために許可されたノード訪問の量がわかりません。161という数字は手動で計算されました。

4

1 に答える 1

3

うーん、グラフの表現が理解できません。ただし、これは、無限ループを回避するすべてのパスを見つけるために使用できる一般的なアルゴリズムです。

最初に、ノードをそれらが接続されている一連のノードにマップするディクショナリとしてグラフを表す必要があります。例：

graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}

つまり、 fromとAに移動できます。からは に、からはに行くことができます。リンクは一方向であると想定しています。双方向にしたい場合は、双方向のリンクを追加するだけです。BCBDCD

そのようにグラフを表す場合、以下の関数を使用してすべてのパスを見つけることができます。

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node in graph[start]:
        if node in visited:
            continue
        if node == end:
            yield [start,end]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [start] + path

使用例:

>>> graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}
>>> for path in find_all_paths('A','D', graph):
...   print path
... 
['A', 'C', 'D']
['A', 'B', 'D']
>>>

グラフ表現を明確にするコメントを考慮して編集する

以下は、グラフ表現を変換する関数です (私がそれを正しく理解し、ルートが双方向であると仮定して) を上記のアルゴリズムで使用されるものに変換します

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = set()
        for link in links:
            adj |= reverse_graph[link]
        adj -= {node}
        result[node] = adj
    return result

通過したノードではなく、リンクの観点からパスを見つけることが重要な場合は、この情報を次のように保存できます。

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = {}
        for link in links:
            for n in reverse_graph[link]:
                adj[n] = link
        del(adj[node])
        result[node] = adj
    return result

そして、この変更された検索を使用します。

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node,link in graph[start].items():
        if node in visited:
            continue
        if node == end:
            yield [link]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [link] + path

これにより、通過するノードではなく、たどるリンクの観点からパスが得られます。お役に立てれば ：）

于 2013-02-26T00:58:29.163 に答える