回溯法与分支界限法.docx

实验6 回溯法与分支界限法1 回溯法C+代码#includeusing namespace std;/*判断是否可以在第row行（下标从0开始）放入下一个皇后，可以返回1，否则返回0*/int put_in(int* positions, int row)/*依次判断此皇后之前的所有皇后是否和要放入的皇后位置冲突*/for (int i = 0; i row; i+)/*判断位置是否冲突这里参考的别人写的，其中：不在同一左对角线可以表示为： arow-ai != row-i不在同一右对角线可以表示为：arow-ai != -(row-i)这两种情况可以合并为abs(arow-ai) != abs(row-i)。不在同一列可以表示为arow != ai因为已经是一行放入一个皇后，所以不会有同一行冲突的情况。*/if (abs(positionsi - positionsrow) = abs(i - row) | positionsi = positionsrow)return 0;return 1;/*递归解决N皇后问题，一次放入一个皇后，参数row表示当前要在第row行放入一个皇后*/int sovle_n_queens(int* positions, int amount_queens,int row)static int solutions = 0; /记录解的个数/这里的i表示列数，从第一列开始尝试for (int i = 0; i amount_queens; i+)positionsrow = i;/*如果可以在第row行的第i列放入一个皇后，那么就递归求解余下的部分 如果不能在第row行的第i列放入一个皇后，那么就放弃尝试这种组合*/if (put_in(positions, row) = 1)/如果已经求解到了最后一行，那么就把解的个数加1if (row = amount_queens - 1)solutions+;/打印结果cout 第 solutions 种解法为： endl;for (int i = 0; i amount_queens; i+)for (int j = 0; j amount_queens; j+)if (positionsi = j)cout ;elsecout - ;cout endl;cout endl endl;elsesovle_n_queens(positions, amount_queens, row + 1);return solutions;int main()/输入皇后的个数int amount_queens = NULL;cout 请输入皇后数量N，这表示棋盘有N*N个格子，并且有N个皇后 amount_queens;/*创建皇后位置数组，所表示意义为每个皇后放置在哪一列，行号为数组下标+1，这里不采用二维数组，因为二维数组会使数组的管理以及验证是否可以放入下一个皇后变得更麻烦*/int* positions = new intamount_queens;/解决N皇后问题并打印解得个数cout amount_queens 皇后问题共有 sovle_n_queens(positions, amount_queens, 0) 个解 endl;system(pause);return 0;运行结果截图算法分析回溯法解决八皇后问题，并推广至N皇后问题，思路是很简单的，只需要一次新增加一个皇后，并判断此皇后可以放在当前行的哪些位置，如果可以在某些列放下去而不产生冲突，那么就在这些方法中继续递归求解下一行。如果在当前行任何位置都不能摆放一个皇后，就放弃当前的某一种尝试。虽然代码很短，但是写起来是不好写的，因为递归程序并不好调试。所以要注意写递归程序的要点：1) 合理定义递归程序的入口和出口2) 每次递归，只是将问题的规模缩小，而问题性质是不变的。在这个算法中是一次求解棋盘中的一行达到规模缩小而问题性质不变。2 分支界限法C+代码#include#include#includeusing namespace std;/*单个物品类，树中的节点和用户输入的物品都用这个类表示*/class stuffpublic:int weight; /重量int value; /价值 int tree_level; /在搜索树中的层数 int up_bound; /此节点的上界stuff() /空构造函数/重载构造函数stuff(int weightt, int valuee, int tree_levell, int up_boundd):weight(weightt), value(valuee), tree_level(tree_levell), up_bound(up_boundd);/对物品的单位价值进行降序排序时用到的函数bool stuff_sort(stuff src1, stuff src2)if (src1.value / (double)src1.weight src2.value / (double)src2.weight)return true;elsereturn false;/解决01问题，stuffs是物品的集合，bag_space是背包的最大容量，返回值是可以装入的最大价值int sovle_01bag(vector stuffs, int bag_space)int tree_level = 0;/当前树中的层数int current_weight = 0; /当前总重量（可能是最优解的一部分，但不一定是）int current_value = 0; /当前总价值（可能是最优解的一部分，但不一定是）int max_value = 0; /背包可以装入最大价值/初始上界，就是背包容量物品的最大单位价值int bound = (stuffs0.value / (double)stuffs0.weight)*bag_space;/可能的节点的集合（可能的节点是指节点可能包含在最优解中）vector possbile_nodes;/*从第0个物品开始，一直运行直到搜索完所有可能的节点 其中第一个if语句段判断当前结点的左孩子节点（放入此物品） 第二个if语句段表示判断当前结点的右孩子节点（不放入此物品） */while (true)/加入下一个物品后的总重量int update_weight = current_weight + stuffstree_level.weight;if (update_weight max_value)max_value = current_value + stuffstree_level.value;/计算左孩子节点的上界，参见教材P335double ratio = stuffstree_level.value / (double)stuffstree_level.weight;bound = current_value + ratio * (bag_space - current_weight);/如果左孩子节点是有希望的，那就把右孩子节点加入以后的搜索过程中if (tree_level = max_value)stuff new_possible_node(update_weight, current_value + stuffstree_level.value, tree_level + 1, bound);possbile_nodes.push_back(new_possible_node);/*计算右孩子的上界，参见教材P335*/double ratio = stuffstree_level.value / (double)stuffstree_level.weight;bound = current_value + ratio * (bag_space - current_weight);/如果右孩子节点是有希望的，那就把右孩子节点加入以后的搜索过程中if (bound = max_value & tree_level stuffs.size() - 1)stuff new_possible_node(current_weight, current_value, tree_level + 1, bound);possbile_nodes.push_back(new_possible_node);/*搜索完了所有有希望的节点，那就返回最优解*/if (possbile_nodes.size() = 0)return max_value;/*将所需参数更新为下一个有希望的节点所包含的参数，同时将此节点出栈*/stuff next_node = possbile_nodespossbile_nodes.size()-1;tree_level = next_node.tree_level;bound = next_node.up_bound;current_value = next_node.value;current_weight = next_node.weight;possbile_nodes.pop_back();return 0;int main()/物品个数定义为10，后面都采用动态空间申请，因此此数字可以改为由用户动态输入int amount_stuff = 10;/背包容量定义为50，可改为用户动态输入int bag_space = 50;/物品的集合vector stuffs(amount_stuff);/输入物品的重量cout 请依次输入物品的重量 endl;for (int i = 0; i stuffsi.weight;/输入物品的价值cout 请依次输入物品的价值 endl;for (int i = 0; i stuffsi.value;/对输入物品进行单位价值的降序排序，计算上界时用到sort(stuffs.begin(),stuffs.end(),stuff_sort);/输出结果int max_value = sovle_01bag(stuffs, bag_space);cout 背包内可以装入的最大价值为 max_value endl;system(pause);return 0;运行结果截图算法分析首先，这个算法是很神奇的，因为在之前使用动态规划法解决01背包问题之后，我一度以为使用穷举的方法因为运算量太大，是基本不可行的。但是使用分支界限法是可以得，而且，即使把分支界限法中的上界bound固定为一个非常大的数，也就是说，完完全全的使用穷举法，不对穷举法进行任何优化，也是可以在瞬间求解的。这充分说明了计算机强大的计算能力。其次，分支界限法是对穷举法的改进