-2

私はこのソリューションを選択します各行の歯は任意の数を選択します。行 x1 と列 y1 の数を選択した場合、行 x1 と列 y1 の別の数を選択することはできません。これらの数の合計ができるだけ小さくなるように、各行と列で 1 つの数を選択する必要があります。

 1 2 3 1
 2 3 1 3
 2 2 1 2
 3 4 1 9

私の関数は、最適ではないソリューションを1つだけ生成します。

 1* 2 3 1
 2 3* 1 3
 2 2 1* 2
 3 4 1  9*

しかし、最善の解決策は次のとおりです。

 1 2 3 1*
 2 3 1* 3
 2* 2 1 2
 3 1* 1 9

関数で何を変更する必要がありますか? 私は2日間の解決策を見つけることができません私は感謝します

bool back(int n, r ** tab, int k){
    for(int i=0;i<n;i++){
        if (check(n,tab,k)){
            tab[k][i].moze=true;
            if (k==n-1)
            {
                for(int j=0;j<n;j++)
                {
                    for(int c=0;c<n;c++)
                    {
                        if(tab[j][k].moze==true)
                            cout<<tab[j][i].quantity;
                    }
                }
                return true;
            }

            if (back(n,tab,k+1))
                return true;
            else

                tab[k][i].moze=false;
        }
    }
    return false;
}

誰か私があなたのために解決するのを手伝ってください、それはおそらく数分の質問です私はすでに5日疲れています

4

1 に答える 1

-1

バックトラッキングは、最適な解を見つけたい場合ではなく、解を見つけたい場合に使用します。意思決定ツリーで続行できない位置に到達すると、後戻りして以前のソリューションで別の選択肢を選択します。あなたの場合、通常のアプローチは、順番にすべての順列をテストすることです。これにより、O(n!)-高価になります。

今でも、教育的なバックトラックに似たものを使用できます。すべての部分的な解決策について、最良の結果を改善できない可能性のあるものをすべて除外します。そうすれば、決定木の枝全体を切り取ることができます。最初のステップとして貪欲なアルゴリズムを使用して適切なソリューションを見つけることは、このアプローチに役立ちます。問題は、これによってアルゴリズムが大幅に高速化されないことです。これは、最良の解があることを知る前に、ツリーの大部分をたどる必要があるためです。それでも面白いです。

バックトラックを練習したい場合は、数独ソルバーを試してください。;)

于 2013-10-16T19:45:31.513 に答える