八数码实验报告
八数码实验报告
:
03122997
学校:上海大学学院:计算机学院
关键字:八数码、人工智能、A*算法、双向广搜、启发式函数
摘要:
九宫排字问题(又称八数码问题)是人工智能当中有名的难题之一。问题是在
3×3方格盘上,
放有八个数码,剩下第九个为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目
标位置,要求通过一系列的数码移动,将初始位置转化为目标位置。本文介绍用普通搜索方法、双
向广度搜索和启发式搜索如何缩短寻找路径的时间,以及各算法间的利与弊。
目录:
问题简介
问题分析
算法设计
程序实现
相关链接
问题简介:
所谓八数码问题是指这样一种游戏:将分别标有数字
1,2,3,…,
8的八块正方形数码牌任意
地放在一块
3×3的数码盘上。放牌时要求不能重叠。于是,在
3×3的数码盘上出现了一个空格。
现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某
种特殊的排列。如下图表示了一个具体的八数码问题求解。
问题分析:
首先,八数码问题包括一个初始状态
(START)和目标状态
(END),所谓解八数码问题就是在两
个状态间寻找一系列可过渡状态(
START>
STATE1>
STATE2>...
>
END)。这个状态是否存在就是我
们要解决的第一个问题:
Q1:每一个状态及每一次操作的表示方法?
有许多表示方法,比如一个
3*3的八数码盘可以压缩成一个
int值表示,但不适用于
15puzzle
或大于
8的
puzzle问题。如果对空间要求很高,应该还可以再压缩。本文采用一个int表示的方法。
表示方法如下:由于
int的表示范围大于
1e9,所以我们取一个
int的低
9位,为了方便寻找空
格的位置,int的个位我们用来放空格的位置(19)
。而前
8位,按照行从上到下,列从左到右的顺
序依次记录对应位置上的数字。例如:
成
231584675,个位的
5表示空格在第
5位,前八位数按顺序记
录。坐标转换公式为:
num(压缩后的
int)
xy(求
x行
y列,1记起)1e(n)为
1乘
10的
n次
int
temp=(x1)*
3+y
if
temp>num%10thenreturn(num/1e(9temp+
1))%10
else
return(num/1e(9temp))%
10
为了方便本文介绍,取目标状态为:123456789即>
操作本文用
urdl分别表示空格的向上向右向下向左四个操作。比如,在简介中的图包括两步操作
ld,可能与平时玩这类游戏的习惯不符合,但这是为了和
ACM例题相统一。
对应地,每种操作引起的状态变化如下:
r:num值++
l:num值u:
有点复杂
int
t0=
9num%
10+
1
int
t1=
num/1e(t0)
int
t2=
t1%1000
t1=
t1t2+
(t2
%100)
*
10+
t2
/100
t1*=
1e(t0)
return(t1+
((num%t0)
3))
d:return前面同
u操作,
return返回
(t1+
((num%t0)+
3))
Q2:判断是否存在中间状态使
START到达
END?
用组合数学的方法可以快速地进行判断,例如SOJ
2061题
2360题中都是关于此类的问题。但
八数码的判断方法比他们简单多了。
本文用的方法是计算排列的逆序数值,以231584675为例子,5表示的是空格,不计算,那么求
23158467的逆序值为
+0
+2
(1<21<3)
+0+
0+
1(
4<5)+
1(6<8
)+1
(7<8)
=5
目标状态
123456789的逆序自然就是
0。
两个状态之间是否可达,可以通过计算两者的逆序值,若两者奇偶性相同则可达,不然两个状
态不可达。
简单证明一下:
l和
r操作,不会影响状态的逆序值,因为只会改变个位数(空格的位置)。
u和
d操作是使某个位置的数字右
/左移两位。由于数字序列的每一次移动会使逆序值奇偶性
改变,所以移动两次后奇偶性不变。
所以四个操作均不会影响序列的奇偶性。
Q3:如何寻找一系列的中间状态及遇到的问题?
要寻找这一系列中间状态的方法是搜索,但搜索很容易遇到时间和空间上的问题。以下就是搜
索的基本原理:
由
137246852状态可以衍生三个状态,假如选择
了
123746855,则又衍生三个状态,继续按某策略进
行选择,一直到衍生出的新状态为目标状态
END为止。
容易看出,这样的搜索类似于从树根开始向茎再向叶
搜索目标叶子一样的树型状。由于其规模的不断扩大,其
叶子也愈加茂密,最终的规模会大到无法控制。这样在空
间上会大大加大搜索难度,在时间上也要消耗许多。
在普通搜索中遇到以下问题:
搜索中易出现循环,即访问某一个状态后又来访问该
状态。
搜索路径不佳便无法得到较好的中间状态集(即中间
状态集的元素数量过大)。
搜索过程中访问了过多的无用状态,这些状态对最后
的结果无帮助。
以上三个问题中,a为致命问题,应该它可能导致程序死循环;
b和
c是非致命的,但若不处理
好可能导致性能急剧下降。
Q4:怎样避免重复访问一个状态?
最直接的方法是记录每一个状态访问否,然后再衍生状态时不衍生那些已经访问的状态了。思
想是,给每个状态标记一个
flag,若该状态
flag=true则不衍生,若为
false则衍生并修改
flag为
true。
在某些算法描述里,称有两个链表,一个为活链表(待访问),一个为死链表(访问完)。每一
次衍生状态时,先判断它是否已在两个链表中,若存在,则不衍生;若不存在,将其放入活链表。
对于被衍生的那个状态,放入死链表。
为了记录每一个状态是否被访问过,我们需要有足够的空间。八数码问题一共有
9!,这个数字
并不是很大,但迎面而来的另一个问题是我们如何快速访问这些状态,如果是单纯用链表的话,那
么在规模相当大,查找的状态数目十分多的时候就不能快速找到状态,其复杂度为
O(n),为了解决这
个问题,本文将采用哈希函数的方法,使复杂度减为
O(1)。
这里的哈希函数是用能对许多全排列问题适用的方法。取
n!为基数,状态第
n位的逆序值为哈
希值第
n位数。对于空格,取其(9
位置)再乘以
8!。例如,137246858的哈希值等于:
0*0!
+0*1!+
0*2!+2*3!+
1*4!+1*5!
+0*6!+
3*7!+(98)*
8!=
55596<9!
具体的原因可以去查查一些数学书,其中
123456789的哈希值是
0最小,876543210
的哈希值是(9!1)
最大,而其他值都在
0到(
9!1)
中,且均唯一。
Q5:如何使搜索只求得最佳的解?
Q5:如何使搜索只求得最佳的解?
为
DFS(深度优先搜索)。除了
DFS,还有
BFS,从概念上讲,两者只是在扩展时
的方向不同,DFS向深扩张,而
BFS向广扩张。在八数码问题的解集树中,树的深度就表示了从初
始态到目标态的步数,DFS一味向深,所以很容易找出深度较大的解。
BFS可以保证解的深度最少,因为在未将同一深度的状态全部访问完前,BFS不会去访问更深的状态,因此比较适合八数码问题,至少能解决求最佳解的难题。例如:
左图进行的是
BFS,起始状态
衍生四个状态,然后依次访问这四
个状态,将第
1层全访问完后再访
问第二层,直到找到
END状态为
止。
但是
BFS和
DFS一样不能解
决问题
c,因为每个状态都需要扩张,所以广搜很容易使待搜状态的数目膨胀。最终影响效率。
Q6:该如何减少因广搜所扩张的与目标状态及解无关的状态?
前面所说的都是从
START状态向
END状态搜索,那么,将
END状态与
START状态倒一下,
其实会有另一条搜索路径(Q8策略三讨论),但简单的交换
END与
START并不能缩小状态膨胀的
规模。我们可以将正向与反向的搜索结合起来,这就是双向广度搜索。
双向广搜是指同时从
START和
END两端搜,当某一端所要访问的一个状态是被另一端访问过
的时候,即找到解,搜索结束。它的好处是可以避免广搜后期状态的膨胀。可以用下面这张图形象
的进行比较:
左图的解集数是双向广搜的树,通过两端的共同搜索,两端找到了共同的状态。右端的树是同
一个问题的
BFS树,在搜索后期,规模不断扩大,虽然能找到了目标状态,但其访问了许多无用结
点,浪费了空间和时间。
采用双向广度搜索可以将空间和时间节省一半!
Q7:决定一个快的检索策略?
双向广搜能大大减少时间和空间,但在有的情况下我们并不需要空间的节省,比如在
Q4中已
经决定了我们需要使用的空间是
9!,所以不需要节省。这样我们可以把重点放在时间的缩短上。
启发式搜索是在路径搜索问题中很实用的搜索方式,通过设计一个好的启发式函数来计算状态
的优先级,优先考虑优先级高的状态,可以提早搜索到达目标态的时间。
A*是一种启发式搜索的,
他的启发式函数
f'()=g'()+
h'()能够应用到八数码问题中来。
g'
()
从起始状态到当前状态的实际代价
g*()的估计值,g'
()>=
g*()
h'
()
从当前状态到目标状态的实际代价
h*()的估计值,h'
()<=
h*()
注意两个限制条件:
(1)h'
()<=
h*()(2)任意状态的
f
'()值必须大于其父状态的
f'()值,即
f'()单调递增。
其中,g'
()是搜索的深度,
h'
()则是一个估计函数,用以估计当前态到目标态可能的步数。解八数码问题时一般有两种估计函数。比较简单的是
difference(Statusa,
Statusb),其返回值是
a和
b状态各位置上数字不同的次数。另一种比较经典的是曼哈顿距离manhattan
(Status
a,
Status
b),
其返回的是各个数字从
a的位置到
b的位置的距离(见例子)。
例如状态
137246852和状态
123456789的
difference是
5(不含空格,图中红色)。
而他的
manhattan距离是:
1
(7d一次)+
1(2u一次)
+2
(4l两次)+3
(6r两次
u一次)
+2
(5u一次
l一次)=9
单个数字的
manhattan应该小于
5,因为对角的距离才
4,若大于
4则说明计算有误。
无论是
difference还是
manhattan,估计为越小越接近
END,所以优先级高。
在计算
difference和
manhattan时,推荐都将空格忽略,因为在
difference中空格可有可无,对整
体搜索影响不大。
考虑下面两个状态(左需要
3步到达
END态,右需要
4步到达
END态),不含空格时
diff=3
是相同的,含空格时左边的比右边的大一,但是实际上左图只要3步就能到达
END态,而右图需要
4步,多计算了空格反而把优先级搞错了。
而
manhattan中,如果把空格也算上,实际上只会降低搜索速度(经过实验证明),同样考虑下图,不计算空格时两者的
manhattan是左
3右
4,比
diff要好,因为左的优先级大于右了。而加上空
格后,manhattan是左
6右
4,不但颠倒了优先级,其误差比
diff加空格后还要大。
本文后面的实现将使用
manhattan不计空格的方法。其实,每移动一步,不计空格,相当于移
动一个数字。如果每次移动都是完美的,即把一个数字归位,那么
START态到
END态的距离就是
manhattan。反过来说,manhattan是
START到
END态的至少走的步数。
回到
f'()=g'()+h'
(),其实广度搜索是
h'
()=0的一种启发式搜索的特例,而深度搜索是
f'
()=0
的一般搜索。h'
()对于优化搜索速度有很重要的作用。
Q8:能否进一步优化检索策略?
Q8:能否进一步优化检索策略?
。
A*搜索策略的优劣就是看
h'
()的决定好坏。前面列举了两个
h'()的函数,但光有这两个是不够
的。经过实验分析,在
f'()中,g
'()决定的是
START态到
END态中求得的解距离最优解的距离。而
h'
()能影响搜索的速度。
所以优化的第一条策略是,放大
h'
(),比如,让
h
'()=
10*
manhattan(),那么
f
'()=
g'
()+10*manhattan(),可能提高搜索速度。可惜的是所得的解将不再会是最优的了。
为什么放大
h'()能加快搜索速度,我们可以想象一下,h'()描述的是本状态到
END态的估计距离,
估计距离越短自然快一点到达
END态。而
g'
()描述的是目前的深度,放大
h'
()的目的是尽量忽略深
度的因素,是一种带策略的深搜,自然速度会比广搜和深搜都快,而因为减少考虑了深度因素,所
以离最优解就越来越远了。关于
h'
()放大多少,是很有趣的问题,有兴趣可以做些实验试试。
第二条是更新待检查的状态,由于
A*搜索会需要一个待检查的序列。首先,在
Q4已经提到用
哈希避免重复访问同一状态。而在待检查队列中的状态是未完成扩张的状态,如果出现了状态相同
但其
g'()比原
g'()出色的情况,那么我们更希望的是搜索新状态,而不是原状态。这样,在待检查队
列中出现重复状态时,只需更新其
g'()就可以了。
第三条是注意实现程序的方法,在起初我用
sort排序
f'()后再找出权值最大的状态,而后发现用
make_heap要更快。想一想,由于需要访问的接点较多,待访问队列一大那么自然反复排序对速度
会有影响,而堆操作则比排序更好。另一点是,实现更新待检查队列时的搜索也要用比较好的方法
实现。我在
JAVA的演示程序中用的
PriorityQueue,可是结果不是很令人满意。
第四条优化策略是使用
IDA*的算法,这是
A*算法的一种,ID名为
Iterativedeepening是迭代加
深的意思。思想是如下:
顺便准备一个记录一次循环最小值的
temp=MAX,
h'取
manhattan距离
先估算从
START态到
END态的
h'()记录为
MIN,将
START放入待访问队列
读取队列下一个状态,到队列尾则
GOTO⑦
若
g'()>
MINGOTO
⑥
若
g'()+h'()
>MIN是否为真,真
GOTO⑥,否
GOTO
⑤
扩展该状态,并标记此状态已访问。找到
END态的话就结束该算法。GOTO
②
temp
=min(manhattan,
temp),GOTO
③
若无扩展过状态,MIN=temp(ID的意思在这里体现)从头开始循环
GOTO
②
第五条优化策略本身与搜索无关,在做题时也没能帮上忙,不过从理论上讲是有参考价值的。记得
Q6中介绍的从
END开始搜起吗?如果我们的任务是对多个
START与
END进行搜索,那么我
们可以在每搜索完一次后记录下路径,这个路径很重要,因为在以后的搜索中如果存在START和
END的路径已经被记录过了,那么可以直接调出结果。
从
END搜起,可以方便判断下一次的
START是否已经有路径到
END了。当前一次搜索完时,
其已访问状态是可以直接使用的,若
START不在其中,则从待访问的状态链表中按搜索策略找下一
个状态,等于接着上一次的搜索结果开始找。
之所以没能在速度上帮上忙,是因为这个优化策略需要加大
g'
()的比重,否则很容易出现深度
相当大的情况,由于前一次搜索的策略与下一次的基本无关,导致前一次的路径无法预料,所以就
会出现深度过大的情况。解决方法是加大
g'
()。
策略五类似给程序加一个缓冲区,避免重复计算。如果要做八数码的应用,缓冲区会帮上忙的。
Q10:怎样记录找到的路径?
Q10:怎样记录找到的路径?
的
DFS,
所以不能借助通过函数调用所是使用的程序栈。
我们可以手工加一个模拟栈。在
Q4中解决了哈希的问题,利用哈希表就能快速访问状态对应
的值,在这里,我们把原来的
bool值改为
char或其他能表示一次操作(至少需要
5种状态,除了
u
rld外还要能表示状态已访问)的值就行了。
在搜索到解时,记录下最后一个访问的状态值,然后从读取该状态对应的操作开始,就像栈操
作的退栈一样,不停往回搜,直到找到搜索起点为止。记录好栈退出来的操作值,就是一条路径。
算法设计:
基本设计(一个简单的类图如下)
ACM解题测试
Status表示可以不压缩(即直接用
char[]表示,因为看下来几个网站对内存要求都不高)。
哈希读取可以直接用
map(C++),HashMap(Java),速度不会慢的。
在每次取优先级最大的状态时,建议用
C++的
make_heap()。
检索策略及效果见下:
PKU
1077题:数据不强,用一点点技巧就能过
JAVA:
DFS,BFS超时
双向广搜
406MS,4904K
以
distance为
h'
()搜索
718MS,3056K
C++:双向广搜
46MS,
1252K
f
'
()=manhattan搜索
015MS,
276K左右
以
manhattan为
h'()搜索
265MS,376K
以
manhattan为
h'(),更新待检查队列
15MS,276K
IDA*
108MS,888K
杭州电子科技大学1043题:数据强了点f
'
()=manhattan搜索
2031ms,676K
f'
()=g'()+manhattan搜索
4031ms,708K
f'
()=g'()+5*manhattan搜索
3766ms,708K
f'
()=g'()+10*manhattan搜索
2515ms,708K
f'
()=g'()+15*manhattan搜索
4297ms,704K
f'
()=g'()+20*manhattan搜索4328ms,704K
ZJU
1217题:对时间好苛刻,在这里
makeheap()
能过
sort()就不能
_
o
只有纯以
manhattan为
f'
()搜索
AC了
00:05.07,900K
以
manhattan为
h'(),更新待检查队列
00:06.11,904K
惊讶
Ivan是如何以
00:00.11,396K过的(还有"绿野风烟")。
UVA
652题:看来功力不够啊~没有通过。
应用设计
首先,拒绝在
ACM试题中表现出色的
f
'
()=manhattan搜索,因为其搜索所得的结果太长了
(搜索深度过大),得不到最优解就宁可选择慢一点点的。
在我写的小八数码软件里,我用了普通广搜、双向广搜和
A*(f'()=g'
()+h'
())三个搜索
作比较。其中普通搜索的速度很慢,而且消耗内存较多。以下用三个搜索对进行搜索,情况如下:
用A算法解决八数码 问题
用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个 棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价 值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制 约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。
A star算法在静态路网中的应用 2.算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 )
实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 (一、)实验内容 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 (二、)基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{
int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成: (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数,就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析,8数码问题中可采用的搜速策略共有:1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索,一共五种。其中,广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 (三、)广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是,从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面。其搜索过程如图(1)所示。
用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个 棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有 一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给 出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动 棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数 得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。对于 几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的 方向进行。明显优于盲目搜索策略。
A star算法在静态路网中的应用 2.算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序}
1、实验目的 (1)熟悉人工智能系统中的问题求解过程; (2)熟悉状态空间中的盲目搜索策略; (3)掌握盲目搜索算法,重点就是宽度优先搜索与深度优先搜索算法。 2、实验要求 用VC语言编程,采用宽度优先搜索与深度优先搜索方法,求解8数码问题 3、实验内容 (1)采用宽度优先算法,运行程序,要求输入初始状态 假设给定如下初始状态S0 2 8 3 1 6 4 7 0 5 与目标状态Sg 2 1 6 4 0 8 7 5 3 验证程序的输出结果,写出心得体会。 (2)对代码进行修改(选作),实现深度优先搜索求解该问题 提示:每次选扩展节点时,从数组的最后一个生成的节点开始找,找一个没有被扩展的节点。这样也需要对节点添加一个就是否被扩展过的标志。 4 源代码及实验结果截图 #include
//八数码状态对应的节点结构体 struct Node{ int s[3][3];//保存八数码状态,0代表空格 int f,g;//启发函数中的f与g值 struct Node * next; struct Node *previous;//保存其父节点 }; int open_N=0; //记录Open列表中节点数目 //八数码初始状态 int inital_s[3][3]={ 2,8,3,1,6,4,7,0,5 }; //八数码目标状态 int final_s[3][3]={ 2,1,6,4,0,8,7,5,3 }; //------------------------------------------------------------------------ //添加节点函数入口,方法:通过插入排序向指定表添加 //------------------------------------------------------------------------ void Add_Node( struct Node *head, struct Node *p) { struct Node *q;
. 用盲目搜索技术解决八数码问题 题目 在3×3的棋盘,有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上 标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 算法流程 使用宽度优先搜索 从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜 索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面, 后进入的节点排在后面。 宽度优先算法如下: 把初始结点S0放入OPEN表中 若OPEN表为空,则搜索失败,问题无解 取OPEN表中最前面的结点N放在CLOSE表中,并冠以顺序编号n 若目标结点,则搜索成功,问题有解N?Sg若N无子结点,则转2 扩展结点N,将其所有子结点配上指向N的放回指针,依次放入OPEN表的尾部,转2 源程序 #include
using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist;//distance between one state and the destination 一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置} Node; Node src, dest;// 父节表目的表 vector
1、程序源代码 #include
一、实验目的 1、熟悉和掌握启发式搜索的定义、估价函数和算法过程。 2、利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验内容 以八数码为例实现A或A*算法。 1、分析算法中的OPEN表CLOSE表的生成过程。 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。 2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。 3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。 4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后更新队列尾指针。 5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。 2、分析估价函数对搜索算法的影响。
3、分析启发式搜索算法的特点。 广度优先搜索和双向广度优先搜索都属于盲目搜索,这在状态空间不大的情况下是很合适的算法,可是当状态空间十分庞大时,它们的效率实在太低,往往都是在搜索了大量无关的状态结点后才碰到解答,甚至更本不能碰到解答。 搜索是一种试探性的查寻过程,为了减少搜索的盲目性引,增加试探的准确性,就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估,从中选择最好、可能容易到达目标的位置,再从这个位置向前进行搜索,这样就可以在搜索中省略大量无关的结点,提高了效率。 启发式函数选取为:f*(n)=g*(n)+ h*(n) 其中: g*(n)是搜索树中节点n的深度 h*(n)用来计算对应于节点n的数据中错放的棋子个数。 三、实验结果
实验三:A*算法求解8数码问题实验 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验内容 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8,其中一个单元格是空的。将任意摆放的数码盘(城初始状态)逐步摆成某个指定的数码盘的排列(目标状态), 如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题,我们可以把数码的移动等效城空格的移动。如图1的
初始排列,数码7右移等于空格左移。那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。最少有两种(当空格位于方阵的4个角时)。所以,问题1 就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。 先定义下面几个函数的含义: f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值,f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示: f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。
人工智能实验一报告题目:采用A*算法解决八数码问题 姓名: XXX 学号: 10S003028 专业:计算机科学与技术 提交日期: 2011-05-04
目录 1问题描述........................................................................................................................... - 2 - 1.1待解决问题的解释............................................................................................... - 2 - 1.2问题的搜索形式描述............................................................................................ - 2 - 1.3解决方案介绍(原理)........................................................................................ - 3 - 2算法介绍........................................................................................................................... - 4 - 2.1A*搜索算法一般介绍............................................................................................ - 4 - 2.2 算法伪代码........................................................................................................... - 4 - 3算法实现........................................................................................................................... - 5 - 3.1 实验环境与问题规模........................................................................................... - 5 - 3.2 数据结构............................................................................................................... - 5 - 3.3 实验结果............................................................................................................... - 6 - 3.4系统中间及最终输出结果.................................................................................... - 6 - 4参考文献........................................................................................................................... - 7 - 5附录—源代码及其注释................................................................................................... - 7 -
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ,A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度,深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。
〈〈人工智能〉〉 题目:15数码问题 实验1: 要求: 采用广度优先算法解决15数码问题,输出扩展结点,步数和最终结果 算法描述: 广度优先搜索,即BFS(Breadth First Search),常常深度优先并列提及。这是一种相当常用的图算法,其特点是:每次搜索指定点,并将其所有未访问过的近邻加入搜索队列(而深度优先搜索则是栈),循环搜索过程直到队列为空。 广度优先搜索算法的基本思想:从初始状态出发,按照给定的结点产生式规则(算符、结点扩展规则)生产第一层结点,每生成一个结点就检查是不是目标结点,如果是目标结点就搜索结束,如果不是目标结点并且前面没出现过就保存该结点(入队列);再用产生式规则将所有第一层的结点依次扩展,得到第二层结点,同时检查是否为目标结点,是目标搜索停止,不是并且没出现过保存(入队);再把第二层的结点按产生规则扩展生产第三层结点,直至找到目标或所有的状态找完但找不到目标(队列空)。 特点:先生成深度为1的所有结点,再生产深度为2的所有结点,依次类推。先横向,再纵向。这种方法找到目标,需要的步数一定最少。
程序算法流程图: 描述: (1).把起始结点放到OPEN表中。 (2).如果OPEN表是个空表,则没有解,失败退出;否则继续。 (3).把第一个结点从OPEN表中移出,并把它放入CLOSE表的扩展节点表 中。 (4).扩展结点N。如果没有后继结点,则转向步骤(2)。 (5).把N的所有后继结点放到OPEN表的末端,并提供从这些后继结点回 到N的指针。 (6).如果N的任意个后继结点是个目标结点,则找到一个解答,成功退出; 否则转向步骤(2). 流程图:
A*算法求解八数码问题 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、 6、7、8,其中一个单元格是空的。将任意摆放的数码盘(城初始状态)逐步摆成某个 指定的数码盘的排列(目标状态),如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题,我们可以把数码的移动等效城空格的移动。如图1的初始排列,数码7右移等于空格左移。那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。最少有两种(当空格位于方阵的4个角时)。所以,问题就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。 先定义下面几个函数的含义:
f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值,f*(n)表示从初始节点s经过n到目标节点g 的最短路径的耗散值。 评价函数的形式可定义如(2)式所示: f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中,如果对所有的x, h(x)<=h*(x) (3) 成立,则称好h(x)为h*(x)的下界,它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。 针对八数码问题启发函数设计如下: f(n)=d(n)+p(n) (4) 其中A*算法中的g(n)根据具体情况设计为d(n),意为n节点的深度,而h(n)设计为
八数码问题分析 班级:计算机1041 学号:01 姓名:李守先 2013年9月26日
摘要 八数码问题(Eight-puzzle Problem )是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java 算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。 关键词 九宫重排, 状态空间, 启发式搜索, A*算法 1 引言 九宫重排问题(即八数码问题)是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则:空格周围的数移向空格,我们可以看作是空格移动,它最多可以有4个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。 图1 许多学者对该问题进行了有益的探索[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有9!=362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题:每个初始状态都存在解路径吗?文献给出了九宫重排问题是否有解的判别方法:九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解;否则问题无解。状态的逆序数是定义把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi 是第 i 个数之前比该数小的数字的个数,则 η=Σηi 是该状态的逆序数,图2说明了逆序数计算的过程 。 本文介绍用JAVA 编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性 ;
基于人工智能的状态空间搜索策略研究 ——八数码问题求解 (一)实验软件 TC2.0 或VC6.0编程语言或其它编程语言 (二)实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 (三)需要的预备知识 1. 熟悉TC 2.0或VC6.0 编程语言或者其它编程语言; 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法; 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用; 4. 熟悉计算机常用人机接口设计。 (四)实验数据及步骤 1. 实验内容 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法(深度优先搜索或宽度优先搜索)或任选一种启发式搜索方法(A 算法或A* 算法)编程求解八数码问题(初始状态任选),并对实验结果进行分析,得出合理的结论。 2. 实验步骤 (1)分析算法基本原理和基本流程; 程序采用宽度优先搜索算法,基本流程如下:
(2)确定对问题描述的基本数据结构,如Open表和Closed表等;
(3)编写算符运算、目标比较等函数; (4)编写输入、输出接口; (5)全部模块联调; (6)撰写实验报告。 (五)实验报告要求 所撰写的实验报告必须包含以下内容: 1. 算法基本原理和流程框图; 2. 基本数据结构分析和实现; 3. 编写程序的各个子模块,按模块编写文档,含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等; 4. 程序运行结果,含使用的搜索算法及搜索路径等; 5. 实验结果分析; 6. 结论; 7. 提供全部源程序及软件的可执行程序。 附:实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论
一、实验内容和要求 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如: [ (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN 表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; % 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为: f'(n) = g'(n) + h'(n) 这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数: f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已
知的。用f(n)作为f'(n)的近似,也就是用g(n)代替g'(n),h(n)代替h'(n)。这样必须满足两个条件:(1)g(n)>=g'(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下: & 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。 2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。 3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。 4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后更新队列尾指针。 5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。 四、程序框图
#include
人工智能实验报告 学院:信息科学与工程学院 班级:自动化0901班 学号: 06 姓名:孙锦岗 指导老师:刘丽珏 日期:2011年12月20日
一、实验名称、目的及内容 实验名称: 八数码难题的搜索求解演示 实验目的: 加深对图搜索策略概念的理解,掌握搜索算法。 实验内容要求: 以八数码难题为例演示广度优先或深度优先搜索、A算法(本实验使用的是广度优先搜索)的搜索过程,争取做到直观、清晰地演示算法。 八数码难题:在3 X 3方格棋盘上,分别放置了标有数字 123,4,5,6,7,8 的八张牌,初始状态SO,目标状态如图所示,可以 使用的操作有:空格上移,空格左移,空格右移,空格下移。试编一程序实现这一搜索过程。 二、实验原理及基本技术路线图 实验原理: 八数码问题中,程序产生的随机排列转换成目标共有两种可能,而且这两种不可能同时成立,也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个数组表示,例如{8,
7,1,5,2,6,3,4,0}其中0代表空格。它在奇序列位置上。 在这个数组中我们首先计算它能够重排列出来的结果,公式就是: E(F(X))=Y,其中F (X),就是一个数他前面比这个数小的数的个数,Y为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。 数据结构: 本实验使用的数据结构是队列,应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列,将初始结点入队,并设置队列头和尾指,然后取出队列(头指针所指)的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列,然后判断扩展出的新结点与队列中的结点是否重复,如果重复则,否则记录其父结点,并将它加入队列,更新队列尾指针,然后判断扩展出的结点是否是目标结点,如果是则显示路径,程序结束。否则如果队列头的结点可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步,知道扩展出的结点是目标结点结束,并显示路径。 算法分析: 九宫问题的求解方法就是交换空格(0)位置,直至到达目标位置为止。如图所示:
八数码问题C语言A星算法详细实验报告含代 码 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
一、实验内容和要求 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如: (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为: f'(n) = g'(n) + h'(n)
这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数: f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。用f(n)作为f'(n)的近似,也就是用g(n)代替 g'(n),h(n)代替h'(n)。这样必须满足两个条件:(1)g(n)>=g'(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下: 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。
《八数码问题》实验报告 一、实验目的: 熟练掌握启发式搜索A *算法。 二、实验内容: 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法,采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理: 1. 问题描述: 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述: 启发式搜索 (1)原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 (2)估价函数
计算一个节点的估价函数,可以分成两个部分: 1、 已经付出的代价(起始节点到当前节点); 2、 将要付出的代价(当前节点到目标节点)。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值,即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价; )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大,越趋向于宽度优先或等代价搜索;反之,)(*n h 的比重越大, 表示启发性能就越强。 (3)算法描述: ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。 (3)算法流程图: