递归回溯的问题 [英] Problem with recursive backtracking
问题描述
大家好，我最近发布了有关我的算法问题的信息.
Hey guys, recently posted up about a problem with my algorithm.
我已经稍微修改了代码，因此现在回溯了一定程度，但是输出仍然有缺陷.香港专业教育学院调试此相当检查所有变量值，似乎无法找出问题.
Ive amended the code slightly, so it now backtracks to an extent, however the output is still flawed. Ive debugged this considerablychecking all the variable values and cant seem to find out the issue.
与全面解决方案相对比，再次获得建议将有很大帮助.我认为我的代码只有几个问题，但是我无法解决问题所在.
Again advice as opposed to an outright solution would be of great help. I think there is only a couple of problems with my code, but i cant work out where.
//来自上一篇文章:
基本上，将一个集传递给下面的此方法，并且还传递一个条形的长度.如果从集合中删除了某些数字，则解决方案应输出该集合中的数字，这些数字可提供最少的浪费钢筋长度.因此，钢筋长度10，集合包括6,1,4，因此解为6和4，浪费为0.我在通过集合回溯的条件上遇到了一些麻烦. Ive还尝试使用浪费的全局"变量来帮助回溯，但无济于事.
Basically a set is passed to this method below, and a length of a bar is also passed in. The solution should output the numbers from the set which give the minimum amount of waste if certain numbers from the set were removed from the bar length. So, bar length 10, set includes 6,1,4, so the solution is 6 and 4, and the wastage is 0. Im having some trouble with the conditions to backtrack though the set. Ive also tried to use a wastage "global" variable to help with the backtracking aspect but to no avail.
SetInt是一个手工制作的集合实现，可以添加，删除，检查集合是否为空并从集合中返回最小值.
SetInt is a manually made set implementation, which can add, remove, check if the set is empty and return the minimum value from the set.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package recursivebacktracking;
/**
*
* @author User
*/
public class RecBack {
int WASTAGE = 10;
int BESTWASTAGE;
int BARLENGTH = 10;
public void work()
{
int[] nums = {6,1,2,5};
//Order Numbers
SetInt ORDERS = new SetInt(nums.length);
SetInt BESTSET = new SetInt(nums.length);
SetInt SOLUTION = new SetInt(nums.length);
//Set Declarration
for (int item : nums)ORDERS.add(item);
//Populate Set
SetInt result = tryCutting(ORDERS, SOLUTION, BARLENGTH, WASTAGE);
result.printNumbers();
}
public SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft, int waste)
{
for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
{
int a = possibleOrders.min(); //select next candidate
System.out.println(a);
if (a <= lengthleft) //if accecptable
{
solution.add(a); //record candidate
lengthleft -= a;
WASTAGE = lengthleft;
possibleOrders.remove(a); //remove from original set
if (!possibleOrders.isEmpty()) //solution not complete
{
System.out.println("this time");
tryCutting(possibleOrders, solution, lengthleft, waste);//try recursive call
BESTWASTAGE = WASTAGE;
if ( BESTWASTAGE <= WASTAGE )//if not successfull
{
lengthleft += a;
solution.remove(a);
System.out.println("never happens");
}
} //solution not complete
}
} //for loop
return solution;
}
}
推荐答案
您是否考虑过使用位掩码算法，而不是使用回溯?我认为这会使您的算法更加简单.
Instead of using backtracking, have you considered using a bitmask algorithm instead? I think it would make your algorithm much simpler.
以下是您如何执行此操作的概述:
Here's an outline of how you would do this:
让N为您集合中元素的数量.因此，如果集合为{6,1,2,5}，则N为4.令max_waste为我们可以消除的最大浪费(在您的示例中为10).
Let N be number of elements in your set. So if the set is {6,1,2,5} then N would be 4. Let max_waste be the maximum waste we can eliminate (10 in your example).
int best = 0; // the best result so far
for (int mask = 1; mask <= (1<<N)-1; ++mask) {
// loop over each bit in the mask to see if it's set and add to the sum
int sm = 0;
for (int j = 0; j < N; ++j) {
if ( ((1<<j)&mask) != 0) {
// the bit is set, add this amount to the total
sm += your_set[j];
// possible optimization: if sm is greater than max waste, then break
// out of loop since there's no need to continue
}
}
// if sm <= max_waste, then see if this result produces a better one
// that our current best, and store accordingly
if (sm <= max_waste) {
best = max(max_waste - sm);
}
}
此算法与回溯非常相似，并且具有相似的复杂性，只是不使用递归.
This algorithm is very similar to backtracking and has similar complexity, it just doesn't use recursion.
位掩码基本上是二进制表示，其中1表示我们使用集合中的项，而0表示我们不使用.由于我们是从1循环到(1<<N)-1，因此我们正在考虑给定项目的所有可能子集.
The bitmask basically is a binary representation where 1 indicates that we use the item in the set, and 0 means we don't. Since we are looping from 1 to (1<<N)-1, we are considering all possible subsets of the given items.
请注意，此算法的运行时间会随着N的增加而迅速增加，但是当N≤20时应该没问题.顺便说一句，回溯适用相同的限制.如果需要更快的性能，则需要考虑另一种技术，例如动态编程.
Note that running time of this algorithm increases very quickly as N gets larger, but with N <= around 20 it should be ok. The same limitation applies with backtracking, by the way. If you need faster performance, you'd need to consider another technique like dynamic programming.
对于回溯，您只需要跟踪集合中的哪个元素，就可以尝试使用该元素，也可以不使用它.如果使用它，则将其添加到总计中，如果未使用，则继续进行下一个递归调用，而不会增加总计.然后，您减少总数(如果您增加了总数)，这就是回溯的来源.
For the backtracking, you just need to keep track of which element in the set you are on, and you either try to use the element or not use it. If you use it, you add it to your total, and if not, you proceeed to the next recursive call without increasing your total. Then, you decrement the total (if you incremented it), which is where the backtracking comes in.
这与上面的位掩码方法非常相似，我提供了位掩码解决方案以帮助您更好地了解回溯算法的工作原理.
It's very similar to the bitmask approach above, and I provided the bitmask solution to help give you a better understanding of how the backtracking algorithm would work.
编辑 好的，我没有意识到您需要使用递归.
EDIT OK, I didn't realize you were required to use recursion.
提示1 首先，我认为您可以通过仅使用一个递归函数并将逻辑放入该函数中来大大简化您的代码.无需提前构建所有集合然后进行处理(我不确定这就是您正在做的事情，但是从您的代码看来，这是必须的).您可以只构建集合，然后跟踪集合中的位置.当您到达集合的最后时，看看您的结果是否更好.
Hint1 First, I think you can simplify your code considerably by just using a single recursive function and putting the logic in that function. There's no need to build all the sets ahead of time then process them (I'm not totally sure that's what you're doing but it seems that way from your code). You can just build the sets and then keep track of where you are in the set. When you get to the end of the set, see if your result is better.
提示2 如果您仍然需要更多提示，请尝试考虑回溯功能应该做什么.终止条件是什么?当我们达到终止条件时，我们需要记录什么(例如，是否获得了新的最佳结果等)?
Hint2 If you still need more hints, try to think of what your backtracking function should be doing. What are the terminating conditions? When we reach the terminating condition, what do we need to record (e.g. did we get a new best result, etc.)?
提示3 扰流板警报 下面是一个C ++实现，可为您提供一些想法，因此，如果您想自己做更多的工作，请在这里停止阅读.
Hint3 Spoiler Alert Below is a C++ implementation to give you some ideas, so stop reading here if you want to work on it some more by yourself.
int bestDiff = 999999999;
int N;
vector< int > cur_items;
int cur_tot = 0;
int items[] = {6,1,2,5};
vector< int > best_items;
int max_waste;
void go(int at) {
if (cur_tot > max_waste)
// we've exceeded max_waste, so no need to continue
return;
if (at == N) {
// we're at the end of the input, see if we got a better result and
// if so, record it
if (max_waste - cur_tot < bestDiff) {
bestDiff = max_waste - cur_tot;
best_items = cur_items;
}
return;
}
// use this item
cur_items.push_back(items[at]);
cur_tot += items[at];
go(at+1);
// here's the backtracking part
cur_tot -= items[at];
cur_items.pop_back();
// don't use this item
go(at+1);
}
int main() {
// 4 items in the set, so N is 4
N=4;
// maximum waste we can eliminiate is 10
max_waste = 10;
// call the backtracking algo
go(0);
// output the results
cout<<"bestDiff = "<<bestDiff<<endl;
cout<<"The items are:"<<endl;
for (int i = 0; i < best_items.size(); ++i) {
cout<<best_items[i]<<" ";
}
return 0;
}
这篇关于递归回溯的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
