-2

我选择这个解决方案牙齿在每一行中选择任意数字。如果选择行数x1和列y1，我不能选择另一个行数x1和列y1，我必须在每一行和每一列中选择一个数，使这些数的总和尽可能小

 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 4 1  9*

但最好的解决方案是：

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

我需要改变我的功能？我这两天找不到解决办法帮帮我，我将不胜感激

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 回答