ACM培训第八讲-搜索

ACM程序设计

第八讲-搜索湖南工学院张新玉zhangxinyu247@163.com搜索算法1.搜索问题2.搜索方法分类3.回溯方法4.一般图搜索算法5.启发式搜索算法1.搜索问题人类的思维过程，可以看作一个搜索过程。我们遇到的很多智力游戏问题，如传教士和野人问题。有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可乘坐2个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在河的两岸以及船上传教士人数不能少于野人的人数？对这个问题，在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？这就是搜索问题。1.搜索问题对这类问题，一般我们都转换为状态空间的搜索问题。如传教士和野人问题，可用在河左岸的传教士人数、野人人数和船的情况来表示。即，初始时状态为（3，3，1），结束状态为（0，0，0），而中间状态可表示为（2，2，0）、（3，2，1）等等。

初始状态结束状态

LR

LRm30m03c30c03B10B011.搜索问题由此，可以看出这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图：SgS0解路径搜索空间全状态空间2.搜索方法分类

不可撤回方法试探性方法回溯方法图搜索方法3.回溯方法回溯方法，属于盲目搜索的一种，它是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或已试探过所有可能仍找不到问题的解为止。3.回溯方法例：皇后问题QQQQ3.回溯方法()()3.回溯方法()()((1,1))Q3.回溯方法()()((1,1))((1,1)(2,3))QQ3.回溯方法()()((1,1))((1,1)(2,3))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQ3.回溯方法()()((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))QQQ3.回溯方法()()((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,1)(4,3))QQQQ3.回溯方法递归的思想：当前状态目标状态g3.回溯方法算法描述：BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向）

返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。3.回溯方法1, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);3.回溯方法7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);4.一般图搜索算法问题的引入：回溯搜索：只保留从初始状态到当前状态的一条路径图搜索：保留所有已经搜索过的路径如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。4.一般图搜索算法问题的引入：回溯搜索：只保留从初始状态到当前状态的一条路径图搜索：保留所有已经搜索过的路径如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。4.一般图搜索算法一些基本概念：节点深度： 根节点深度=0

其它节点深度=父节点深度+101234.一般图搜索算法一些基本概念：路径:设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值:

一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点:

生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。4.一般图搜索算法一般性图搜索算法：1:G←S,OPEN←(S);建立一个搜索图G,它只含有初始节点S,建立一个OPEN表(今后它用于存储生成的节点),开始它只含有初始节点S。2:CLOSED←();建立一个CLOSED表(今后它用于存储已扩展节点或将要扩展的某个节点),它的初始状态为空表。3:LOOP:ifOPEN=()thenreturnFAIL;进入循环。如果OPEN表已空,说明没有节点可扩展,就返回FAIL,即失败。4:n←FIRST(OPEN),CLOSED←(n,CLOSED);从OPEN表中取出一个节点n,将其放入CLOSED表中。5:ifn∈目标集thenreturn[s→…→n];如果n为目标节点,则沿着G中从n到s的链指针得出一条路径,并以此返回。4.一般图搜索算法一般性图搜索算法(续)：6:M←expand(n),G'←G,G←{M,G'};扩展节点n,建立集合M,并把M中的节点作为n的后继者加入G中。7:

对M中的所有节点m(1)ifm

G'then建立指针m→n,OPEN←CONS(M,OPEN);对M中原来不在G中的节点建立一个从这些节点到n的指针,并把它们加入OPEN表。

(2)ifm∈OPENthen根据其扩展路径确定是否应将它们的指针指向n。

(3)ifm∈CLOSEDthen根据其扩展路径确定是否应改变m的后代的指针。8:

对OPEN中的节点按某种原则重新排序；9:GOLOOP；4.一般图搜索算法节点类型：…...…...…...…...…...mjmkml4.一般图搜索算法广度优先搜索法：该方法从初始节点开始,顺序扩展生成下一级各子节点,放在OPEN表中已有的节点后面(实现先生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法认为同一级各节点对问题求解的价值是同等的,因而对全部节点沿广度进行横向扫描,按各节点生成的先后次序,先生成、先检查、先扩展,沿广度遍历所有节点。这种方法只要问题有解,即若树图上存在目标节点,经搜索一定能找到。所以,广度优先搜索法是完备的,是一种推理算法。但是,在问题大节点多,且目标节点距离初始节点较远时将会产生许多无用节点,搜索效率低,还可能产生组合爆炸。因此,这种方法较适宜问题不大的环境中。4.一般图搜索算法广度优先搜索算法：1:G:=G0(G0=s),OPEN:=(s),CLOSED:=();2:LOOP:IFOPEN=()THENEXIT(FAIL);3:n:=FIRST(OPEN);4:IFGOAL(n)THENEXIT(SUCCESS);5:REMOVE(n,OPEN),ADD(n,CLOSED);6:EXPAND(n)→{mi},G:=ADD(mi,G);7:IF目标在{mi}中THENEXIT(SUCCESS);8:

ADD(OPEN,mj),

并标记mj到n的指针;9:GOLOOP;

4.一般图搜索算法例:8数码难题

在一个3×3的方框内放有8个编号的小方块，紧邻空位的小方块可以移入到空位上，通过平移小方块可将某一布局变换为另一布局。请给出从初始状态到目标状态移动小方块的操作序列。231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876544.一般图搜索算法广度优先搜索的性质：当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法4.一般图搜索算法深度优先搜索法：该方法从初始节点开始,顺序扩展生成下一级各子节点,放在OPEN表中已有的节点前面(实现后生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法每一次扩展最晚生成的子节点,沿着最晚生成的子节点分支,逐级纵向深入发展。这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上,则可较快地得到解。但是,如果目标节点不在此分支上,不回溯就不可能得到解。所以,深度优先搜索是不完备的,只是推理步骤。如果回溯,不难证明其平均效率与广度优先搜索法相同。因此,深度优先搜索法如果没有启发信息,很难有实用价值。4.一般图搜索算法深度优先搜索算法：1:G:=G0(G0=s),OPEN:=(s),CLOSED:=();2:LOOP:IFOPEN=()THENEXIT(FAIL);3:n:=FIRST(OPEN);4:IFGOAL(n)THENEXIT(SUCCESS);5:REMOVE(n,OPEN),ADD(n,CLOSED);6:IFDEPTH(n)≥DmGOLOOP;7:EXPAND(n)→{mi},G:=ADD(mi,G);8:IF目标在{mi}中THENEXIT(SUCCESS);9:

ADD(mj,OPEN),

并标记mj到n的指针;10:GOLOOP;231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标4.一般图搜索算法深度优先搜索的性质：一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法5.启发式搜索算法引入:利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。希望引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。5.启发式搜索算法基本思想:

定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的格式：

f(x)=g(x)+h(x)g*(x)：为从初始节点S。到节点x的最短路径的耗散值h*(x)：从x到目标节点Sg的最短路径的耗散值f*(x)=g*(x)+h*(x)：从S。经过x到Sg的最短路径的耗散值g(x)、h(x)、f(x)分别是g*(x)、h*(x)、f*(x)的估计值5.启发式搜索算法A算法:1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{Mi},

计算f(n,mi):=g(n,mi)+h(mi);5.启发式搜索算法A算法(续): ADD(mj,OPEN),标记mj到n的指针；

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

标记mk到n的指针；

IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),

标记ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；5.启发式搜索算法一个A算法的例子:定义评价函数：

f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值

h(n)为当前节点“不在位”的将牌数2831647512384765h计算举例 h(n)=42

831

6475123457682831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标1234563.4.3典型的启发式图搜索算法A*算法:如果对一般性图搜索算法作以下限制,则它成为A*算法:(1)OPEN表中的节点按估价函数f(x)=g(x)+h(x)的值从小至大进行排序.(2)g(x)是到目前为止,从S。到x的一条最小耗散值路径的耗散值,是作为从S。到x最小耗散值路径的耗散值g*(x)的估计值,g(x)>0。

(3)h(x)是h*(x)的下界,即对所有x均有h(x)≤h*(x)。而h*(x)是从节点x到目标节点的最小代价,若有多个目标节点,则为其中最小的一个。3.4.3典型的启发式图搜索算法A*条件举例:8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：2283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465s(5)A(7)B(5)C(7)D(7)E(5)F(7)G(5)H(7)I(5)J(5)K(7)目标12345h2(n)=将牌“不在位”的距离和搜索过程实验要求

编写一程序实现以A*算法搜索八数码难题的解决步骤：

在一个3×3的方框内放有8个编号的小方块，紧邻空位的小方块可以移入到空位上，通过平移小方块可将某一布局变换为另一布局（如图所示）。2831675412384765A*算法回顾启发函数:8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：2移动规则的表示规则集合:

移动一块将牌(即走一步)就使状态发生改变.有4种走法:空格上移、空格下移、空格左移、空格右移。规则集可形式化表示如下:

设Sij记矩阵第i行第j列的数码，i0,j0

记空格所在的行、列数值，即Si0j0=0，则

ifj0-1≥1thenSi0j0=Si0(j0-1),Si0(j0-1)=0(Si0j0向左）

ifi0-1≥1thenSi0j0=S(i0-1)j0,S(i0-1)j0=0(Si0j0向上）

ifj0+1≤3thenSi0j0=Si0(j0+1),Si0(j0+1)=0(Si0j0向右）

ifi0+1≤3thenSi0j0=S(i0+1)j0,S(i0+1)j0=0(Si0j0向下）节点的表示structnode{ intstate[3][3];//数码状态

structnode*parent;//指向父节点的指针

structnode*next;//指向下一节点的指针

intinherit;//启发函数值

intdepth;//搜索深度

intf_value;//评价函数值};程序设计细节程序会用到的全局变量structnode*close,*open,*goal;//分别指向close表、open表和目标节点的指针intend[3][3]={{1,2,3},{8,0,4},{7,6,5}};//用于比较的目标节点的数码状态intsucceed=0;//判断是否成功搜索到目标状态程序设计细节初始节点的创建structnode*p;inti,j,h;p=new(structnode);p->parent=NULL;p->next=NULL;p->depth=0;p->inherit=0;printf("请输入初始状态:\n");for(i=0;i<3;i++)for(j=0;j<3;j++){ scanf("%d",&h); p->state[i][j]=h;}h=heuristic(p);p->f_value=h;程序设计细节处理open=p;close=NULL;goal=NULL;

/*对OPEN表进行扩展*/expend();程序设计细节结果的输出if(succeed==0){printf("不能得到目标状态！\n");}else{p=goal;

i=0;while(p!=NULL){proc[i]=p->inherit;p=p->parent;i=i+1;}程序设计细节结果的输出(续）

printf("操作步骤如下所示：\n");for(j=i;j>=0;j--){h=proc[j];switch(h){case1:

printf("第%d步为:左移\n",i-j-1);break; case2:printf("第%d步为:上移\n",i-j-1);break; case3:

printf("第%d步为:右移\n",i-j-1);break; case4:printf(“第%d步为:下移\n”,i-j-1)；break;}}}启发函数的计算intheuristic(structnode*x){

/*计算启发函数*/

intvalue=0;intnum,loc,flag;

for(inti=0;i<3;i++)

for(intj=0;j<3;j++)

{

num=x->state[i][j]; flag=0;

for(intk=0;k<3;k++)

{

for(intl=0;l<3;l++) if(end[k][l]==num) {

loc=abs(i-k)+abs(j-l);value=value+loc;

flag=1;

break; } if(flag==1)break;

} }

returnvalue;}扩展过程voidexpend(){

/*从OPEN表中选取第一个结点进行扩展*/

introw,col,h;

structnode*p,*q;

while((open!=NULL)&&(succeed==0))

{

p=open;

open=open->next;

p->next=close;

close=p;

for(inti=0;i<3;i++)

for(intj=0;j<