算法与数据结构程式设计报告B.docVIP

回溯法应用 课题内容和要求 在人机对弈、决策问题、人工智能、组合数学等等一系列非数值问题的算法设计中，回溯法是经常采用的一种重要而有效的方法。 回溯法是一种选优有哪些信誉好的足球投注网站法。按选择最优解的条件向前有哪些信誉好的足球投注网站，以达到目的。但每当有哪些信誉好的足球投注网站到某一步时，发现其达不到预期的效果，就退回一步重新选择。这种行不通就退回的技术称为回溯法。 回溯法的逻辑思路可表示为一棵数，根节点是初始状态，没有哪些信誉好的足球投注网站到一个节点都有若干个可供选择的后续节点，没有任何能够达到目标的暗示，只有走着瞧，不行了就回溯到上一层节点，回复刚刚使用的参数，再走另一条路径，所以回溯法的本质是穷举与试探，找到从根节点到叶子节点的所有正确结果。 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 二、需求分析 运用面向对象思想，将八皇后问题的解决放在一个类中来解决。 “构造函数模块”用来实现数据的初始化。 “主程序模块”，负责调用其他函数依次在一到八行放置皇后，并按一定规律调整皇后位置，求出八皇后问题的所有解，并输出到文件。 “皇后放置模块”，在解决问题过程中，需要将“皇后”依次放置到第一、二、……、八行。该模块负责尝试在某一行放置一个“皇后”，放置成功返回一个“成功”值，说明当前皇后放置在某一个位置上可能存在“解”。否则失败的话，返回“失败”值，说明当前行无论怎样放置皇后，都得不到解，只有调整上面行的皇后的位置。 “输出模块”，负责将某一种皇后放置的方法写到文件中以供查看。 三、概要设计 主类成员变量及函数原型声明： class Queen { private: int location[9]; //location[i]（i大于，小于等于）表示在（i，location(i)）的位置放置了一个“皇后” bool LR[16]; //LR[i]（i大于，小于等于）从左上角往右下角数第i条斜线上是否有皇后，true为真 int lr_orgin[16]; //lr_origin用以记录左上角往右下角数第i条斜线被哪一行的皇后占用，未被占用为0 bool RL[16]; //RL[i]（i大于，小于等于）从右上角往左下角数第i条斜线上是否有皇后，true为真 int rl_orgin[16]; //rl_origin用以记录从右上角往左下角数第i条斜线被哪一行的皇后占用，未被占用为0 bool line[9]; //line[i]（i大于，小于等于8）表示在第i列上是否有皇后，true为真 int line_orgin[9]; //line[i]（i大于，小于等于8）表示在第i列上被哪一行的皇后占用，未被占用为0 int num; //用以统计解的个数 public: Queen(); //构造函数实现数据的初始化 bool mytry(int i); //测试第i行皇后的位置，成功返回true，失败返回false； int SolveProblem(); //八皇后问题的解决 void Result(); //输出结果，*8的样式显示，在皇后安放处显示一个Q }; 成员变量设计： 数组location[9]用来记录一至八行各个皇后所在列的序号（location[0]不使用）。LR[16]负责记录从左上角往右下角数，一至十六条斜线是否被占用（即实现皇后间的相互影响）。由于回溯时需要消除已经放置的部分皇后产生的影响（即改变LR[16]数组的值），所以必须记录某一个值的改变是有哪一行的皇后引起的，否则无法知道哪些影响是该消除的，所以需要设计一个数组lr_origin[16]，他的元素与LR[16]一一对应，每当某一条斜线被占用时，先将LR的某一元素的值改变，同时再在lr_origin中相应元素中记录下此改变是由某一行引起的。数组RL[16]、rl_origin[16]道理相同，只不过是记录从右上角至左下角第i条斜线的使用情况。此外，某一列是否被占用，被哪一行的皇后占用，也需要记录下来，所以设计bool数组line[9]，和int型l数组ine_origin[9]。有了这些，就可以记录某一皇后放置的位置，及产生的影响，同时也可以在需要的时候将相应的影响消除，便于重新放置皇后。 成员函数设计： 类的构造函数，实现数据的初始化。一个函数负责调用其他函数解决八皇后问题。由于八皇后问题需要不断尝试在某一行放置一个皇后，所以将这一动