《搜索与应用——向期中》由会员分享，可在线阅读，更多相关《搜索与应用——向期中（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)以及深度dep，即从初始状态到达这个状态的最少步数。,分析,因为
4、新产生的结点深度（也即从初始布局到该结点的步数）一般要比数据库原有结点大（或相等），按步数大的后扩展的要求，应该放在数据库的后面。而当前扩展的结点从数据库前面选取，即符合先产生的先扩展，后产生的后扩展规律。所以数据库的结构用队列的结构形式较合适。用上述记录为元素的数组data来表示数据库，并设置两个指针：closed为队列的首指针，open为队列的尾指针。,分析,产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看作空格向四周移动。这样处理更便于编程。如果空格位置在（si，sj），则有四条规则： （1）空格向上移动。 If si-1=1 then ch(si,sj)：
5、=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=3 then ch(si,sj)：=ch(si-1,sj); ch(si,sj+1):=0 用数组DI和HJ来表示移动的行列增量，则有： R 1 2 3 4 方向 左 上 右 下 DI 0 -1 0 1 HJ -1 0 1 0,程序实现（伪代码）,Program num8; 初始化；把初始布局存入数据库data； 设首指针closed：=0； 尾指针open：=1； Re
6、peat Closed增1，取出队列首记录为当前被扩展结点； For r：=1 to 4 do r是规则编号 Begin If 新空格位置合法 then Begin Open增1，并把新布局存入队尾； If 新布局与队列中原有记录重复 then 删除新产生的布局 Else if 达到目标 then 输出并退出； End； End； Until closed=open； 队列空 具体程序实现参照ppt附带的num8.pas,总结与拓展,从上例可以看出，广度优先搜索法可以求出步数最少的解，即深度最少的解。 与深度优先搜索类似，不同的问题，用广度优先搜索的基本算法是一样的，但在数据库的表示方法、产生
7、的结点是否符合条件和重复的判断上可以有不同的编程技巧，程序的运行效率也有所不同。以八数码问题为例，上面的程序中用3*3的二维数组表示布局比较直观，但在判断重复，判断是否达到目标方面，却给程序增加了复杂性，也影响了运行速度。可以改用字符串形式来表示布局，第13个数表示第一行的三个数，第46个数，表示第二行的三个数，第79个数表示第三行的三个数。例如初始布局表示为“123456780”，目标布局表示为“012563478”。,产生规则也必须作相应改动。设空格当前位置是SI，则有： （1）空格向上移动：空格的位置减3，即交换SI和SI-3的字符； （2）空格向左移动：空格的位置减1，即交换SI和SI
8、-1的字符； （3）空格向右移动：空格的位置加1，即交换SI和SI+1的字符； （4）空格向下移动：空格的位置加3，即交换SI和SI+3的字符。 如设规则编号为k，则上述四条规则可归纳为一条： 交换SI和SI+（2*k-5）的字符 布局用字符串表示，使得判断重复过程和判断目标的过程变得很简单，只需判断两个字符串是否相等就可以了。按照上述的改进，读者可自己编制的解八数码问题的程序。,总结与拓展,一般广度优先搜索的基本框架,根据八数码问题的基本框架，与一般广度优先搜索的基本思想，我们可以得到如下一般广度优先搜索的基本框架。 Program BFS; 初始化；建立数据库data；初始状态存入数据库d
9、ata； 设队列首指针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个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止
10、。编程让计算机找出步数最少的翻法并把翻币过程及次数打印出来（用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个正面朝上的硬币翻过来就达
11、到了目标。因此在搜索过程中只需考虑当前状态正面朝上的个数。,分析,又如，如果当前状态是：* * * 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个硬币正面朝上，再翻一次就都可以达到目标。所以产生规则也只需考虑翻正面朝上的硬币的个数不同就可以了。,分析,建立产生式系统。其中：综合数据库。综合数据库中每个记录设计为三项：当前状态中硬币正面朝上的个数，父结点位置，由父结点翻了几个正面朝上的硬币得到当
12、前状态。数据库本身用队列形式。 产生规则有六条，即翻R(0=R=5)个正面朝上的硬币： if 当前结点正面朝上的硬币个数MR且反面朝上的个数5-R then 子结点data=（M-R）+（5-R） R=0，1，2，5 搜索策略。采用广度优先搜索法求解。 具体程序见目录下coin.pas,例题三,有两个无刻度标志的水壶，分别可装x升和y升（x、y为整数，x、y=100）的水，设另有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。 已知x升壶为满壶，y升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在y升壶中量出z(=100)升的水来。,例题三,例如，X=5，Y=6，Z=3时，有如
13、下方案： setp 0: x=5 y=0 setp 1: x=0 y=5 setp 2: x=5 y=5 setp 3: x=4 y=6 setp 4: x=4 y=0 setp 5: x=0 y=4 setp 6: x=5 y=4 setp 7: x=3 y=6 setp 8: x=3 y=0 setp 9: x=0 y=3,分析,本题要求最少步数，显然应采用广度优先搜索。设A水壶内有a升水，B水壶内有b升水，则最多会有六种产生规则： （1）当a0且b0且ax时，可以从水壶B倒MIN(b,x-a)升水给水壶A。这时水壶A内有a+MIN(b,x-a)升水；水壶B内有b+MIN(b,x-a)升水
14、；,A水壶 B水壶,A水壶 B水壶,A水壶 B水壶,分析,(3)当a0时,可以从水壶A倒a升水给水缸,这时水壶A内有0升水.水壶B内有b升水； (4)当ax时,可以从水缸倒x-a升水给水壶A；这时水壶A内有x升水，水壶B内有b升水；,分析,（5）当b0时,可以从水壶B倒b升水给水缸，这时水壶A内有a升水；水壶B内有0升水 （6）当by时,可以从水缸倒y-b升水给水壶B，这时水壶A内有a升水水壶B内有y升水,分析,初始时，水壶A内有x升水，水壶B内有0升水。 综合数据库： 可用一个记录类型描述一个状态： atype=record father，a，b：word； end； father记录当前节
15、点的父亲节点的编号，a、b表示当前状态中，水壶A和水壶B里各有多少水。 整个数据库可用一个以为数组DATA110000 of atype;另外用一个标志数组bool，当boolI，j为真，表示水壶A为I升，水壶B为j升的状态还没有产生过，反之则表示已产生过。使用广度优先搜索求解即可。 源程序见目录下battle.pas,例题四,黑白棋游戏的棋盘由44方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互
16、换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。,分析,首先分析状态量，16个格子，每个格子可以是黑或者白，所以状态不超过216，这个状态量是很小的，完全可以进行广搜。 状态：一个4*4的棋盘 决策：将任何2个相邻方格中棋子互换位置,分析,那么广搜的判重就可以用hash表来解决 把16个格子的黑白棋看成是一个二进制数，那么一个状态就对应一个数，这是最简单的hash函数 通过这样的hash函数，hash是可以不用挂链的,例题五,分析,看到这一问题，首先想到的自然是广度优先搜索。但是搜索中必然会出现许多重复，大大的增加了时空复杂度，比如连用两次规则A显然是浪费的，因此需要判重。如果是用传统的比较方法来排除重复的话，无疑将花去很多的时间，事实上也的确如此。 因为，我们需要找到一种更为便捷的方法，来进行判重。,受多维数组元素地址的
