c++ - バックトラックの停止

Question

プログラムを終了せずに最初の解決策を見つけた後、バックトラッキングアルゴリズムを停止する方法はC / C ++にありますか？

関数がすぐに関数を終了するようにしたいのですが、すべてのレベルの再帰を1つずつ終了してリターンを示すのではありません。

score 5 · Accepted Answer

手っ取り早い方法は、例外をスローしてベースレベルでキャッチすることです (現在、多くの人がエラーに対してのみ例外を使用するように叫ぶでしょう。私は、解決策を見つけることは例外的なイベントであると主張します。ノーマル)

score 3 · Accepted Answer

何が必要なのか正確にわからない場合は、独自のスタックの実装を検討し、再帰を完全に回避します。そうすれば、バックトラッキングツリーを終了すること (1 回の「リターン」) が簡単になり、ユーザー定義スタックの状態が保持されていると仮定して、関数を再度呼び出すことで次の解決策を見つけるために検索を再開することもできます (静的変数で)。もちろん、単純な再帰プログラムをループに変換するには、プログラミングのオーバーヘッドが多少かかりますが、実行するのは非常に簡単です。

score 3 · Accepted Answer

完了時に設定され、関数でチェックされるフラグがある場合、これを解決できます。例えば

void foo(..)
{
   if (g_done) return;
...
}

score 1 · Accepted Answer

実際には実装によって異なりますが、特別なパラメータを設定して、「解決策が得られましたか？はいの場合は、現在のルーチンを中止して、その解決策のみを出力に取得する」などのフラグとして使用できます。

score 1 · Accepted Answer

関数をすぐに終了させたいのはなぜですか? 破棄する必要のあるオブジェクトがスタック上にある可能性があるため、スタックをバックトラックしないことは危険です。例外をスローすると、トリックが発生する可能性があり、スタックがクリーンアップされます。あなたがしようとしていることについてより多くの情報を提供してください。他のアプローチを提供できるかもしれません。

score 0 · Accepted Answer

バックトラッキングアルゴリズムが実際にこれが問題になるほど深く再帰している場合は、スタックを爆破する危険があるため、再帰を使用しないでください。longjmpを含む残虐行為を犯すのではなく、状態を表すPODオブジェクトを格納する独自のヒープ割り当てスタックを使用して、アルゴリズムを反復アプローチに書き直すことを検討する必要があります。ソリューションを見つけたら、状態コンテナを1つの効率的なステップで破棄して、答えを返すことができます。

再帰から反復への移行方法を参照してください

score 0 · Accepted Answer

C と C++ の両方で setjmp()/longjmp() を使用して、フラグをずっと後ろに渡す必要性をバイパスする粗いが効果的な方法を使用できます。

score 0 · Accepted Answer

まず、再帰関数に対しては実行できないことに注意してください。次のコードを検討してください。

int SumNum(int nMax)
{
    if (0 == nMax)
        return 0;
    else
        return nMax + SumNum(nMax-1);
}

実際の値は、バックトラッキング中に計算されます。

ただし、次の方法でコードを書き直すことができます。

int SumNum(int nMax, int nSum)
{
    if (0 == nMax)
        return nSum;
    else
        return SumNum(nMax-1, nSum+nMax);
}

これで、次のトリックを実行できます。

    int SumNum(int nMax, int nSum)
    {
        if (0 == nMax)
            throw nSum;
        else
            return SumNum(nMax-1, nSum+nMax);
    }


f()
{
        int nSum;

        try
        {
            SumNum(100, 0);
        }
        catch (int _nSum)
        {
            nSum= _nSum;
        }
}

c++ - バックトラックの停止

8 に答える 8

Related

Reference