人工智能搜索实验Word格式.docx
- 文档编号:3636205
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:40
- 大小:95.17KB
人工智能搜索实验Word格式.docx
《人工智能搜索实验Word格式.docx》由会员分享,可在线阅读,更多相关《人工智能搜索实验Word格式.docx(40页珍藏版)》请在冰点文库上搜索。
while(q<
end)
}else{
while(p<
mid)
copy(tmp,tmp+size,begin);
delete[]tmp;
boolCheck(intdata[],intnum)
inti;
for(i=0;
i<
num;
++i)
if(data[i]==0)
break;
return(CalcInvNum(data,data+num)-i)%2==0;
intmain()
while(true){
intm,n;
cin>
>
m>
n;
if(m==0)
intnum=m*n;
int*data=newint[num];
for(inti=0;
++i){
data[i];
cout<
<
(Check(data,num)?
"
YES"
:
NO"
)<
endl;
delete[]data;
八数码问题
一.八数码问题
八数码问题也称为九宫问题。
在3×
3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。
棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。
要求解决的问题是:
给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。
棋子移动后,状态就会发生改变。
解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
八数码问题一般使用搜索法来解。
搜索法有广度优先搜索法、深度优先搜索法、A*算法等。
这里通过用不同方法解八数码问题来比较一下不同搜索法的效果。
二.搜索算法基类
1.八数码问题的状态表示
八数码问题的一个状态就是八个数字在棋盘上的一种放法。
每个棋子用它上面所标的数字表示,并用0表示空格,这样就可以将棋盘上棋子的一个状态存储在一个一维数组p[9]中,存储的顺序是从左上角开始,自左至右,从上到下。
也可以用一个二维数组来存放。
2.结点
搜索算法中,问题的状态用结点描述。
结点中除了描述状态的数组p[9]外,还有一个父结点指针last,它记录了当前结点的父结点编号,如果一个结点v是从结点u经状态变化而产生的,则结点u就是结点v的父结点,结点v的last记录的就是结点u的编号。
在到达目标结点后,通过last可以找出搜索的路径。
3.类的结构
在C++中用类来表示结点,类将结点有关的数据操作封装在一起。
不同的搜索算法具有一定共性,也有各自的个性,因此这里将不同搜索算法的共有的数据和功能封装在一个基类中,再通过继承方式实现不同的搜索算法。
4.结点扩展规则
搜索就是按照一定规则扩展已知结点,直到找到目标结点或所有结点都不能扩展为止。
八数码问题的结点扩展应当遵守棋子的移动规则。
按照棋子移动的规则,每一次可以将一个与空格相邻棋子移动到空格中,实际上可以看作是空格作相反移动。
空格移动的方向可以是右、下、左、上,当然不能移出边界。
棋子的位置,也就是保存状态的数组元素的下标。
空格移动后,它的位置发生变化,在不移出界时,空格向右、下、左和上移动后,新位置是原位置分别加上1、3、-1、-3,如果将空格向右、下、左和上移动分别用0、1、2、3表示,并将-3、3、-1、1放在静态数组d[4]中,空格位置用spac表示,那么空格向方向i移动后,它的位置变为spac+d[i]。
空格移动所产生的状态变化,反映出来则是将数组p[]中,0的新位置处的数与0交换位置。
5.八数码问题的基类
八数码问题的基类及其成员函数的实现如下:
#defineNum9
classTEight
public:
TEight(){}
TEight(char*fname);
virtualvoidSearch()=0;
protected:
intp[Num];
intlast,spac;
staticintq[Num],d[],total;
voidPrintf();
booloperator==(constTEight&
T);
boolExtend(inti);
};
intTEight:
:
q[Num];
d[]={1,3,-1,-3};
total=0;
TEight:
TEight(char*fname)
ifstreamfin;
fin.open(fname,ios:
in|ios:
nocreate);
if(!
fin)
cout<
"
不能打开数据文件!
endl;
return;
for(inti=0;
i<
Num;
)
fin>
p[i++];
spac;
for(i=0;
q[i++];
fin.close();
last=-1;
voidTEight:
Printf()
ofstreamfout;
fout.open("
.\Eightr.txt"
ios:
ate);
fout<
setw(4)<
total++<
t"
;
setw
(2)<
fout.close();
boolTEight:
operator==(constTEight&
T)
if(T.p[i]!
=p[i++])
return1;
Extend(inti)
if(i==0&
spac%3==2||i==1&
spac>
5
||i==2&
spac%3==0||i==3&
spac<
3)
inttemp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
数据文件的结构:
一共三行,第一行是用空格隔开的九个数字0~8,这是初始状态。
第二行是一个数字,空格(数字0)的位置,第三行也是用空格隔开的九个数字0~8,这是目标状态。
三.线性表
搜索法在搜索过程中,需要使用一个队列存储搜索的中间结点,为了在找到目标结点后,能够找到从初始结点到目标结点的路径,需要保留所有搜索过的结点。
另一方面,不同问题甚至同一问题的不同搜索方法中,需要存储的结点数量相差很大,所以这里采用链式线性表作为存储结构,同时,为适应不同问题,线性表设计成类模板形式。
template<
classType>
classTList;
//线性表前视定义
classTNode
//线性表结点类模板
friendclassTList<
Type>
public:
TNode(){}
TNode(constType&
dat);
private:
TNode<
*Next;
TypeData;
classTList
TList(){Last=First=0;
Length=0;
}
//构造函数
intGetlen()const{returnLength;
//成员函数,返回线性表长度
intAppend(constType&
T);
//成员函数,从表尾加入结点
intInsert(constType&
T,intk);
//成员函数,插入结点
TypeGetData(inti);
//成员函数,返回结点数据成员
voidSetData(constType&
//成员函数,设置结点数据成员
*First,*Last;
//数据成员,线性表首、尾指针
intLength;
//数据成员,线性表长度
intTList<
Append(constType&
T)
Insert(T,Length);
return1;
Insert(constType&
T,intk)
*p=newTNode<
p->
Data=T;
if(First)
{
if(k<
=0)
Next=First;
First=p;
if(k>
Length-1)
Last->
Next=p;
Last=Last->
Next;
Next=0;
0&
k<
Length)
k--;
*q=First;
while(k-->
0)
q=q->
Next=q->
q->
else
First=Last=p;
First->
Next=Last->
Length++;
TypeTList<
GetData(intk)
*p=First;
p=p->
returnp->
Data;
voidTList<
SetData(constType&
四.广度优先搜索法
在搜索法中,广度优先搜索法是寻找最短路经的首选。
1.广度优先搜索算法的基本步骤
1)建立一个队列,将初始结点入队,并设置队列头和尾指针
2)取出队列头(头指针所指)的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列。
3)如果扩展出的新结点与队列中的结点重复,则抛弃新结点,跳至第六步。
4)如果扩展出的新结点与队列中的结点不重复,则记录其父结点,并将它加入队列,更新队列尾指针。
5)如果扩展出的结点是目标结点,则输出路径,程序结束。
否则继续下一步。
6)如果队列头的结点还可以扩展,直接返回第二步。
否则将队列头指针指向下一结点,再返回第二步。
2.搜索路径的输出
搜索到目标结点后,需要输出搜索的路径。
每个结点有一个数据域last,它记录了结点的父结点,因此输出搜索路径时,就是从目标结点Q出发,根据last找到它的父结点,再根据这个结点的last找到它的父结点,....,最后找到初始结点。
搜索的路径就是从初始结点循相反方向到达目标结点的路径。
3.广度优先搜索法TBFS类的结构
广度优先搜索法TBFS类是作为TEight类的一个子类。
其类的结构和成员函数的实现如下:
classTBFS:
publicTEight
TBFS(){}
TBFS(char*fname):
TEight(fname){}
virtualvoidSearch();
voidPrintl(TList<
TBFS>
&
L);
intRepeat(TList<
intFind();
voidTBFS:
Printl(TList<
L)
TBFST=*this;
if(T.last==-1)
else
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
intTBFS:
Repeat(TList<
intn=L.Getlen();
n;
i++)
if(L.GetData(i)==*this)
returni;
Find()
if(p[i]!
=q[i++])
Search()
TList<
L;
L.Append(T);
inthead=0,tail=0;
while(head<
=tail)
4;
T=L.GetData(head);
if(T.Extend(i)&
T.Repeat(L)>
tail)
T.last=head;
tail++;
if(T.Find())
head++;
4.广度优先搜索法的缺点
广度优先搜索法在有解的情形总能保证搜索到最短路经,也就是移动最少步数的路径。
但广度优先搜索法的最大问题在于搜索的结点数量太多,因为在广度优先搜索法中,每一个可能扩展出的结点都是搜索的对象。
随着结点在搜索树上的深度增大,搜索的结点数会很快增长,并以指数形式扩张,从而所需的存储空间和搜索花费的时间也会成倍增长。
五.双向广度优先搜索法
1.双向广度优先搜索法
八数码问题具有可逆性,也就是说,如果可以从一个状态A扩展出状态B,那么同样可以从状态B扩展出状态A,这种问题既可以从初始状态出发,搜索目标状态,也可以从目标状态出发,搜索初始状态。
对这类问题如果采用双向广度优先搜索法,将可以大大节省搜索的时间。
所谓双向广度优先搜索法,是同时从初始状态和目标状态出发,采用广度优先搜索的策略,向对方搜索,如果问题存在解,则两个方向的搜索会在中途相遇,即搜索到同一个结点。
将两个方向的搜索路径连接起来,就可以得到从初始结点到目标结点的搜索路径。
2.双向广度优先搜索算法
双向广度优先搜索算法的基本步骤如下:
1)建立两个队列,一个是正向搜索的队列,另一个是反向搜索的队列。
将初始结点放入正向队列,将目标结点放入反向队列,并设置两个队列的头和尾指针。
2)从正向队列取出队列头(头指针所指)的结点进行扩展。
5)检查扩展出的结点是否在另一方向的队列中,如果是则两个方向的搜索相遇,显示搜索路径,程序结束。
否则将队列头指针指向下一结点,然后对另一方向搜索的队列,按照第二步开始的同样步骤处理。
3.双向广度优先搜索法的优势
广度优先搜索法搜索时,结点不断扩张,深度越大,结点数越多。
如果从两个方向向对方搜索,就会在路径中间某个地方相会,这样,双方的搜索的深度都不大,所搜索过的结点数就少得多,搜索时间也就节省不少。
从理论上说,如果每一结点可扩展的子结点数为m,广度优先搜索的搜索树就是一颗m叉树,也就是每个结点都由m个分支。
按完全m叉树计算,如果目标结点在第n层,广度优先搜索就必须在搜索树上扩展完n-1层的所有结点,扩展的结点数为m(mn-1)/(m-1)。
对于双向广度优先搜索来说,如果两个方向的搜索在第i层生成同一子结点,那么正向搜索扩展的结点数为m(mi-1)/(m-1),反向搜索扩展的结点数为m(mn-i-1)/(m-1),搜索的结点总数为m(mi+mn-i-1)/(m-1)(其中n是最优解路径长度,i=(m+1)div2,)。
设n为偶数(n=2*i),广度优先双向搜索扩展的结点数约是广度优先搜索的2/(mi/2+1)*100%,相对减少(mi/2-1)/(mi/2+1)*100%。
4.判断两个方向的搜索相遇
在双向广度优先搜索法中,如何判断两个方向的搜索相遇呢?
只要我们在生成结点的同时,判断该结点是否出现在相反方向的搜索树上即可,也就是说,在某个方向搜索中扩展出一个新结点,如果它与另一个方向已扩展出的结点重复,也就找到了解。
5.双向广度优先搜索法的TDBFS类结构
双向广度优先搜索法的TDBFS和广度优先搜索法类似,也是TEight类的子类,类结构及其成员函数的实现如下:
classTDBFS:
TDBFS(){}
TDBFS(char*fname):
voidPrintp(TList<
TDBFS>
voidPrintb(TList<
voidTDBFS:
Printp(TList<
TDBFST=*this;
T.Printp(L);
Printb(TList<
while(T.last>
-1)
intTDBFS:
if(L.GetData(i++)==*this)
TDBFST1=*this;
TDBFST2;
T2.p[i]=q[i];
if(q[i]==0)
T2.spac=i;
T2.last=-1;
L1,L2;
L1.Append(T1);
L2.Append(T2);
inthead1=0,tail1=0,head2=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 搜索 实验