南邮算法分析与设计实验3 回溯法

       学习编程实现深度优先搜索状态空间树求解实际问题的方法。着重体会求解第一个可行解和求解全部可行解之间的区别。

加深理解回溯法通过搜索状态空间树、同一时候用约束函数剪去不含答案状态子树的算法思想，会用蒙特卡罗方法预计算法实际生成的状态空间树的结点数。

                             

实验内容：

1、求24点问题

给定四个1-9之间的自然数，当中每一个数字仅仅能使用一次。用算术运算符＋。－，＊。／构造出一个表达式，将这4个正整数连接起来（能够使用括号），使终于的得数为24。要求依据问题的特征设计详细算法并编程实现，输入数据为4个自然数。

输出若有多个满足要求的表达式，则仅仅输出当中一组；若搜索失败。则输出“Fail!”。

【演示样例】採用一个表达式中用括号确定运算先后次序的方式，如：

输入1。5。5，5四个自然数，输出((5-(1/5))*5)。

输入3。3，8，8四个自然数。输出(8/(3-(8/3)))。

【測试数据】

(1) 1,5,5,5

(2) 3,3,8,8

(3) 3,8,8,8

(4) 1,2,3,4

(5) 2,4,5,6

(6) 4,2,2,5

(7) 1,2,2,6

(8) 4,2,8,8

(9) 0,3,8,8 

 2、n皇后问题

要求用回溯法求解8-皇后问题，使放置在8*8棋盘上的8个皇后彼此不受攻击。即：不论什么两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的全部可行解。

问题1：通过24点问题，体会用递归程序实现深度优先搜索的技巧。

因为回溯法通过搜索状态空间树求解，因此对输入的自然数与运算符（＋。－，*，/）全部可能的组合均需进行检查。每一个表达式中包含4个自然数和3个运算符，怎样决定运算的先后顺序？ 

假设每次先从4个数中取出两个数进行运算，然后把运算结果和第三个数进行运算。再把结果与第四个数进行运算。就能够轻易地决定这些数的运算次序，避免了对括号的处理。而且这样做。输出时非常easy通过为表达式逐层加上3层括号。唯一的确定终于结果表达式。

递归函数voidDFS(n)负责寻找可行解，当中n为本层调用的操作数个数。

每次两数运算后。原来的两个操作数被去除。运算结果成为新的操作数。因此总的操作数数量减1。

由于＋和*满足交换率。而－和/不满足，因此程序中应当计算a+b。a*b，a-b。b-a，a/b，b/a几种情况。

因为此程序仅仅要求第一个可行解，因此求得第一个可行解后，即能够层层返回并输出结果，同一时候结束程序。

（也能够借助一个标识符found来标识是否已找到第一个可行解）

当递归调用至n==1仅仅剩一个操作数时。推断该操作数是否等于24。假设是，则搜索成功,输出表达式；否则，则程序自己主动回溯至上层。若DFS()函数调用完成后，仍没有满足要求的的表达式，则输出“Fail.”搜索失败。

用全局数组num[]来存放操作数。递归调用时在下一层递归调用前改变，在下一层递归调用返回后恢复。

详细处理过程：每次从当前num[]数组中的n个数中。选择两个数进行一次运算。将这两个数从数组中去除，同一时候使用局部变量c1, c2暂存它们的值。而将它们的运算结果写入到数组中。

接着对当前num[]数组中剩余的n-1个数进行下一层递归调用，在递归调用返回到本层调用点后。再用局部变量c1, c2 恢复整个数组到调用前的初始状态。

实验代码：

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <string> using namespace std; double EPS = 1e-10; double num[4]; bool flag; int cnt; string re[4]; bool equel(double a, double b) { if(fabs(a - b) <= EPS) return true; return false; } void DFS(int n) { if(n == 1 && equel(num[0], 24)) { cnt ++; cout << re[0] << endl; exit(0); } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { double c1 = num[i], c2 = num[j]; string re1, re2; num[j] = num[n - 1]; num[i] = c1 + c2; re1 = re[i]; re2 = re[j]; re[j] = re[n - 1]; re[i] = \'(\' + re1 + \'+\' + re2 + \')\'; DFS(n - 1); num[i] = c1 - c2; re[i] = \'(\' + re1 + \'-\' + re2 + \')\'; DFS(n - 1); num[i] = c2 - c1; re[i] = \'(\' + re2 + \'-\' + re1 + \')\'; DFS(n - 1); num[i] = c1 * c2; re[i] = \'(\' + re1 + \'*\' + re2 + \')\'; DFS(n - 1); if(!equel(c2, 0)) //judge denominator { num[i] = c1 / c2; re[i] = \'(\' + re1 + \'/\' + re2 + \')\'; DFS(n - 1); } if(!equel(c1, 0)) { num[i] = c2 / c1; re[i] = \'(\' + re2 + \'/\' + re1 + \')\'; DFS(n - 1); } num[i] = c1; num[j] = c2; re[i] = re1; re[j] = re2; } } } int main() { //consider the rational numbers, we define them as double scanf("%lf %lf %lf %lf", &num[0], &num[1], &num[2], &num[3]); re[0] = num[0] + \'0\'; re[1] = num[1] + \'0\'; re[2] = num[2] + \'0\'; re[3] = num[3] + \'0\'; cnt = 0; DFS(4); if(cnt == 0) printf("Fail!\n"); return 0; }

測试数据：

(1) 1,5,5,5     ((5-(1/5))*5)

(2) 3,3,8,8     (8/(3-(8/3)))

(3) 3,8,8,8     (((3+8)-8)*8)

(4) 1,2,3,4     (((1+2)+3)*4)

(5) 2,4,5,6     (((2+4)*5)-6)

(6) 4,2,2,5     ((4*2)*(5-2))

(7) 1,2,2,6     ((1+2)*(6+2))

(8) 4,2,8,8     (((4-2)*8)+8)

(9) 0,3,8,8     (((0*8)+3)*8)