算法与数据结构程序设计报告_b08030111

《算法与数据结构程序设计报告_b08030111》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯法应用一、课题内容和要求在人机对弈、决策问题、人工智能、组合数学等等一系列非数值问题的算法设计中，回溯法是经常采用的一种重要而有效的方法。回溯法是一种选优搜索法。按选择最优解的条件向前搜索，以达到目的。但每当搜索到某一步时，发现其达不到预期的效果，就退回一步重新选择。这种行不通就退回的技术称为回溯法。回溯法的逻辑思路可表示为一棵数，根节点是初始状态，没搜索到一个节点都有若干个可供选择的后续节点，没有任何能够达到目标的暗示，只有走着瞧，不行了就回溯到上一层节点，回复刚刚使用的参数，再走另一条路径，所以回溯法的本质

2、是穷举与试探，找到从根节点到叶子节点的所有正确结果。八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。二、需求分析运用面向对象思想，将八皇后问题的解决放在一个类中来解决。“构造函数模块”用来实现数据的初始化。“主程序模块”，负责调用其他函数依次在一到八行放置皇后，并按一定规律调整皇后位置，求出八皇后问题的所有解，并输出到文件。“皇后放置模块”

3、，在解决问题过程中，需要将“皇后”依次放置到第一、二、……、八行。该模块负责尝试在某一行放置一个“皇后”，放置成功返回一个“成功”值，说明当前皇后放置在某一个位置上可能存在“解”。否则失败的话，返回“失败”值，说明当前行无论怎样放置皇后，都得不到解，只有调整上面行的皇后的位置。“输出模块”，负责将某一种皇后放置的方法写到文件中以供查看。三、概要设计16输出模块：开始输出八行皇后的放置位置结束16Queen类中问题解决模块：开始标志位置为1标志位是否大于0能否在第“标志位行放置一个皇后”是返回解法数否结束此皇后是否位

4、于第8行输出一种解法标志位减1（继续寻找）是是标志位减一（退一行）否标志位加1（继续往下1行寻找）否16皇后放置模块：（负责在某一行放置皇后）开始消除当前行及下一行以前皇后位置的影响当前皇后是否在第8列否皇后位置变为当前位置加1是否超过第8列是返回“失败”结束是否与前面的皇后有冲突否是是记录该皇后位置，将相应列、斜线占用返回“成功”16主类成员变量及函数原型声明：classQueen{private:intlocation[9];//location[i]（i大于，小于等于）表示在（i，location(i)）的位

5、置放置了一个“皇后”boolLR[16];//LR[i]（i大于，小于等于）从左上角往右下角数第i条斜线上是否有皇后，true为真intlr_orgin[16];//lr_origin用以记录左上角往右下角数第i条斜线被哪一行的皇后占用，未被占用为0boolRL[16];//RL[i]（i大于，小于等于）从右上角往左下角数第i条斜线上是否有皇后，true为真intrl_orgin[16];//rl_origin用以记录从右上角往左下角数第i条斜线被哪一行的皇后占用，未被占用为0boolline[9];//line[

6、i]（i大于，小于等于8）表示在第i列上是否有皇后，true为真intline_orgin[9];//line[i]（i大于，小于等于8）表示在第i列上被哪一行的皇后占用，未被占用为0intnum;//用以统计解的个数public:Queen();//构造函数实现数据的初始化boolmytry(inti);//测试第i行皇后的位置，成功返回true，失败返回false；intSolveProblem();//八皇后问题的解决voidResult();//输出结果，*8的样式显示，在皇后安放处显示一个"Q"};成员变

7、量设计：数组location[9]用来记录一至八行各个皇后所在列的序号（location[0]不使用）。LR[16]负责记录从左上角往右下角数，一至十六条斜线是否被占用（即实现皇后间的相互影响）。由于回溯时需要消除已经放置的部分皇后产生的影响（即改变LR[16]数组的值），所以必须记录某一个值的改变是有哪一行的皇后引起的，否则无法知道哪些影响是该消除的，所以需要设计一个数组lr_origin[16]，他的元素与LR[16]一一对应，每当某一条斜线被占用时，先将LR的某一元素的值改变，同时再在lr_origin中相应

8、元素中记录下此改变是由某一行引起的。数组RL[16]、rl_origin[16]道理相同，只不过是记录从右上角至左下角第i条斜线的使用情况。此外，某一列是否被占用，被哪一行的皇后占用，也需要记录下来，所以设计bool数组line[9]，和int型l数组ine_origin[9]。有了这些，就可以记录某一皇后放置的位置，及产生的影响，同时也可以在需要的时候将相