《优先搜索应用》由会员分享，可在线阅读，更多相关《优先搜索应用（111页珍藏版）》请在金锄头文库上搜索。
1、万能的解题金钥匙搜索 基础概念 在我们遇到的一些问题当中，有些问题不能够确切 的建立数学模型，或即便有数学模型但该模型的准 确方法也不一定能运用现成算法。在要求枚举方案 时，常常会遇到这一类问题。 解决这一类问题，我们一般采用搜索的方法解决， 即从初始状态出发，运用题目所给出的条件和规则 扩展所有可能情况，从中找出满足题意要求的解答 。 状态：指当前所面临的具体问题 转移：指从一个状态到另一状态的一种决策 状态和转移可能是题目中已经给出，也可能是需要 自己分析出的。一道题的状态与决策可能有多种。 产生式系统：把状态通过转移得到的一颗状态树， 称作产生式系统 广度优先搜索 在搜索算法中，我们对每
2、个节点进行拓展 ，深度越小的结点越先得到扩展，就是广 度优先搜索法，下面通过一个具体实例来 讨论广度优先算法的一般规律。 例题一 八数码难题：在33的棋盘上，摆有八个棋子，每个棋子上标 有1至8的某一数字。棋盘中留有一个空格（空格用0表示）。 空格周围的棋子可以移到空格中。要求解的问题是：给出一种 初始布局（初始状态）和目标面局（目标状态），找到一种最 少步骤的移动方法，实现从初始布局到目标布局的转变。 以上图为例，从初始状态到目标状态的最少步数方案如下： 将8移到空位，将7移到空位，将4移到空位，将5移到空位，将 6移到空位，将3移到空位，将2移到空位，将1移到空位。 初始状态目标状态 分析
3、 由于题目要找到的解是达到目标最少步骤，因 此解题的方法为：从初始状态出发，先把移动 一步后的布局全部找到，检查是否达到目标布 局，如果没有，再从这些移动一步的布局出发 ，找到移动两步后的所有布局，再判断是否有 达到目标的，如此继续，一直达到目标状态为 止，输出结果。 由于是按移动步数从少到多产生新布局的，所 以找到的第一个目标一定是移动步数最少的一 个，也就是最优解。 分析 具体实现使用产生式系统： 那么对于当前的一个状态，我们记录如下 信息：一个3*3的矩阵ch用于表示矩阵的布 局，其中chi,j表示第i行，第j列所放的数 字；为了方便程序编写，我们记录空格的 位置(si, sj)以及深度
4、dep，即从初始状态到 达这个状态的最少步数。 分析 因为新产生的结点深度（也即从初始布局 到该结点的步数）一般要比数据库原有结 点大（或相等），按步数大的后扩展的要 求，应该放在数据库的后面。而当前扩展 的结点从数据库前面选取，即符合先产生 的先扩展，后产生的后扩展规律。所以数 据库的结构用队列的结构形式较合适。用 上述记录为元素的数组data来表示数据库， 并设置两个指针：closed为队列的首指针， open为队列的尾指针。 分析 产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一 种角度观察，也可看作空格向四周移动。这样处理更便于编程。如果 空格位置在（si，sj），则有四条
5、规则： （1）空格向上移动。 If si-1=1 then ch(si,sj)：=ch(si-1,sj); ch(si-1,sj):=0 （2）空格向下移动。 If si+1=1 then ch(si,sj)：=ch(si,sj-1); ch(si,sj-1):=0 （4）空格向右移动。 If sj+1=open； 队列空 具体程序实现参照ppt附带的num8.pas 总结与拓展 从上例可以看出，广度优先搜索法可以求出步数最少的解， 即深度最少的解。 与深度优先搜索类似，不同的问题，用广度优先搜索的基本 算法是一样的，但在数据库的表示方法、产生的结点是否符 合条件和重复的判断上可以有不同的编程
6、技巧，程序的运行 效率也有所不同。以八数码问题为例，上面的程序中用3*3 的二维数组表示布局比较直观，但在判断重复，判断是否达 到目标方面，却给程序增加了复杂性，也影响了运行速度。 可以改用字符串形式来表示布局，第13个数表示第一行的 三个数，第46个数，表示第二行的三个数，第79个数表示 第三行的三个数。例如初始布局表示为“123456780”，目标 布局表示为“012563478”。 产生规则也必须作相应改动。设空格当前位置是SI，则有： （1）空格向上移动：空格的位置减3，即交换SI和SI-3的字符 ； （2）空格向左移动：空格的位置减1，即交换SI和SI-1的字符 ； （3）空格向右移
7、动：空格的位置加1，即交换SI和SI+1的字符 ； （4）空格向下移动：空格的位置加3，即交换SI和SI+3的字符 。 如设规则编号为k，则上述四条规则可归纳为一条： 交换SI和SI+（2*k-5）的字符 布局用字符串表示，使得判断重复过程和判断目标的过程变得 很简单，只需判断两个字符串是否相等就可以了。按照上述的 改进，读者可自己编制的解八数码问题的程序。 总结与拓展 一般广度优先搜索的基本框架 根据八数码问题的基本框架，与一般广度优先搜索的基本思想，我们可以 得到如下一般广度优先搜索的基本框架。 Program BFS; 初始化；建立数据库data；初始状态存入数据库data； 设队列首指
8、针closed：=0； 队列尾指针open：=1； Repeat Closed增1，取出closed所指结点进行扩展； For r：=1 to rmax do r为产生规则编号 Begin If 子结点符合条件 then Begin Open增1，并把新结点存入数据库队尾； If 新结点与原有结点重复 then 删去该结点（open减1 ） Else if 新结点即目标 then 输出并退出； End； End； Until closed=open； 队列空 例题二 翻币问题。有N个硬币（N6）正面朝上排成一排，每次 将5个硬币翻过来放在原位置，直到最后全部硬币翻成反 面朝上为止。编程让计算机
9、找出步数最少的翻法并把翻币 过程及次数打印出来（用O表示正面，*表示反面）。 例如N=6的情况： step 0: oooooo step 1: *o step 2: oooo* step 3: *ooo step 4: oo* step 5: *ooooo step 6: * 分析 由于问题要求找出最少步骤，用广度优先搜索法 来求解。表面看，翻币的过程与正反面硬币的排 列位置有关，但只要经过仔细分析会发现：实际 上翻币过程仅与硬币正反面的个数有关，与它们 的位置是无关的。例如下面两种状态： O * O * O * O O * * * O O O O O 都只要把5个正面朝上的硬币翻过来就达到了
10、目标 。因此在搜索过程中只需考虑当前状态正面朝上 的个数。 分析 又如，如果当前状态是：* * * O O * * * 翻第1，2，4，6，8个得到：O O * * O O * O 而翻第3，5，6，7，8个得到：* * O O * O O O 这两种翻法虽翻的硬币不同，但都是把原状态中4 个反面朝上1个正面朝上的硬币翻过来。结果状态 不同，但都有5个硬币正面朝上，再翻一次就都可 以达到目标。所以产生规则也只需考虑翻正面朝 上的硬币的个数不同就可以了。 分析 建立产生式系统。其中：综合数据库。综合数据库 中每个记录设计为三项：当前状态中硬币正面朝上 的个数，父结点位置，由父结点翻了几个正面朝上
11、 的硬币得到当前状态。数据库本身用队列形式。 产生规则有六条，即翻R(0timen，使得 处理机有序化，其中time1便是完成所有工作的时 间。 用贪心法可以得到time1的上限，并且我们可以计 算出time1的下限，然后搜索。 贪心求上限的方法无非是构造一组可行解，使得 time1尽量小。比如说我们依次扫描每一个物品， 在满足time1time2timen的条件下，往背 包内放，这样就可以构造出一组可行解出来，我们 就可以拿这时的time1作为上界了。 伪代码 Procedure dfs(i:integer); i表示当前搜索到了哪一个处理机 For i:=1 to m do if (not
12、 boi) and 该作业未被之前的处理机处理 (timei+tiHi+1。 条件3： 表面积Q最小，令Q= S 问题： 给出的n和m， 找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 (除Q外，以上所有数据皆为正整数) 输入 n (n Hi+1 （3） Vi+1 = Vi - Ri+1* Ri+1* Hi+1 （4） Si+1 = Si + 2 * Ri+1* Hi+1 确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件 1）是否做到了m层 2）是否最终体积为0 3）是否当前面积最小 若上述条件成立，则保留当前最优值，否则继续 做下一层蛋糕，若重做蛋糕
13、基本算法 Search (i, Ri , Hi , Si , Vi) 对每层蛋糕进行搜索 if (i=m) and (Vi =0) then 更新最优值 else for Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Problem-Cake 枚举所有的初始状态 - 第一层蛋糕的大小 for R1m to sqrt ( n ) do
14、/*假设 H1=1，只做一层蛋糕 */ for H1n div (R1*R1) downto m do S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) 优化？ （1）因为知道余下的蛋糕体积,因此可以估算一下余下侧面积, 这样我们可以就加入如下剪枝条件: if 当前的表面积 + 余下的側面积 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层, Si：为第i层蛋糕的侧面积, FSi：余下的侧面积,怎么求FSi ? 因为: 2Vi= 2Ri+1 * Ri+1 * Hi+1 + .+ 2Rm *
15、 Rm * Hm = Ri+1 * Si+1 + .+ Rm * Sm Ri+1 * (Si+1+ .+ Sm) = Ri+1 * FSi 所以: FSi 2Vi / Ri+1 因此剪枝条件为： if Si-1 + 2 * Vi-1 / Ri 当前最优值 then exit 优化？ (2)如果剩下的蛋糕材料太少，不能保证做到m层,那么没 有必要继续往下做了，设， 最m层半径和高都为1，Rm=Hm=1 第m-1层半径和高都为2，Rm-1=Hm-1=2 第 i +1层半径和高都为i, Ri = Hi = m i 这样， 余下的m-i层的最小体积为 因此,剪枝条件为, if Vi当前最优值 then exit; 剪枝1 if Vi =C. 若能推导出A=A （A,B为任何不相等 字母），则当前的枚举不可行。可用递归枚举，从 后向前枚举，处理一个竖列时则加上2个不等式， 看是否矛盾。数据结构用邻接矩阵。（规定A=B ，要加入所有x(x=A) =y(B=y)，枚举x,y用O(n2)得时间。再判断是 否有x=y. 传染病控制 (NOIP2003-4) 染病的传播具有两种很特殊的性质： 第一是它的传播途径是树型的，一个人X只可能被某个特定 的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断 ，则X就不会得病。第二是，这种疾病的传播有周期性，在一 个疾病传播周期之
