ACM专题——搜索算法1

1、ACM专题讲座搜索算法 12搜索算法1. 搜索问题2. 搜索方法分类3. 回溯方法4. 一般图搜索算法 5. 启发式搜索算法31.搜索问题人类的思维过程，可以看作一个搜索过程。我们遇到的很多智力游戏问题，如传教士和野人问题。 有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可乘坐2个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在河的两岸以及船上传教士人数不能少于野人的人数？对这个问题，在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？ 这就是搜索问题。41.搜索问题对这类问题，一般我们都转换为状态空间的搜索问题。如传教士和野人问题，可用在河左岸的传教士

2、人数、野人人数和船的情况来表示。即，初始时状态为（3，3，1），结束状态为（0，0，0），而中间状态可表示为（2，2，0）、（3，2，1）等等。 初始状态 结束状态 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 151.搜索问题由此，可以看出这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图：SgS0解路径解路径搜索空间搜索空间全状态空间全状态空间62.搜索方法分类不可撤回方法不可撤回方法试探性方法试探性方法回溯方法回溯方法图搜索方法图搜索方法73. 回溯方法回溯方法，属

3、于盲目搜索的一种，它是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或已试探过所有可能仍找不到问题的解为止。83. 回溯方法 对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；

4、从而得出结果。但是，回溯法中通过构造约束函数，可以大大 提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。93. 回溯方法回溯法中，首先需要明确下面三个概念： （一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。 （二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有

5、一个部分与父节点不同。 （三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。103. 回溯方法深度优先搜索（DFS）和广度优先搜索（FIFO） 在分支界限法中，一般用的是FIFO或最小耗费搜索；其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列（队列在 遍历过程中不断增长）完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回

6、溯法中，一般都用DFS。为什么呢？这是因 为可以通过约束函数杀死一些节点从而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。FIFO 理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。 因此，回溯法可以被认为是一个有过剪枝的DFS过程。 113. 回溯方法利用回溯法解题的具体步骤 首先，要通过读题完成下面三个步骤： (1)描述解的形式，定义一个解空间，它包含问题的所有解。 (2)构造状态空间树。 (3)构造约束函数（用于杀死节点）。 123. 回溯方法然后就要通过DFS思想完成回溯，完整过程如下：

7、(1)设置初始化的方案（给变量赋初值，读入已知数据等）。 (2)变换方式去试探，若全部试完则转(7)。 (3)判断此法是否成功（通过约束函数），不成功则转(2)。 (4)试探成功则前进一步再试探。 (5)正确方案还未找到则转(2)。 (6)已找到一种方案则记录并打印。 (7)退回一步（回溯），若未退到头则转(2)。 (8)已退到头则结束或打印无解。13 修道士和野人问题编程实现 过河问题的求解：三个修道士和三个野人过河，船一次最多只能载两个人，在任何时候修道士的人数不能少于野人人数，否则野人会吃掉修道士。找出六个人顺利过河的所有方案。 14整体思想 采用四元组（修道士人数03，会划船野人数02

8、，不会划船野人数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代表上船的人数，根据船所在位置决定在状态上是加或者减操作。扩展结点时按顺序应用操作，直到回溯到初始状态且所有操作用完，程序结束。 15类设计 state类：描述状态结点，包括描述状态的相关成员变量和操作变量的成员函数 river类：描述和解决过河问题 16【算法和数据结构】 1算法 采用带回溯的深度优先策略。 在每个合法结点上应用所有7种操作，生成所有

9、结点，然后判断结点的合法与否，确定是否回溯。每找到一种方法只要没有生成所有结点则回溯继续搜索。直到回溯到初始结点并且初始结点的所有操作已经应用完毕，则整个搜索过程结束。 2.数据结构 采用链表结构，结点是生成的状态，当前结点在链表头。结点中包含状态信息和程序需要的相关控制信息。新扩展生成的结点放在链表头，回溯时删除头结点并移动头指针。当找到一种过河方案时，当前链表中的所有结点就是按顺序生成的状态结点，只要遍历链表输出状态就可以得到该种方法经过的状态和所用的操作。17N皇后问题 问题描述： 在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜

10、角线上。183. 回溯方法n例：皇后问题QQQQ193. 回溯方法( )( )203. 回溯方法( )( )(1,1)Q213. 回溯方法( )( )(1,1)(1,1) (2,3)QQ223. 回溯方法( )( )(1,1)(1,1) (2,3)Q233. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)QQ243. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)QQQ253. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)QQ263. 回溯方

11、法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q273. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)283. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)Q293. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)QQ303. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)QQQ313. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)(1,2) (2,4) (3,