《算法三部曲》之 搜索算法（上篇）
本帖最后由 Knuth学徒 于 2011-2-10 20:55 编辑Content目录：
搜索算法（中篇）：https://www.chinapyg.com/viewthread.php?tid=61783
搜索算法（下篇）：https://www.chinapyg.com/viewthread.php?tid=61831&extra=page%3D1
在介绍搜索之前，我先引入一个例子，看看可以用什么办法解决它。
N皇后问题：
在 N*N 的国际棋盘上放入N个皇后，使得这N个皇后互相不攻击，其中皇后的攻击范围是：同行、同列、同对角线。 问:一共有多少种放法？
这个题目是IT公司面试题的经典题目，虽然现在这题出现的少，但是在以前是一个程序员必定要会的。
要做这个题目，需要解释一下搜索的本质：对于一些问题，无法直接通过数学的计算算出结果，需要进行逐步试探，在试探的过程中得到解。
而如果我们亲自去逐步试探可能会因为问题规模过大而无法进行，这时候就可以利用计算机的高效的运算速度来进行搜索。
搜索一般分为 深度优先搜索——Depth_First_Search，一下简称 DFS， 和 广度优先搜索——Breadth_First_Search,一下简称 BFS,这两种搜索的方法原理不一样，过程也不一样，但是它们都可以遍历整个解空间，所以我们可以在不同的问题中选取不同的搜索方法。
回到 N 皇后的问题，这个问题无法用数学公式直接计算出来，但是我们可以通过计算机逐步试探皇后的位置来得到解。
根据皇后攻击的定义，可以知道—— 在每行、每列、每个对角线上最多只能有 1 个皇后，那么我们“人脑”是这样想的：
先在第一行的第一列位置先放一个皇后，然后再考虑第二行，第二行的第一个合法位置是第三列，于是把第二个皇后放在第三列。 然后在考虑第三行，第三行的第一个合法位置是第四列。。。。以此试探下去。
于是，可以把上面的过程抽象成一棵搜索树：树的根节点就是"没放任何皇后",那么树的第一层的子节点就是在第一行的合法位置放入一个皇后，于是 第一层 的第1个子节点代表 “在第一行的第 1个合法位置放入皇后”，第二层 的第 3个 子节点代表"在第二行 的 第三个合法位置放入一个皇后"…… 归纳一下：第 m 层的 第 n 个子节点代表 “在第m行的第n个合法位置放入一个皇后”。
现在我们搜索树的模型已经建立好了，那么这里采用 DFS 还是 BFS呢？取决于这两种搜索算法的区别：
深度优先搜索：在一棵搜索树中，采用 先序遍历 的方法遍历整棵树
广度优先搜索：在一棵搜索树中，采用 层次遍历 的方法遍历整棵树
我们仔细体味一下 “人脑” 的思维过程，在放好一个皇后之后，我们考虑的是下一行的皇后再放一个，然后再考虑下下一行……如果对于树的4种遍历方式很熟悉的朋友，应该很快就能想到 这就是 先序遍历，于是自然而然的采用 深度优先搜索即 DFS，在找到一个结果后，用一个计数器累加，直到所有的情况都搜索完了再返回计数器的值。
实现代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#defineN8 //先定义棋盘的大小，当然可以用键盘输入来定义，这里先用8来做例子
intmap = {0}; // 这个二维数组 用来表示当前的位置是否合法，合法为0,不合法非0
intcount (0) ; // 计数器
void change(int x, int y , bool flag )//在第x行,第y列放/拿皇后,更新map数组的值
{
if(flag){ //拿掉皇后
for(int i = x ; i < N ;++i)
if(map == x + 1) map = 0; //列
for(int j = y - 1 ; j >= 0 && (x-j+y < N) ; --j)
if(map == x+1) map[ x - j + y ] = 0; //左下
for(int k= y+1 ;k < N && (x+k-y < N); ++k)
if( map == x+1) map = 0;//右下
}
else //放皇后
{
for(int i = x ; i < N ;++i)
if(map == 0) map = x+1; //列
for(int j = y - 1 ; j >= 0 && (x-j+y < N) ; --j)
if(map == 0) map[ x - j + y ] = x+1;//左下
for(int k= y+1 ;k < N && (x+k-y < N); ++k)
if( map == 0) map = x+1;//右下
}
}
void Depth_First_Search(int line) //深度优先搜索函数，递归实现
{
if( line == N + 1 ) { count ++; return;}//如果已经放入了N个皇后,计数器+1,继续搜索
for(int i = 0; i< N ; ++i ) //对每列进行试探
{
if( map == 0) //如果当前列合法
{
change ( line - 1 , i, false ) ; // 在这个位置放皇后
Depth_First_Search ( line + 1); //递归试探下一行
change ( line - 1 , i, true ) ; //在这个位置拿掉皇后
}
}
}
int main()
{
count = 0; //计数器归零
Depth_First_Search(1);//从第一行开始搜索
printf("%d\n", count);
system("pause");
return 0;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
我用了深度优先搜索的方法解决了N皇后问题的方案数，但是我没有进行优化剪枝。
在搜索算法（中） 我会讨论 另一个经典的搜索问题——迷宫问题，这个问题有两种问法，比如输出从入口走到终点的路径，或者是求从入口走到终点的需要的最短步数。
这两个问题要用不同的搜索方法，前者用 DFS ，后者用 BFS，然后还有 深搜和广搜结合的方法，可以 输出 最短路线，这点在 （上）就不深入探讨了。
第一部曲——搜索算法的三分之一 就到此为止了.
转载请注明出处作者，谢谢
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 自己先顶一个。。。
这个帖子花了我很多精力 虽然N皇后现在面试题不多了，但是下一节要讲的 迷宫问题 是经常被问道的，我会尽力写好。 支持，C还在初学阶段，预留一下 /:L学到C++的路还长着呢。。 回复 5# Ever.G
一起学习，一起努力！ 回复 7# wlm2421331
C语言固然强大，配上 优秀的算法，将会使程序变得高效，健壮 这个要好好学习一下 回复 9# consult1026913
谢谢关注哈，中篇已经写完了。