-1

以下のように、Pythonで深さ優先検索のサンプルコードがあります。

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            yield from self.DFS_paths_recursive(vertex, end, path+[vertex])

しかし、コードを次のように変更すると、出力が奇妙になります。私がしたことは、最後の行の再帰呼び出しの前にパスを変更しただけです。何が問題ですか？

def DFS_paths_recursive(self, start, end, path = None):
    if path == None:
        path = [start]
    if start == end:
        yield path
    else:
        unvisited = set(self._graph_dic[start]) - set(path)
        for vertex in unvisited:
            path.append(vertex)
            yield from self.DFS_paths_recursive(vertex, end, path)

たとえば、グラフのg = { "a" : ["d"], "b" : ["c"], "c" : ["b", "c", "d", "e"], "d" : ["a", "c", "e"], "e" : ["c"], "f" : ["g"], "g" : ["f"] } 場合、「a」と「e」の間のパス['a', 'd', 'c', 'b', 'e'],['a', 'd', 'c', 'b', 'e', 'e']の出力が になることもあれば、出力が になることもあります['a', 'd', 'e']。

4

1 に答える 1

0

これは とは関係ありませんyield from。を実行するとpath.append(vertex)、元のコピーが変更pathされます (つまり、呼び出し元が渡したバージョンと、再帰呼び出しに渡すバージョン)。関数内であっても、 s が繰り返されると、各再帰呼び出しは、各ループで固定ベースと単一の追加値でappendはなく、最後の値と同じ値にさらに 1 つを加えたものを処理することを意味するため、動作が異なります。path

行うことpath+[vertex]は、再帰呼び出しに渡す newlistを作成し、ミューテーションが自分の のコピーに影響を与えないようにし、 base を変更せずに再帰呼び出しごとに baseにpathnew を 1 つだけ追加することです。valuepathpath

于 2015-10-23T03:59:10.950 に答える