人工智能大作业.doc

人工智能基础
大作业
—－－－八数码难题
　学院：数学与计算机科学学院
　　 　班级：计科14—1
　 　　 　 　 姓名:王佳乐
　 　 　 学号：１2
　 　 　 　 　 　 　　　　 2０1６、12、20
一、 实验名称
八数码难题得启发式搜索
二、 实验目得
八数码问题:在3×3得方格棋盘上,摆放着1到８这八个数码,有1个方格就是空得，其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移与空格下移这四个操作使得棋盘从初始状态到目标状态.
要求：1、熟悉人工智能系统中得问题求解过程;
2、熟悉状态空间得启发式搜索算法得应用；
3、熟悉对八数码问题得建模、求解及编程语言得应用。
三、 实验设备及软件环境
1. 实验编程工具：VC＋+　6、0
2. 实验环境：Wｉndoｗs7 64位
四、 实验方法：启发式搜索
1、算法描述
1. 将Ｓ放入open表,计算估价函数f(ｓ)
2. 判断oｐeｎ表就是否为空，若为空则搜索失败,否则，将opeｎ表中得第一个元素加入cｌｏse表并对其进行扩展（每次扩展后加入ｏpen表中得元素按照代价得大小从小到大排序，找到代价最小得节点进行扩展）
注:代价得计算公式ｆ(n)=d（ｎ）+ｗ（n)、其中f（n)为总代价，d(n）为节点得度,w（ｎ)用来计算节点中错放棋子得个数.
判断i就是否为目标节点,就是则成功，否则拓展i，计算后续节点f（j），利用f（j)对oｐeｎ表重新排序
2、算法流程图：

3、程序源代码：
＃ ｉncluｄｅ＜stdｉｏ、ｈ>
#　iｎclude＜strｉng、h>
# include
# iｎclude〈stｄliｂ、ｈ＞
tyｐeｄef　ｓtruct nodｅ　｛
ﻩint i,cost,ｄeｇree，eｘp，fａthｅr；
ﻩｉnt a［3]［３];
ﻩｓtｒｕct nｏde ＊bef，＊late；
strucｔ node ＊ｓｏn；
｝treeｎode；
int fｌａg=0，cｏuｎｔ=1,nuｍ＝0,ｉ＝０；
vｏｉｄ set(treｅnodｅ ＊s)；
vｏid cpynoｄe（ｔreenode ＊s１，ｔreenｏde ＊ｓ2）;
void add1（tｒeenode ＊ｓ，treeｎodｅ ＊open)；
vｏid adjｕst1（tｒeｅｎode ＊clｏｓe);
void　jscost（ｔrｅeｎｏde ＊s);
voiｄ　tｉaｏzｈeｎg（tｒｅenｏdｅ *opｅn）;
ｖoid sortoｐen（ｔｒeeｎoｄe ＊opｅn)；
iｎt test(treenode ＊s1,treenｏdｅ ＊s2）;
vｏiｄ posｉtion（treｅnodｅ *s,treeｎｏdｅ *oｐen，treenode ＊ｃｌose，tｒeenｏｄe ＊s1）；
void ｐrintstｒ(ｔreｅnode ＊ｏpen);
iｎｔ　ｓeａrｃｈ（ｔrｅenｏde ＊s１，tｒeeｎode ＊s2）;
voｉd input(ｔrｅｅnode *s）;
ｉnt cmpnode（treenｏdｅ ＊ｓ1,tｒeenode ＊s2)；
void ｐｒｉnt(treｅnｏｄe　＊ｓ）;
ｖｏｉd add(treenoｄｅ ＊s,tｒeenode *ｃlosｅ）；

void　xuhao（tｒeeｎｏdｅ ＊s）；
voｉd extenｄ(treeｎode ＊r1，trｅeｎodｅ ＊s，ｔrｅｅｎodｅ *s1,tｒeｅｎode *open,ｔrｅenodｅ ＊clｏsｅ）；
voiｄ main（） {
tｒｅenodｅ　*s0，*s1，*s；
ﻩtrｅeｎode ＊open,＊cloｓe，＊ｏpｅnd,＊cｌoｓｅd；
opeｎ=(ｔreenｏde＊)mａlｌoc(ｓizｅof（tｒeenｏde)）;
cｌosｅ=(ｔｒeeｎodｅ＊)ｍａｌlｏc(sizeof（trｅenｏdｅ））;
　　ｏpen－＞ｌate=ＮULL；
ﻩclose-＞latｅ＝ＮULＬ;
ﻩopeｎd=oｐen；
ﻩclosed=ｃlose；
ﻩｓ0=(treenoｄｅ*)malloｃ（sizeof（treｅnｏde））;
ｓｅt (ｓ0）；
ﻩs1=(tｒeeｎode＊)mallｏc(sizeof（treenodｅ）)；
ｓeｔ(s1）；
prｉｎｔｆ（＂请输入八数码得初始状态：（以空格为分隔）\n”）；
iｎpｕt （ｓ0）;
prｉntｆ(＂请输入八数码得目标状态　:(以空格为分隔)\ｎ”)；
input(ｓ1）;
xuhao（s0）；
ﻩadd （s0，oｐend)；
ﻩwhｉlｅ（opｅｎ—>late！=NULＬ ＆＆ flａg==0） ｛
ﻩ ｓ=(treeｎｏｄｅ*）mａlloc（siｚeｏf（treenodｅ））；
ﻩ　 ｃpynode（ｓ，ｏpen-〉ｌａte）；
ﻩoｐen=opeｎ—〉laｔe；
ﻩ add（s，clｏse）；
ﻩ if(tｅst(s,s1)==0){
ﻩ ﻩｆlag=1；ﻩ}
eｌｓe｛
pｏｓitioｎ（s，open,close,s1)；
ﻩ sｏrtｏpen(oｐen）; };};
ﻩif（open-〉ｌate!＝NULL) {
ﻩﻩprｉntf（"搜索过程如下:＼n ＂）;
ﻩ 　ａdｊuｓt1（ｃｌosｅ)；
ﻩﻩpｒintstr（cｌosｅ);
printf("\n%d 步，％ｄ 个节点\ｎ"，num,cｏuｎt）;｝
ﻩelｓe {
ﻩﻩpｒinｔｆ("查找错误 ! \n＂）；}; ｝
ｖoid sｅt（treenｏdｅ *ｓ) ｛
ｓ—〉i=i;
s—＞fａtheｒ=０；
ﻩs－＞ｄｅｇrｅe=0；
ｓ—〉beｆ＝NULL；
s-＞sｏｎ＝NＵLL；
ﻩｓ－〉lａte=NULL; ｝；
void inpuｔ（tｒｅenode ＊s） {
inｔ j，k;
ﻩｆor（j＝0；ｊ〈３;j++）
ﻩﻩfｏr（k=0;k<３；k++）
ﻩﻩ scaｎｆ（＂％d＂，&s—>a［j］［k］）; };
int cmpnoｄe（treenode *s1,ｔrｅenｏde *s2）{
ﻩint j,k;
ｆor(j=0；j<3；j++)
ﻩ for(ｋ=0；k〈3;k++) {
ﻩﻩ if（s１—〉a［ｊ］[k］!=s2—>a[j］[k]）
ﻩ ﻩ return 0; }；
ﻩretuｒｎ　1; ｝
inｔ ｔｅst（tｒeenoｄe *s1,treeｎode ＊s２) ｛
int j,k，ｎ=0;
ｆｏr(j＝0；ｊ＜3；j++）
ﻩﻩfor（ｋ=0；k〈3；k＋+) ｛
ﻩ if（ｓ１－〉a[j］［k］！=s2-〉a［j]［k]）
ﻩﻩ ﻩｎ++； };
ｓ1-〉exp＝n;
retｕｒn n; }；
ｖｏid ｘuhａo（tｒeｅnｏdｅ *ｓ） ｛
ﻩi++;
ｓ—〉i=i；　}
void　cpynode(treenｏde　*s1，ｔｒｅｅnodｅ　*s２)　{
ﻩ inｔ j，ｋ；
ﻩｆoｒ（ｊ=0;j<3;ｊ＋＋）
ﻩ for（ｋ=0；k＜３;k+＋）
ﻩﻩs1—〉a［j][k］=s2-＞ａ［j][k];
s1—〉bef=ｓ2—＞bｅf；
ｓ１-〉ｃost＝s２-〉ｃosｔ;
s１－〉ｅxp=s2－＞exp;
ﻩs１—〉degreｅ＝s２->degreｅ；
ﻩs1—＞i=ｓ２—>i;
s1->fａther=s２—>father; ｝;
void　prinｔ(tｒeeｎode *s） ｛
ﻩiｎt j，k；
ﻩfor（j=０;ｊ<３;ｊ+＋) {
ﻩ for(k=0;k＜3;k++） ｛
ﻩﻩ 　 ｐriｎtf(”％2d"，ｓ－＞ａ［ｊ］[ｋ］）； }
ﻩﻩｉf(j==1）　 pｒintｆ（＂ n=％2d ｄ=％2ｄ ｆ=％2d”,ｓ—>ｉ，s-〉degrｅe，ｓ-〉father）；
printf（＂\n"）; ｝
ﻩprintｆ（"\ｎ＂）; }
void　poｓｉｔｉoｎ(tｒｅeｎode ＊s，ｔrｅenode *opeｎ，ｔreeｎoｄe *clｏsｅ,treｅｎｏde ＊s1) ｛
ﻩｉｎｔ m,n,t,ｋ；
treenodｅ *r1；
ﻩfoｒ（m=０;m＜3;m＋+) {
ﻩ fｏｒ（n=0;ｎ〈3；n++） ｛
ﻩﻩｋ＝s—〉a[m][n］;
ﻩﻩif（k=＝０)
ﻩﻩﻩｂrｅaｋ; ｝；
ﻩif(k＝=0） bｒeak; }
ﻩｉf（m+1＜=2&＆flag==０)ﻩ{
ﻩ ｒ１=(treenoｄe＊)malloｃ（sizeof（ｔｒeｅｎode））; 　
ﻩ cpynodｅ(r1,s)；
ﻩﻩt=r1－>a[m+1］[n］；
　 r1—〉a[m+1]［n]　＝ r1-＞a［ｍ］[ｎ］;
r1—＞a［m］[n]=t;
ﻩeｘtｅnd（r1，ｓ,s1，opeｎ,cｌｏse）； };
iｆ（ｍ－1＞=0＆＆fｌａg＝=０）ﻩ{
ﻩ ｒ１＝(trｅeｎodｅ*）ｍａllｏc(sizｅｏf（treenoｄe）);
ﻩ 　　cpyｎｏde(r1，s）;
ﻩ t=ｒ1—>a［m—1］[n];
ﻩ 　 r１—＞a[ｍ-1］［n］=ｒ1-＞a[m］［ｎ］；
　 r１->ａ［m]［n］=t；
exｔｅnd（r1，s，s1,open，close); };
ﻩif（n－1〉＝0 &&　fｌａg＝=０）　｛
ﻩﻩｒ1＝（treｅnｏde＊）maｌloｃ(ｓizeof(treｅｎodｅ)）;
　　　ﻩcpyｎodｅ(r1,s)；
ﻩ ｔ=r１－>a[ｍ］［n－1］；
ﻩ 　 r１—＞a[m］［n－１]=r１—>a［m］［n］；
ﻩ r1-〉a［m］［n]＝t；
ﻩﻩextｅnd（r1，s，s1,open，clｏse）；　｝;
ﻩif（n+1〈＝2　&＆ ｆlａg=＝0）　｛
ﻩ r１=(tｒeenoｄｅ＊）malloc（sizeｏｆ（ｔreenｏde)）；
　 　cpｙnｏｄｅ(r1，ｓ）；
ﻩﻩt=r1-＞a［m］[n+1]；
　 　r1－〉a［ｍ][n+1]=r1－＞a［m][n]；
　 ｒ１->a［m］[n］=t；
ﻩextend(r1，s，ｓ1，oｐen，close）； }； }
vｏid prinｔstr(treｅnode *s) ｛
ﻩｔｒeｅnode ＊ｔ;
ﻩt＝s－〉late;
ﻩwhiｌｅ（t！＝NULL） ｛
ﻩ num++；
print（t）;
ﻩﻩｔ=t->ｓon; ｝； ｝
void ｅxｔend（trｅenode *r１，ｔreeｎｏde ＊s，treｅｎｏde ＊s1，trｅeｎoｄｅ ＊ｏpeｎ,trｅenoｄe ＊close)　｛
ﻩ r1—〉fatｈer=ｓ—>i
r1-＞dｅｇreｅ=s—＞degｒｅｅ+1;
ﻩﻩif（test（r１，s1）!=０) ｛
ﻩ ﻩjsｃｏｓt(r１）；
ｉf(searｃh（ｒ1,clｏsｅ）＝=1　&＆　ｓeａrcｈ（r1，oｐen）==1) {
ﻩxuhａｏ(ｒ1）;
ﻩadd1（ｒ1，oｐen）；
ﻩr1—〉bef=s；
ﻩﻩﻩ count＋＋; }
ﻩ ｅlse frｅe（r1)；　}
ｅlse {
ﻩ xｕhao（r1）;
ﻩﻩﻩjsｃost（r1)；
ﻩ cｏuｎt++;
ﻩ ﻩadd(r１，clｏse）；
ﻩﻩr１—〉ｂeｆ=s；
flａg=1； ｝　}
inｔ　sｅarch（treenodｅ ＊s1，ｔｒeeｎoｄｅ *clｏse）　{
ﻩｔｒｅenodｅ *r,＊t；
ﻩr＝s１；
ｔ=clｏsｅ－>late；
ﻩwｈｉle(t！=ＮULL)　｛
ﻩﻩiｆ(r—〉exp==t—〉exp） {
ﻩif（ｃmpnode（r,t）==１）
ﻩretuｒｎ ０； ｝;
ﻩﻩt=ｔ—>ｌate；　｝;
reｔuｒｎ 1; }
voiｄ ａdｄ（ｔｒｅenoｄe　*ｓ,treenoｄe ＊ｃloｓe) {
ﻩtreenoｄe　*r,*t；
ﻩt＝s；
r=ｃlｏse;
ﻩｗhile(ｒ—>late！=NULL)
ﻩr＝r—＞late;
r－>lａtｅ=t;
t—〉latｅ=NＵＬL； ｝
vｏｉd ａｄd1(treｅnｏde　*s,ｔreeｎode ＊open）｛
ﻩｔrｅenode ＊t；
ﻩt=oｐen；
s-＞laｔｅ＝t->ｌatｅ;
ﻩt-〉laｔe=s； ｝
vｏid　adjｕst1(tｒeｅnode　*closｅ） {
ｔreenode ＊s,＊t；
ﻩs=close;
s—>laｔe－>bef=ＮULL;
ﻩwhile(ｓ—〉late！=NULL)
s＝s—〉laｔｅ;
s－>ｓon=NULL；
ｗhiｌe(s->bef!=ＮUＬL) {
ﻩﻩt=ｓ->bｅf；
t－〉son=s；
ｓ=s->bｅf； ｝; }
ｖｏid jscｏst(treenodｅ *s） {
ｓ－>cosｔ=（ｓ-〉ｅxｐ)+s－〉degｒeｅ；　｝
ｖoid ｓortopeｎ（treｅnｏｄｅ *ｏpeｎ） ｛
ﻩtreｅnode *t，*s，*r；
ﻩinｔ ｋ;
r=(tｒeeｎode*）ｍalloｃ（ｓizeoｆ(tｒeenode)）;
t=oｐｅn-〉late；
ﻩwhile（ｔ！＝ＮＵLL　＆＆ t—＞late！=ＮＵＬL）　｛
ﻩﻩs=t-＞lａｔe；
ﻩﻩk＝t－>coｓｔ；
ﻩﻩﻩwhｉle(s!=NULL） ｛
ｉf（k ＞ s—>ｃoｓt） {
ﻩ ﻩk=ｓ—>cｏｓｔ；
ﻩ cpynoｄe(ｒ，t)；
ﻩ ﻩ cpynｏde（t,ｓ）;
ﻩ ﻩcpｙnｏdｅ(s,ｒ）；　｝
s＝ｓ-＞lａtｅ; ｝
ﻩﻩﻩt=t－>laｔｅ; }; }
五、 实验结果：
１、程序截图

2、搜索过程
请输入八数码得初始状态:(以空格为分隔)ﻫ２ 8 ３
1 0 4
7 ６ ５
请输入八数码得目标状态 ：（以空格为分隔）
１ 2 3
8 0 4
7 ６ ５ﻫ搜索过程如下：ﻫ 　2 ８ 3ﻫ 1 0 ４ n= 1 d= 0 ｆ＝ 0ﻫ 7 6 5ﻫ
 2 0 3ﻫ 1 8 ４ n＝ ３ d= 1 f＝ １
 7 6 5
ﻫ 0 2 3
 1 8 4 n= 8 d= ２ f＝ ３
 7 ６ ５

 1 2 3ﻫ ０ ８ 4 ｎ=10 ｄ= 3 f= 8ﻫ 7 6 ５

 １ ２ 3
 ８ ０ ４ n=1２ ｄ= 4 f=10
 ７ ６ ５ﻫﻫ
5 步,12 个节点ﻫPｒess aｎy key to continuｅ
六、 实验分析：
在进行搜索得过程中，同时记录了扩展新节点得个数。启发式搜索仅扩展12个新节点。可见,在本实验中启发式搜索更优,效率更高。而在求解最短路径得问题上盲目搜索能更高效一点.在实际得应用中应根据具体情况灵活选择不同得策略,提高程序执行效率
启发式搜索就就是在状态空间中得搜索对每一个搜索得位置进行评估,得到最好得位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓得搜索路径，提高了效率。
七、 结论
此次实验用启发式搜索方法求解问题得使用，让我们明白了具体问题具体分析，更明白了算法得重要，好得算法能够极大得提高程序得运行效率。同时,通过此次实践,也对课本知识有了更深刻得认识与体会，真正将课本知识融于实践中就是对我们得最大考验。
这次试验让我更加深入了解了什么就是人工智能，让我了解了人工智能得作用以及含义与人工智能得使用范围以及对于我们未来生活得作用得广大.用机器语言解决实际问题得,提高了动手能力。