文档介绍：ACM专题 ——搜索算法
搜索算法
1. 搜索问题
2. 搜索方法分类
3. 回溯方法
4. 一般图搜索算法
5. 启发式搜索算法
人类的思维过程，可以看作一个搜索过程。我们遇到的很多智
(7)退回一步（回溯），若未退到头则转(2)。
 
(8)已退到头则结束或打印无解。
修道士和野人问题编程实现
过河问题的求解：三个修道士和三个野人过河，船一次最多只能载两个人，在任何时候修道士的人数不能少于野人人数，否则野人会吃掉修道士。找出六个人顺利过河的所有方案。
整体思想
采用四元组（修道士人数[0~3]，会划船野人数[0~2]，不会划船野人数[0/1]，船所在岸[0/1]）描述结点状态，开始状态为（3，2，1，0），目标状态为（0，0，0，1）。采用带回溯的深度优先搜索策略，共定义了7种合法操作{2,0,0},{1,0,0},{1,1,0},{0,1,0},{0,2,0},{0,1,1},{1,0,1}代表上船的人数，根据船所在位置决定在状态上是加或者减操作。扩展结点时按顺序应用操作，直到回溯到初始状态且所有操作用完，程序结束。
类设计
state类：描述状态结点，包括描述状态的相关成员变量和操作变量的成员函数
river类：描述和解决过河问题
【算法和数据结构】
1．算法
采用带回溯的深度优先策略。
在每个合法结点上应用所有7种操作，生成所有结点，然后判断结点的合法与否，确定是否回溯。每找到一种方法只要没有生成所有结点则回溯继续搜索。直到回溯到初始结点并且初始结点的所有操作已经应用完毕，则整个搜索过程结束。
采用链表结构，结点是生成的状态，当前结点在链表头。结点中包含状态信息和程序需要的相关控制信息。新扩展生成的结点放在链表头，回溯时删除头结点并移动头指针。当找到一种过河方案时，当前链表中的所有结点就是按顺序生成的状态结点，只要遍历链表输出状态就可以得到该种方法经过的状态和所用的操作。
N皇后问题
问题描述：
在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。
3. 回溯方法
例：皇后问题
Q
Q
Q
Q
3. 回溯方法
( )
( )
3. 回溯方法
( )
( )
((1,1))
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
Q
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
Q
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
Q
Q
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
Q
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
((1,2))
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
((1,2))
((1,2) (2,4))
Q
Q
3. 回溯方法
( )
( )
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) ())
((1,2))
((1,2) (2,4))