ACM专题——搜索算法

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

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 1 ACM专题搜索算法 1.搜索问题 由此，可以看出这类问 题的解，就是一个合法状态 的序列，其中序列中第一个 状态是问题的初始状态，而 最后一个状态则是问题的结 束状态。如图所示即搜索问 题的示意图： Sg S0 解路径解路径 搜索空间搜索

3、空间 全状态空间全状态空间 ACM专题搜索算法 2.搜索方法分类 不可撤回方法不可撤回方法 试探性方法试探性方法 回溯方法回溯方法 图搜索方法图搜索方法 ACM专题搜索算法 3. 回溯方法 回溯方法，属于盲目搜索的一种，它是这样一种策略： 首先将规则给出一个固定的排序，在搜索时，对当前状态依 次检测每一条规则，在当前状态未使用过的规则中找到第一 条可应用规则，应用于当前状态，得到的新状态重新设置为 当前状态，并重复以上搜索。如果当前状态无规则可用，或 者所有规则已经被试探过仍未找到问题的解，则将当前状态 的前一个状态（即直接生成该状态的状态）设置为当前状态。 重复以上搜索，直到找到问题的解，或

4、已试探过所有可能仍 找不到问题的解为止。 ACM专题搜索算法 3. 回溯方法 对于用回溯法求解的问题，首先要将问题进行适当 的转化，得出状态空间树。 这棵树的每条完整路径都代 表了一种解的可能。通过深度优先搜索这棵树，枚举每 种可能的解的情况；从而得出结果。但是，回溯法中通 过构造约束函数，可以大大 提升程序效率，因为在深度 优先搜索的过程中，不断的将每个解（并不一定是完整 的，事实上这也就是构造约束函数的意义所在）与约束 函数进行对照从而删除一些 不可能的解，这样就不必继 续把解的剩余部分列出从而节省部分时间。 ACM专题搜索算法 3. 回溯方法 回溯法中，首先需要明确下面三个概念： （一）

5、约束函数：约束函数是根据题意定出的。通过描述合法解的一般特 征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。 因此，约束函数是对于任何状态空间树上的节点都有效、等价的。 （二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描 述。树上的每个子节点的解都只有一个部分与父节点不同。 （三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它 的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过 与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点； 死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意 义）。 ACM专题搜索算法 3. 回

6、溯方法 深度优先搜索（DFS）和广度优先搜索（FIFO） 在分支界限法中，一般用的是FIFO或最小耗费搜索； 其思想是一次性将一个节点的所有子节点求出并将其放入 一个待求子节点的队列。通过遍历这个队列（队列在 遍历 过程中不断增长）完成搜索。而DFS的作法则是将每一条合 法路径求出后再转而向上求第二条合法路径。而在回溯法 中，一般都用DFS。为什么呢？这是因 为可以通过约束函 数杀死一些节点从而节省时间，由于DFS是将路径逐一求出 的，通过在求路径的过程中杀死节点即可省去求所有子节 点所花费的时间。FIFO 理论上也是可以做到这样的，但是 通过对比不难发现，DFS在以这种方法解决问题时思路要清

7、 晰非常多。 因此，回溯法可以被认为是一个有过剪枝的DFS过程。 ACM专题搜索算法 3. 回溯方法 利用回溯法解题的具体步骤 首先，要通过读题完成下面三个步骤： (1)描述解的形式，定义一个解空间，它包含问题的所有解。 (2)构造状态空间树。 (3)构造约束函数（用于杀死节点）。 ACM专题搜索算法 3. 回溯方法 然后就要通过DFS思想完成回溯，完整过程如下： (1)设置初始化的方案（给变量赋初值，读入已知数据等）。 (2)变换方式去试探，若全部试完则转(7)。 (3)判断此法是否成功（通过约束函数），不成功则转(2)。 (4)试探成功则前进一步再试探。 (5)正确方案还未找到则转(2)。

8、 (6)已找到一种方案则记录并打印。 (7)退回一步（回溯），若未退到头则转(2)。 (8)已退到头则结束或打印无解。 ACM专题搜索算法 修道士和野人问题编程实现 过河问题的求解：三个修道士和三个野人过河， 船一次最多只能载两个人，在任何时候修道士的人 数不能少于野人人数，否则野人会吃掉修道士。找 出六个人顺利过河的所有方案。 ACM专题搜索算法 整体思想 采用四元组（修道士人数03，会划船野人数02，不会 划船野人数0/1，船所在岸0/1）描述结点状态，开始 状态为（3，2，1，0），目标状态为（0，0，0，1）。采 用带回溯的深度优先搜索策略，共定义了7种合法操作 2,0,0,1,0,0

9、,1,1,0,0,1,0,0,2,0,0,1,1,1,0,1代 表上船的人数，根据船所在位置决定在状态上是加或者减 操作。扩展结点时按顺序应用操作，直到回溯到初始状态 且所有操作用完，程序结束。 ACM专题搜索算法 类设计 state类：描述状态结点，包括描述状态的相关成 员变量和操作变量的成员函数 river类：描述和解决过河问题 ACM专题搜索算法 【算法和数据结构】 1算法 采用带回溯的深度优先策略。 在每个合法结点上应用所有7种操作，生成所有结点，然后判 断结点的合法与否，确定是否回溯。每找到一种方法只要没有生成 所有结点则回溯继续搜索。直到回溯到初始结点并且初始结点的所 有操作已经应

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

11、法 ( )( ) ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) Q Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) Q Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q Q Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,

12、1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) Q Q ACM专题搜索算法 3. 回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1)