0

この問題を正確に解決する方法がわかりません。12 ノード AL のグラフが表示されました。17 個のエッジがそれらを接続します。A から L までのすべてのパスを見つけるように言われました。ノードを複数回トラバースできますが、エッジは 1 回しかトラバースできません。出力には、各パスとパスの総数が表示されます。

たとえば、パスが 1 つだけの場合。出力は次のようになります。

ABCDEFGHIJKL
12

再帰的な深さ優先検索機能で解決できるはずだと思っていましたが、すべてのパスを出力する方法がわかりません。たとえば、関数がパス ABDL を見つけて末尾 L に到達した場合、ABDL を出力します。次に、D に戻り、別のパスを見つけようとします。次の行で A から再度印刷するにはどうすればよいですか?

任意の入力をいただければ幸いです。ありがとう！

4

1 に答える 1

0

情報を最後のノードに渡して、行き止まりになったときにたどったパスを出力するか、たどったパスを呼び出し元に戻して、最後にパス全体を出力できるようにします。

子関数を再帰的に呼び出してデータを転送することは明らかなはずです...あえて言えば、簡単です;)

これを逆に行うには、再帰関数が子呼び出しからトラバースされたノードのリスト (トラバースされたサブパスのリスト) を戻り値として受け入れるようにします。関数の最後に、サブコールの場合は、関数自体がアクセスしたノード パスと共にそれらを返します (他のノードの先頭に追加し、それ以上の深さ再帰がない場合は、単一のノードをリストに追加します)。いくつかのノードで行われました)。

最後に、サブコールでない場合は、通過したすべてのパスの完全なリストが表示されます。それらを印刷するだけです。

たとえば、[AAA、ABA、ACA、ABC、ACC] という文字を調べたいとします。いくつかのパスは無効です (たとえば、A の後に C をトラバースすることは許可されていません)。

def mypathsearch(path_traversed, current_letter, left_letters): """検索された文字列、current_letter 文字、および各位置の残りの文字の組み合わせを含む文字配列の配列を取ります"""

if can_traverse(path_traversed, current_letter):

    for next_letter in remaining_letters[0]:
        letters_after = remaining_letters[1:]

        sub_paths_searched = mypathsearch(
            path_traversed + current_letter, next_letter, letters_after
        )

else:
    # end of the line
    print_path_traversed(path_traversed)
于 2013-10-07T23:42:01.360 に答える