ナイトツアー問題を考えてみましょう。それは反復に変換できますか？私を混乱させているのは、バックトラックの部分です。ループでバックトラックするにはどうすればよいですか? 再帰から反復に移行する場合、バックトラッキングを実装するために必ずスタック データ構造を使用する必要がありますか?
私はここでこの質問をより良い方法で尋ねました:再帰の代わりに反復によるバックトラックの実用的な例をコードで説明できる人はいますか?
質問する
8007 次
3 に答える
8
すべての再帰アルゴリズムは反復アルゴリズムに変換でき、その逆も可能です。これは、Church-Turing テーゼの直接的な結果です。
常に明白 (または自明) であるとは限りませんが、どのアルゴリズムも再帰的または反復プロセスとして表現できます。一般的なケースでは、この質問は以前に回答されています。
howに関しては、あるスタイルから別のスタイルに移行するために適用できるいくつかの手法があります。たとえば、この回答を参照するか、より詳細な議論については、スタックを使用して再帰を排除する方法を説明するこの記事を参照してください。
于 2012-12-08T21:33:00.623 に答える
3
基本的に、すべての再帰はループ+スタックとして実装できます。これは、基本的にマシン（ハードウェア）レベルで実装されたものであるため、リターンアドレスと引数を格納するための一連のブランチとスタックだけです。
条件が満たされていない間に繰り返すループを作成し、再帰呼び出しの代わりに、次の反復 (および場合によっては最後の状態) のパラメーターをスタックにプッシュし、ループの開始点に戻ります。
編集:(単純な再帰ではなく、末尾再帰バックトラッキングについて話していることは明らかなので):
ウィキペディアから: In computer science, a tail call is a subroutine call that happens inside another procedure as its final action. 私の知る限り、複数の再帰呼び出しを持つ関数は、定義上、末尾再帰ではなく、バックトラッキング アルゴリズムには複数の呼び出しがあるため、「末尾再帰」ではありません。
また、ループと定数スペースのみを持つプログラムは、多項式時間で実行される 2 番目のプログラム P' に変換できることに注意してください (ほとんどの2^CONST状態は基本的CONST'に であり、これらのそれぞれの検証は多項式時間で行われるため) - 時間の合計、CONST'*p(n). これはまだ多項式です)、そうでない限りP=NP、バックトラッキングの解をループベースの多項式の解に変換することで多項式時間でSATを解くことができるため、不可能です。（そして、とにかくそれが不可能であることを示すために、 HPからさらに削減することは実行可能だと思います）。
于 2012-12-08T21:33:17.287 に答える