啟發(fā)式搜索算法

1、人工智能基礎(chǔ)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：八數(shù)碼問題姓名：張俊學(xué)號：2220092333指導(dǎo)老師：鄧安生啟發(fā)式搜索算法實(shí)驗(yàn)內(nèi)容：使用啟發(fā)式搜索算法求解8數(shù)碼問題。編制程序?qū)崿F(xiàn)求解8數(shù)碼問題A*算法，采用估價(jià)函數(shù)f(n )= d (n )+卜:，p (n )其中：d (n)是搜索樹中結(jié)點(diǎn)n的深度；w(n)為結(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)；p(n)為 結(jié)點(diǎn)n的數(shù)據(jù)庫中每個(gè)棋子與其目標(biāo)位置之間的距離總和。分析上述中兩種估價(jià)函數(shù)求解8數(shù)碼問題的效率差別，給出一個(gè)是p(n)的上界的 h (n)的定義，并測試使用該估價(jià)函數(shù)是否使算法失去可采納性。實(shí)驗(yàn)?zāi)康氖炀氄莆諉l(fā)式搜索A *算法及其可采納性。實(shí)驗(yàn)原理八數(shù)碼問題是在

2、3行和3列構(gòu)成的九宮棋盤上放置數(shù)碼為1到8的8個(gè)棋盤，剩下一 個(gè)空格的移動來不斷改變棋盤的布局，求解這類問題的方法是：給定初始布局(即初始狀 態(tài))和目標(biāo)布局(即目標(biāo)狀態(tài))，定義操作算子的直觀方法是為每個(gè)棋牌制定一套可能的走 步上，下，左，右四種移動，再根據(jù)所定義的啟發(fā)式搜索函數(shù)在搜索過程中選擇最合適 的操作算子，得到最優(yōu)的路徑。源代碼#include #include #include #include #include #include #include /以上為 C+源文件using namespace std;static int space=0;int target9;class Ei

3、ghtNum/定 義一個(gè) EightNum 類public:int num9;int玲/初始狀態(tài)與目標(biāo)狀態(tài)相比，棋子錯(cuò)放個(gè)數(shù)int deap;/深 度int evalfun;/狀態(tài)的估價(jià)值EightNum *parent;以下為類內(nèi)成員函數(shù)的聲明EightNum(int nnum9);int get_evalfun();int get_deapfun();void eval_func(int id);int Canspread(int n);void Spreadchild(int n);void getnum(int num19);void setnum(int num19);void sh

4、ow(void);int operator =(EightNum& NewEightN);int operator =(int num29);int Shownum();-以下為EightNum類成員函數(shù)定義-class Stackprivate:EightNum * eightnum;public:Stack * next;EightNum * Minf();EightNum * Belong(EightNum * suc);void Putinto(EightNum * suc);EightNum:EightNum(int nnum9)/此 函數(shù)功能為：初始化 num； for(int i

5、=0;i9;i+)numi=nnumi;f=0;deap=0;parent=NULL;int EightNum:get_evalfun()return evalfun;int EightNum:get_deapfun()return deap;void EightNum:eval_func(int id)/此 函數(shù)為估價(jià)函數(shù)int i,qifa;qifa=0;switch(id)case 1:for(i=0;i9;i+)if(numi!=targeti)qifa+;break;case 2:int j, h1,h2;for(i=0;i9;i+)for(j=0j9;j+)if(numj=i)h1

6、=j;if(targetj=i)h2=j;qifa+=(int)(fabs(double)(h1/3 - h2/3) + fabs(double)(h1%3 - h2%3);break;case 3:int j, h1,h2;for(i=0;i9;i+)for(j=0;jparent=NULL) deap=0;else deap=this-parent-deap+1;evalfun=deap+f;int EightNum:Canspread(int n)/判斷空格”0”可否移動int i,flag = 0;for(i = 0;i numi = 0)break;switch(n)case 1:i

7、f(i/3 != 0)flag = 1;break;case 2:if(i/3 != 2)flag = 1;break;case 3:if(i%3 != 0)flag = 1;break;case 4:if(i%3 != 2)flag = 1;break;default:break;return flag ;void EightNum:Spreadchild(int n)/擴(kuò)展child節(jié)點(diǎn)的子節(jié)點(diǎn)int i,loc,qifa;for(i = 0;i numi = this-parent-numi;for(i = 0;i numi = 0)break;if(n=0)loc = i%3+(i/3

8、 - 1)*3;else if(n=1)loc = i%3+(i/3 + 1)*3;else if(n=2)elseloc = i%3+1+(i/3)*3;qifa = this-numloc;this-numi = qifa;this-numloc = 0;void EightNum:getnum(int num19)for(int i=0;i9;i+)num1i=numi;void EightNum:setnum(int num19)for(int i=0;i9;i+)numi=num1i;void EightNum:show()/輸出函數(shù)for(int i=0;i9;i+)coutnum

9、i;if(i+1)%3=0)coutn;coutparent-Shownum();this-show();coutendl;return n+1;int EightNum:operator =(EightNum& NewEightN)int compere=1;for(int i=0;i9;i+)if(numi!=NewEightN.numi)compere=0;break;if(compere=0) return 0;else return 1;-以下為分函數(shù)的定義-/判斷是否有解的函數(shù)int solve(int num9,int target9)int i,j;int num_con=0,

10、tar_con=0;for(i=0;i9;i+)for(j=0;ji;j+)if(numjnumi & numj!=0)num_con+;if(targetjnext;Stack * min = this-next;Stack * minp = this;EightNum * minx;while(qifa-next != NULL)if(qifa-next-eightnum-get_evalfun() eightnum-get_evalfun()min = qifa-next;minp = qifa;qifa = qifa-next;minx = min-eightnum;qifa = mi

11、np-next;minp-next = minp-next-next;free(qifa);return minx;判斷節(jié)點(diǎn)是否屬于OPEN表或CLOSED表EightNum * Stack:Belong(EightNum * suc)Stack * qifa = this- next ;if(qifa = NULL)return NULL;while(qifa != NULL)if(suc=qifa-eightnum)return qifa -eightnum;qifa = qifa-next;return NULL;/把節(jié)點(diǎn)存入OPEN或CLOSED表中void Stack:Putinto

12、(EightNum * suc)Stack * qifa;qifa =(Stack *) malloc(sizeof(Stack);qifa-eightnum = suc;qifa-next = this-next;this-next = qifa;int BelongProgram(EightNum * suc ,Stack *Open ,Stack *Closed ,EightNum goal,int m )EightNum * qifa = NULL;int flag = 0;if(Open-Belong(suc) != NULL) II (Closed-Belong(suc) != N

13、ULL)if(Open-Belong(suc) != NULL) qifa = Open-Belong(suc);else qifa = Closed-Belong(suc);flag=1;elseOpen-Putinto(suc);suc-eval_func(m);return flag;/擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)void Spread(EightNum * suc, Stack * Open, Stack * Closed, EightNum goal,int m)int i;EightNum * child;for(i = 0; i Canspread(i+1)space+;child = (

14、EightNum *) malloc(sizeof(EightNum);child-parent = suc;child-Spreadchild(i);child-eval_func(m);if(BelongProgram(child, Open, Closed, goal,m) /判斷子節(jié)點(diǎn)是否屬于OPEN 或 CLOSED 表free(child);執(zhí)行函數(shù)EightNum * Process(EightNum * org, EightNum goal, Stack * Open, Stack * Closed,int m)while(1)if(Open-next = NULL)retur

15、n NULL;EightNum * minf =Open-Minf();Closed-Putinto(minf);if(*minf)=goal)return minf;Spread(minf, Open, Closed, goal,m);-人*算法搜索函數(shù)-void A(int id,EightNum start,EightNum Target)EightNum * result;space=0;float time;Stack *Open = (Stack *) malloc(sizeof(Stack);Open-next = NULL;Stack *Closed = (Stack *) m

16、alloc(sizeof(Stack);Closed-next = NULL;clock_t startt,finisht;startt=clock();/開始時(shí)間start.eval_func(id);Open-Putinto(&start);result = Process(&start, Target, Open, Closed,id); 進(jìn)行剩余的操作coutn 搜索過程:nShownum()endl;finisht=clock();time=(float)(finisht-startt);coutendlid算法處理結(jié)果：所耗時(shí)間:；couttime;coutms,;cout所耗空間

17、:”；coutspace;cout塊,endlendl;-主函數(shù)-int main(void)/主 函數(shù)int i,j;int flag;int num9;int error;doerror=0;cout請輸入八數(shù)碼問題的初始狀態(tài)(0代表空格,“棋子”間用空格隔開):endl;for(i=0;inumi;for(j=0;ji;j+)if(numj=numi)flag=1;if(numi8|flag=1)error+;if(error!=0)cout輸入數(shù)據(jù)錯(cuò)誤!請重新輸入!endl;while(error!=0);/輸入八數(shù)碼問題的初始狀態(tài)(0代表空格，“棋子”間用空格隔開)；int erro

18、rl;doerror1=0;coutvv請輸入新的目標(biāo)狀態(tài)(用0代表空格，“棋子”間用空格隔開):endl;for(i=0;itargeti;for(j=0;ji;j+)if(targetj=targeti)flag=1;if(targeti9llflag=1)error1+;if(error1!=0)cout輸入數(shù)據(jù)錯(cuò)誤!請重新輸入!endl;while(error1!=0);/輸入八數(shù)碼問題的目標(biāo)狀態(tài)(用0代表空格,中間用空格隔開)；EightNum start(num),Target(target);int m=solve(num,target);/判斷初始狀態(tài)到目標(biāo)狀態(tài)是否有解，有解返回1，誤解返回0；