参考盲目搜索策略及其在实际中的应用研究.docx
- 文档编号:13804795
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:17
- 大小:358.66KB
参考盲目搜索策略及其在实际中的应用研究.docx
《参考盲目搜索策略及其在实际中的应用研究.docx》由会员分享,可在线阅读,更多相关《参考盲目搜索策略及其在实际中的应用研究.docx(17页珍藏版)》请在冰点文库上搜索。
参考盲目搜索策略及其在实际中的应用研究
商务学院
课程论文
论文题目盲目搜索策略及其在实际中的应用研究
专业年级08计科24班
课程名称人工智能
指导教师刘文江
学生姓名伍铖煌
学号200818131023
成绩
教务处制
二O一一年十月十日
盲目搜索策略及其在实际中的应用研究
摘要:
搜索策略是人工智能研究的主攻方向之一,采用不同的搜索策略在求解问题的过程中也会存在差异.通过对于八数码的搜索求解分析,采用盲目搜索中的广度优先搜索算法和宽度搜索算法进行实现,将广度优先搜索算法与宽度搜索算法进行比较,从而评价这两种搜索算法的优劣性.
关键字:
搜索策略;深度优先;宽度优先;八数码
1盲目的图搜索策略
图搜索策略可分为两种:
一种称为盲目的图搜索策略,或称无信息图搜索策略; 而另一种称为启发式搜索策略,又称为有信息的图搜索策略。
盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索[1]。
最常用的两种无信息图搜索策略是宽度优先搜索和深度优先搜索。
1.1宽度优先搜索[2]
它是从根节点(起始节点)开始,按层进行搜索,也就是按层来扩展节点。
所谓按层扩展,就是前一层的节点扩展完毕后才进行下一层节点的扩展,直到得到目标节点为止。
这种搜索方式的优点是,只要存在有任何解答的话,它能保证最终找到由起始节点到目标节点的最短路径的解,但它的缺点是往往搜索过程很长。
1.2深度优先搜索[3]
它是从根节点开始,首先扩展最新产生的节点,即沿着搜索树的深度发展下去,一直到没有后继结点处时再返回,换一条路径走下去。
就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一级节点,沿另一方向又继续前进。
这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
由于一个有解的问题树可能含有无穷分枝,深度优先搜索如果误入无穷分枝(即深度无限),则不可能找到目标节点。
为了避免这种情况的出现,在实施这一方法时,定出一个深度界限,在搜索达到这一深度界限而且尚未找到目标时,即返回重找,所以,深度优先搜索策略是不完备的[4]。
另外,应用此策略得到的解不一定是最佳解(最短路径)。
2用深度优先或宽度优先解决8数码(见附录)
【八数码问题】[5]
所谓八数码问题是指这样一种游戏:
将分别标有数字1,2,3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上。
放牌时要求不能重叠。
于是,在3×3的数码盘上出现了一个空格。
现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列。
解决八数码问题的算法很多,盲目是搜索算法如深度优先搜索、宽度优先搜索等[7]。
1八数码游戏问题的状态空间法表示
1.1状态描述
我们在八数码问题中,将号码牌摆放的位置抽象成一个序列,用来记录不同码值的号码牌的摆放位置。
若用0来表示空格,则
将初始状态为:
,目标状态为
:
的八数码问题转换为从开始序列:
[2,8,3,1,0,4,7,6,5]转换到目标序列[1,2,3,8,0,4,7,6,5]的问题。
1.2操作符描述
对于八数码问题中空格的移动问题,我们建立以下操作符:
左移:
1;上移:
2;下移:
3;右移:
4
建立下列状态转换:
空格右移了一步,所以用4来表示。
1.3状态空间法的数据结构
structNode
{
public:
intpath[2];//path[0]isthelineoftheclosedboxpath[1]isthedirectionof
//thefathernodemovetothisnode
intlayer;//layeristhedeepnumsofthenodeinthewholegraph
stringseq;//usingthestringtoachievethesequence
};
其中stringseq记录数码位置,path[2]以及intlayer。
path[0]表示这个结点记录是closed表当中的第几个记录,path[1]是本记录结点的父结点。
Layer表示在已搜索的树当中是第几层。
空格移动规则如表1所示。
2八数码游戏问题的盲目搜索技术
2.1宽度优先搜索
2.1.1宽度优先搜索的搜索步骤
①把起始节点放到OPEN表中(如果该起始节点为一目标节点,则得到解)
②如果OPEN是个空表,则无解,失败退出;否则继续下一步
③把第一个节点(记作节点n)从OPEN表移出,并把它放入CLOSED的已扩展节点表中
④扩展节点n。
如果没有后继节点,则转向第②步
⑤把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针
⑥如果n的任一个后继节点是个目标节点,则找到一个解(反向追踪得到从目标节点到起始节点的路径),成功退出,否则转向第②步
2.1.2宽度优先的成员数据结构
stringInitialString,ResultString;
初始序列以及结果序列
OPEN表:
SeqQueuews_open
(特别说明,这里的SeqQueue是我自己实现的队列模板,因为想试下有没有用,就放到程序里试了一下)
存放待扩展的节点,从数据结构上来说,它是一个先进先出的队列
CLOSED表:
vectorws_closed;
(堆栈用vector实现)
是存放已被扩展过的节点(包括有后继节点的非端节点和无后继节点的端节点)
intWsExpand(Nodenode,intNo)
宽度优先搜索的扩展结点函数
输入:
待扩展结点node;父结点(即node结点)在closed表的编号No
结果:
扩展上下左右四个方向的结点,并存入open表。
如果生成结点中有目标结点,则返回最后一步移动的方向。
voidswap(char&a,char&b)
字符交换函数
输入:
字符a,字符b
结果:
在序列中,将a和b的位置交换
(深度和宽度合用)
voidWideSearch()
输入:
无
结果:
对成员初始序列到结果序列进行宽度优先搜索,得出搜索过程。
boolisInOpenOrClosed(Nodes)
输入:
待测结点s
结果:
返回带测结点在open或closed表中的真值
2.2深度优先搜索
2.2.1深度优先搜索的搜索过程
①把起始节点S放到未扩展节点的OPEN表(此时OPEN表是一个堆栈,后进先出)中。
如果此节点为一目标节点,则得到解
②如果OPEN为一空表,则无解、失败退出
③把第一个节点(记作节点n)从OPEN表移到CLOSED表
④如果节点n的深度等于最大深度,则转向②
⑤扩展节点n,产生其全部后继节点,并把它们放入OPEN表的前头。
如果没有后继节点,则转向
②
⑥如果后继节点中有任一个节点为目标节点,则求得一个解(反向追踪从目标节点到起始节点的路径),成功退出;否则,转向②
2.2.2深度优先搜索的成员数据结构
stringInitialString,ResultString;
初始序列以及结果序列
OPEN表:
vectords_open
在深度优先搜索中,open表式一个后进先出的堆栈,这里用vector来实现。
CLOSED表:
vectords_closed
在宽度优先搜索中,closed表用vector来实现,是存放已被扩展过的节点(包括有后继节点的非端节点和无后继节点的端节点)
intDsExpand(Nodenode,intNo)
深度优先搜索的扩展结点函数
输入:
待扩展结点node;父结点(即node结点)在closed表的编号No
结果:
扩展上下左右四个方向的结点,并存入open表。
如果生成结点中有目标结点,则返回最后一步移动的方向
voidswap(char&a,char&b)
字符交换函数
输入:
字符a,字符b
结果:
在序列中,将a和b的位置交换
(深度和宽度合用)
voidDeepSearch()
输入:
无
结果:
对成员初始序列到结果序列进行深度优先搜索,得出搜索过程。
boolisInDSOpenOrClosed(Nodes)
输入:
待测结点s
结果:
返回带测结点在open或closed表中的真值
3例子及分析
初始状态通过目标状态倒推
3.1.1宽度优先搜索
程序运行如图3.1.1所示。
图3.1.1
如图所示,宽度优先搜索共走了4步,所用时间约为0.65秒,获得的解为全局最优解。
3.1.2深度优先搜索
而深度优先搜索结果和深度界限有关,所以当深度界限分别为3,5,20时,结果如下:
当深度界限为3时,如图3.1.2所示。
图3.1.2
当深度界限为5时,如图3.1.3所示。
图3.1.3
走了4步,耗费时间0.027s
当深度界限为20时如图3.1.4所示。
图3.1.4
走了20步,所用时间为4.65s
4结束语
从例子的结果来看,宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径(所用操作符最少),只要结点间可以到达,就一定可以找到一个最优解。
深度优先搜索具有深度界限,当搜索深度达到深度界限时,停止搜索。
所以,深度优先搜索有可能会得不到结果,是一种不安全的搜索方法。
但是当结果在搜索界限内时,可以快速的得到结果,时间效率高。
故对于深度优先搜索,如何去定义一个较好的搜索界限,是下一步需要继续改进的方面。
3深度优先搜索和宽度优先搜索的优缺点[6]
(1)宽度优先搜索在有解的情况下可以找到最优解,但深度优先搜索不同,它不保证第一次碰到某个状态时,找到的就是到这个状态的最短路径,而且也不保证一定能找到解。
(2)宽度优先可以保证找到解,但是如果存在一个不利的分支(各个状态相对很多的情况),那么会非常耗时。
(3)如果要搜索具有很多分支的空间,那么深度优先搜索的效率更高,因为它不必把给定层的所有结点保存到open列表中
(4)选择深度优先搜索还是宽度优先搜索的最佳答案是仔细分析问题空间并向这个领域的专家咨询。
例如,对于国际象棋来说,宽度优先搜索就是不可能的。
在更简单的游戏中,宽度优先搜索不仅是可能的,而且可能是避免迷失的惟一方法。
附录:
利用宽度优先算法解决8数码(源代码)
#include
#include
#include
#definemax_layer5/*最大扩展层数宏定义*/
#definetrue1
#definefail0
#definenull0
structlink
{
intdata[3][3];/*八数码状态*/
intlayer;/*该节点的层数*/
structlink*next;
structlink*prior;
};
structlink*close_head;/*Close表的根节点*/
structlink*open_head;/*Open表的根节点*/
/*****************************************************/
/*函数名称:
output()*/
/*功能说明:
输出指针P指向的节点的数据*/
/****************************************************/
voidoutput(structlink*p)
{
inti,j;
while(p!
=NULL)
{for(i=0;i<3;i++)/*行输出控制*/
{
for(j=0;j<3;j++)/*列输出控制*/
printf("%d",p->data[i][j]);/*输出i行j列上的数据*/
printf("\n");/*每输出一行数据,回车换行*/
}
printf("---------------------\n");/*输出一条横线以区分屏幕上其他节点数据*/
p--;
}/*函数名称:
compare*/
/*功能说明:
将指针Operate指向的节点中的数据与二维数组dest中的数据进行比较*/
intcompare(structlink*q,intdest[3][3])
{
inti,j,count=0;
for(i=0;i<3;i++)/*行比较控制*/
{
for(j=0;j<3;j++)/*列比较控制*/
{
if(q->data[i][j]==dest[i][j])/*比较i行j列上的数据*/
count++;/*计数器加一*/
else/*只要发现有一个数据不相等*/
{/*即返回fail,宣告比较失败*/
j=3;/*强制推出for循环*/
i=3;/*强制推出for循环*/
return0;
}}}
if(count==9)/*相等的数据的个数与维数平方相等*/
return1;/*表示数据都对应相等,返回true*/
}
/*函数名称:
eight()*/
/*功能说明:
通过深度扩展的方式找出八数码问题从初始状态到目标状态的路径*/
inteight(structlink*open_head,intdest[3][3])
{
inti,j,zero_x,zero_y;/*0的横坐标,0的纵坐标*/
structlink*new_point;/*处理open表的一个临时指针*/
structlink*open_point=*open_head;/*open表操作指针1*/
structlink*close_point;
while(open_link_point!
=NULL)
{
close_point=open_point;
open_point->prior->next=NULL;
open_point--;
if(compare(close_point,dest)==1)
{
printf("findsolution");
output(close_point);
return1;
}
else
{
if(close_point->layer>max_layer)
{
close_point->next=*open_point;
close_point++;
}
else
{
for(i=0;i<3;i++)/*获取0的坐标*/
{
for(j=0;j<3;j++)
{
if(close_point->data[i][j]==0)/*dataordest*/
{
zero_x=i;/*横坐标*/
zero_y=j;/*纵坐标*/
j=3;/*强制退出循环*/
i=3;/*强制退出循环*/
}}}
if((zero_x-1)>=0)/*往上移*/
{/*申请内存空间*/
new_point=(structlink*)malloc(sizeof(structlink));
for(i=0;i<3;i++)/*对新扩展的节点赋值*/
{
for(j=0;j<3;j++)
new_point->data[i][j]=close_point->data[i][j];
}
new_point->data[zero_x][zero_y]=new_point->data[zero_x-1][zero_y];
new_point->data[zero_x-1][zero_y]=0;
open_point->next=*new_point;
open_point++;
}
if((zero_x+1)<3)/*往下移*/
{/*申请内存空间*/
new_point=(structlink*)malloc(sizeof(structlink));
for(i=0;i<3;i++)/*对新扩展的节点赋值*/
{
for(j=0;j<3;j++)
new_point->data[i][j]=close_point->data[i][j];
}
new_point->data[zero_x][zero_y]=new_point->data[zero_x+1][zero_y];
new_point->data[zero_x+1][zero_y]=0;
open_point->next=*new_point;
open_point++;
}
if((zero_y-1)>=0)/*0往右移*/
{/*申请内存空间*/
new_point=(structlink*)malloc(sizeof(structlink));
for(i=0;i<3;i++)/*对新扩展的节点赋值*/
{
for(j=0;j<3;j++)
new_point->data[i][j]=close_point->data[i][j];
}
new_point->data[zero_x][zero_y]=new_point->data[zero_x][zero_y-1];
new_point->data[zero_x][zero_y-1]=0;
open_point->next=*new_point;
open_point++;
}
if((zero_y+1)<3)/*0往左移*/
{/*申请内存空间*/
new_point=(structlink*)malloc(sizeof(structlink));
for(i=0;i<3;i++)/*对新扩展的节点赋值*/
{
for(j=0;j<3;j++)
new_point->data[i][j]=close_point->data[i][j];
}
new_point->data[zero_x][zero_y]=new_point->data[zero_x][zero_y+1];
new_point->data[zero_x][zero_y+1]=0;
open_point->next=*new_point;
open_point++;
}}}}
if(open_point=NULL)
printf("nosolution");
}
/*函数名称:
main*/
voidmain()
{
inti,j;
intdestination[3][3];/*二维数组,用以存放目标状态*/
structlink*open_head=(structlink*)malloc(sizeof(structlink));/*申请一个节点空间*
printf("Themaxdimentionis3");/*提醒用户八数码的维数大小*/
printf("Pleaseinputtheinitialstateof
\n");
for(i=0;i<3;i++)/*获取八数码的初始状态*/
{
for(j=0;j<3;j++)
scanf("%d",&open_head->data[i][j]);/*把初始状态存放在申请的节点中,即Open表*/
}
printf("Pleaseinputthefinalstateof
\n");
for(i=0;i<3;i++)/*获取八数码的目标状态*/
{
for(j=0;j<3;j++)
scanf("%d",&destination[i][j]);/*把目标状态数据存放在destination[][]中*/
}
open_head->layer=0;/*初始化初始状态节点的层数为0,表示还为进行扩展*/
eight(open_head,destination);
}
参考文献
[1]耿汝年浅谈人工智能中的搜索策略《山东轻工业学院学报》2005年20卷2期(30-31)
[2]马少平图的深度优先遍历算法及运用《电脑编程技巧与维护》2011年卷16期(93-94)
[3]耿汝年无信息图搜索算法的改进研究《山东轻工业学院学报》2006年20卷2期(40-44)
[4]殷永峰深度优先搜索的优化算法《计算机仿真》2011第07期(20-23)
[5]曾范清求解八数码问题的算法比较《福建电脑报》2008第12期(3)
[6]龙振海林泓深度优先和宽度优先《计算机科学》2010第2期
[7]周浩八数码问题DFS和BFS算法的设计与实现《电脑知识与技术》2011第22期
[8]钱莹基于广度优先搜索的八数码问题解决方案《电脑学习》2008第01期
[9]刘翔龚道雄深度优先算法的仿真研究《制造业自动化》2011第11期
[10]钟声基于深度优先的图匹配算法《计算机工程与科学》2008第12期
素材资料从网络收集整理而来,供参考!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 参考 盲目 搜索 策略 及其 实际 中的 应用 研究