1

ここに私のコードがあります：

  hasht= {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
   paths=[]
   def recusive(start, finish, val):
      if start==finish and val!=1:
        return start
    else:
        for i in hasht[start]:
            path= start+ recusive(i,finish,2)
            paths.append(path)
print (recusive("C","C",1))
print paths

望ましい出力:[CDC, CDEBC, CEBC]

上記のようなテーブルを生成しようとしていますが、文字列と配列が連結されていないという問題が発生しています。私がちょうど戻ったとき、それは戻っCDCて動作しますが、return の意図どおりに関数を終了します。ここでコードを改善して機能させ、ロジックに問題があった理由を理解する方法を考えています。たとえば、 say[DC]が生成されることは理解していますが、それを回避する方法について混乱しています。おそらく返された値にインデックスを付けますか？しかし、それもうまくいきません！パスが一度戻ったら、CDC次のパスに移動する方法について混乱しています。

4

1 に答える 1

0

Python で再帰を使用する場合は、少し注意が必要です。再帰の深さの事前設定された制限が非常に低く、再帰が深すぎると、RuntimeError: maximum recursion depth exceeded in cmpのようなエラーが発生し始めるからです。

コードを実行しようとすると、「 TypeError: cannot concatenate 'str' and 'NoneType' objects 」というエラーが表示されます。これは、関数がstart == finishの場合、つまり例で再び 'C' に到達した場合にのみ値を返すためです。関数のelse部分にはreturnがないため、 start != end の場合は特別な値Noneを返します。Pythonでは、エラーを説明する文字列にNoneを追加できません。

以下のコードは、あなたがしようとしていることを実行します。これは、startNodeからendNodeまでのすべてのパスのリストを返します。ここでグラフを入力引数にすると、パスのリストが返されます。すべてのパスのリストと現在のパスを追跡するには、 allPathsとpathSoFarの2 つの追加引数が必要です。これは、これを実現するために再帰を使用する方法の例としてのみ意図されています。このコードにはいくつか問題があります。

1) 先に述べたように、再帰を使用しますが、事前に設定された制限を増やさない限り、Python ではあまり良いアイデアではありません。

2) サイクルを適切に処理しません。グラフにサイクルがある場合、この関数は再帰制限に達するまで続行します。これを確認するには、開始ノードと終了ノードとしてAを使用して実行してみてください。

    def generatePaths(theGraph, startNode, endNode, allPaths, pathSoFar=""):
        """
        Recursive function. Finds all paths through the specified
        graph from start node to end node. For cyclical paths, this stops
        at the end of the first cycle.
        """
        pathSoFar = pathSoFar + startNode

        for node in theGraph[startNode]:

            if node == endNode:
                allPaths.append(pathSoFar + node)
            else:
                generatePaths(theGraph, node, endNode, allPaths, pathSoFar)




    graph = {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
    paths = []
    generatePaths(graph, "C", "C", paths)
    print paths
于 2013-10-23T16:13:15.207 に答える