昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告〔2013——2014學(xué)年第一學(xué)期〕課程名稱：人工智能導(dǎo)論開(kāi)課實(shí)驗(yàn)室：信自樓234室2013年11月5日年級(jí)、專業(yè)、班學(xué)號(hào)姓名成績(jī)實(shí)驗(yàn)工程名稱狀態(tài)空間搜索實(shí)驗(yàn)—八數(shù)碼問(wèn)題求解指導(dǎo)教師教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理：A.了解□B.根本了解□C.不了解□該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ篈.強(qiáng)□B.中等□C.差□該同學(xué)的實(shí)驗(yàn)是否到達(dá)要求：A.到達(dá)□B.根本到達(dá)□C.未到達(dá)□實(shí)驗(yàn)報(bào)告是否標(biāo)準(zhǔn)：A.標(biāo)準(zhǔn)□B.根本標(biāo)準(zhǔn)□C.不標(biāo)準(zhǔn)□實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄：A.詳細(xì)□B.一般□C.沒(méi)有□教師簽名：年月日一、實(shí)驗(yàn)問(wèn)題1、用軟件編程解決八數(shù)碼問(wèn)題二、實(shí)驗(yàn)?zāi)康?、熟悉人工智能求解八數(shù)碼問(wèn)題，以及對(duì)人工智能深入了解。2、熟悉狀態(tài)空間的盲目搜索、啟發(fā)式搜索，和A*算法。3、熟悉人工智能系統(tǒng)中的問(wèn)題求解過(guò)程。三、實(shí)驗(yàn)原理1、將初始節(jié)點(diǎn)s放入open表中2、假設(shè)open表為空那么推出3、移出open表中的第一個(gè)節(jié)點(diǎn)N放入close表中，并冠以順序編號(hào)n，4、假設(shè)目標(biāo)節(jié)點(diǎn)Sg=N，那么搜索成功，結(jié)束5、假設(shè)N不可擴(kuò)展，那么轉(zhuǎn)入第2步四、程序框圖StartStart把S放入open表中判斷open表是否為空表YESEND把open表的第一個(gè)節(jié)點(diǎn)移到close表中擴(kuò)展節(jié)點(diǎn)n，把其后裔放入open表前面是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)YESENDNO五、實(shí)驗(yàn)結(jié)果及分析1、通過(guò)逆序數(shù)的奇數(shù)偶數(shù)來(lái)判斷。因?yàn)樵诳瞻滓苿?dòng)過(guò)程中，數(shù)碼的逆序數(shù)不改變。左右移動(dòng)，數(shù)碼序列不變。上下移動(dòng)，數(shù)碼序列中某個(gè)數(shù)字那么移動(dòng)了兩位。八數(shù)碼問(wèn)題為3*3矩陣，3為奇數(shù)，故逆序數(shù)不作改變。故可通過(guò)判斷當(dāng)前狀態(tài)S的逆序數(shù)以及目標(biāo)狀態(tài)的數(shù)字序列的逆序數(shù)的奇偶性是否相同來(lái)判斷該問(wèn)題是否可解。2、是否到達(dá)目標(biāo)節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)進(jìn)行比擬3、對(duì)于f(n)的考慮，f〔n〕是否最小，選擇最小的擴(kuò)展，假設(shè)幾個(gè)相等的狀態(tài)同時(shí)出現(xiàn)，那么隨機(jī)選一個(gè)。4、將Open表中的所有節(jié)點(diǎn)進(jìn)行排序選擇估價(jià)函數(shù)f(n)最優(yōu)的進(jìn)行擴(kuò)展。第二種選擇就是選擇當(dāng)前層擴(kuò)展的節(jié)點(diǎn)中選擇最優(yōu)的f(n)進(jìn)行擴(kuò)展。六、結(jié)論1、盡管明白怎么樣解決八數(shù)碼問(wèn)題，但用電腦編程還是不會(huì)編。雖然學(xué)過(guò)C語(yǔ)言，由于不用也生疏了。以后對(duì)學(xué)過(guò)的只是溫故而知新。2、通過(guò)本次試驗(yàn)我對(duì)啟發(fā)式搜索有了更加深入的了解。在實(shí)驗(yàn)中通過(guò)對(duì)兩種啟發(fā)式搜索所擴(kuò)在的節(jié)點(diǎn)數(shù)來(lái)看更加有效能在復(fù)雜情況下求得更加優(yōu)質(zhì)的解防止不必要的節(jié)點(diǎn)的擴(kuò)展。使搜索的速度更快。3、八數(shù)碼的啟發(fā)式搜索、A算法等用書面的形式很容易表示出來(lái)，但用計(jì)算機(jī)能讀懂的語(yǔ)言〔如C語(yǔ)言〕表示，這個(gè)轉(zhuǎn)換的的過(guò)程很困難。七、源程序及注釋#include<stdio.h>#include<conio.h>intn,m;typedefstructNode{charmatrix[10];/*存儲(chǔ)矩陣*/charoperate;/*存儲(chǔ)不可以進(jìn)行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/charextend;/*是否可以擴(kuò)展，Y代表可以，N代表不可以*/intfather;/*指向產(chǎn)生自身的父結(jié)點(diǎn)*/}Node;charstart[10]={"83426517"};charend[10]={"12384765"};Nodebase[4000];intresult[100];/*存放結(jié)果的base數(shù)組下標(biāo)號(hào)，逆序存放*/intmatch()/*判斷是否為目標(biāo)*/{inti;for(i=0;i<9;i++){if(base[n-1].matrix[i]!=end[i]){return0;}}return1;}voidshow()/*顯示矩陣的內(nèi)容*/{inti=1;while(m>=0){intmm=result[m]; //clrscr();printf("\n\n\n狀態(tài)方格\t\t步驟%d",i); printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]); printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]); printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);//sleep(1);m--;i++;}}voidleave()/*推理成功后退出程序之前要執(zhí)行的函數(shù)，主要作用是輸出結(jié)果*/{n--;while(base[n].father!=-1){result[m]=n;m++;n=base[n].father;}result[m]=0;result[m+1]='\0';show();//clrscr();printf("\n\n\n\n\n\n\n\n\n\t\t\t\t搜索結(jié)束\n\n\n\n\n\n\n\n\n\n");getch();//exit(0);}intleft(intx)/*把下標(biāo)為X的數(shù)組中的矩陣的空格左移*/{inti,j;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==3||i==6||i==9){return0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-1];base[n].matrix[i-1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='R';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intright(intx)/*把下標(biāo)為X的數(shù)組中的矩陣的空格右移*/{inti,j;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==2||i==5||i==8||i==9){return0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+1];base[n].matrix[i+1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='L';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return1;}intup(intx)/*把下標(biāo)為X的數(shù)組中的矩陣的空格上移*/{inti,j;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==0||i==1||i==2||i==9){return0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-3];base[n].matrix[i-3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='D';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i)) leave(); return1;}intdown(intx)/*把下標(biāo)為X的數(shù)組中的矩陣的空格下移*/{inti,j;charch;for(i=0;i<9;i++){if(base[x].matrix[i]=='')break;}if(i==6||i==7||i==8||i==9){return0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+3];base[n].matrix[i+3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='U';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i)) leave();return1;}main(){inti;chara[20],b[20];n=1;/*以下是輸入初始和目標(biāo)矩陣，并把輸入的0轉(zhuǎn)換為空格*/printf("3*3方格初始狀態(tài):");scanf("%s",a);printf("3*3方格結(jié)束狀態(tài):");scanf("%s",b);for(i=0;i<9;i++){if(a[i]=='0'){start[i]='';continue;}if(b[i]=='0'){end[i]='';continue;}start[i]=a[i];end[i]=b[i];}start[9]='\0';end[9]='\0';for(i=0;i<9;i++){base[0].matrix[i]=start[i];}base[0].operate='N';base[0].extend='Y';base[0].father=-1;/*以上是為第一個(gè)base數(shù)組元素賦值*/for(i=0;n<4000;i++){if(base[i].extend=='Y'){if(base[i].operate=='L'){right(i);up(i);down(i);}if(base[i].operate=='R'){left(i);