啟發(fā)式搜索介紹八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個空格（以數(shù)字0來表示），與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態(tài)和一個目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動棋子步數(shù)最少的移動步驟。所謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。使用啟發(fā)式搜索算法求解8數(shù)碼問題。A，A星算法采用估價函數(shù)，其中：是搜索樹中結(jié)點的深度；為結(jié)點的數(shù)據(jù)庫中錯放的棋子個數(shù)；為結(jié)點的數(shù)據(jù)庫中每個棋子與其目標(biāo)位置之間的距離總和。寬度搜索采用f(i)為i的深度，深度搜索采用f(i)為i的深度的倒數(shù)。算法流程把起始節(jié)點S放到OPEN表中，并計算節(jié)點S的；如果OPEN是空表，則失敗退出，無解；從OPEN表中選擇一個值最小的節(jié)點。如果有幾個節(jié)點值相同，當(dāng)其中有一個為目標(biāo)節(jié)點時，則選擇此目標(biāo)節(jié)點；否則就選擇其中任一個節(jié)點作為節(jié)點；把節(jié)點從OPEN表中移出，并把它放入CLOSED的已擴(kuò)展節(jié)點表中；如果是個目標(biāo)節(jié)點，則成功退出，求得一個解；擴(kuò)展節(jié)點，生成其全部后繼節(jié)點。對于的每一個后繼節(jié)點：計算；如果既不在OPEN表中，又不在CLOCED表中，則用估價函數(shù)把它添入OPEN表中。從加一指向其父節(jié)點的指針，以便一旦找到目標(biāo)節(jié)點時記住一個解答路徑；如果已在OPEN表或CLOSED表中，則比較剛剛對計算過的和前面計算過的該節(jié)點在表中的值。如果新的較小，則(I)以此新值取代舊值。(II)從指向，而不是指向他的父節(jié)點。(III)如果節(jié)點在CLOSED表中，則把它移回OPEN表中。轉(zhuǎn)向②，即GOTO②。估價函數(shù)計算一個節(jié)點的估價函數(shù)，可以分成兩個部分：已經(jīng)付出的代價（起始節(jié)點到當(dāng)前節(jié)點）；將要付出的代價（當(dāng)前節(jié)點到目標(biāo)節(jié)點）。節(jié)點n的估價函數(shù)定義為從初始節(jié)點、經(jīng)過n、到達(dá)目標(biāo)節(jié)點的路徑的最小代價的估計值，即=+。是從初始節(jié)點到達(dá)當(dāng)前節(jié)點n的實際代價；是從節(jié)點n到目標(biāo)節(jié)點的最佳路徑的估計代價，體現(xiàn)出搜索過程中采用的啟發(fā)式信息（背景知識），稱之為啟發(fā)函數(shù)。所占的比重越大，越趨向于寬度優(yōu)先或等代價搜索；反之，的比重越大，表示啟發(fā)性能就越強(qiáng)。實驗代碼為方便起見，目標(biāo)棋局為不變(1)以下代碼估價函數(shù)為深度+錯放棋子個數(shù)(2)若估價函數(shù)為深度+每個棋子與其目標(biāo)位置之間的距離總和，則加入估價函數(shù)intcalvalue1(inta[])//不在位棋子數(shù){ intc=0;intb=0; for(inti=0;i<=8;i++)for(intj=0;j<=8;j++)if(a[i]=goal[j]) if(goal[j]!=0)c=c+abs(i%3-j%3)+abs((i-i%3)/3+(j-j%3)/3); returnc;}(3)寬度搜索采用OPEN->jiedian.f=depth;(4)深度搜索采用OPEN->jiedian.f=-depth;源代碼：#include"stdio.h"intgoal[9]={1,2,3,8,0,4,7,6,5},sgoal[9];//goal為棋盤的目標(biāo)布局,并用中間狀態(tài)sgoal與之比較 { if(OPEN->next)//如果還有節(jié)點 { OPEN=OPEN->next; OPEN->previous=NULL; } elseOPEN=NULL;//否則置為空 } if(TEMP->jiedian.shuzu[0]-1>=0&&TEMP->jiedian.e!=2)//防止棋子回到原狀態(tài) OPEN=addnode(OPEN,newnode(TEMP,depth,1)); if(TEMP->jiedian.shuzu[0]+1<=8&&TEMP->jiedian.e!=1) OPEN=addnode(OPEN,newnode(TEMP,depth,2)); if(TEMP->jiedian.shuzu[0]-3>=0&&TEMP->jiedian.e!=4) OPEN=addnode(OPEN,newnode(TEMP,depth,3)); if(TEMP->jiedian.shuzu[0]+3<=8&&TEMP->jiedian.e!=3) OPEN=addnode(OPEN,newnode(TEMP,depth,4)); depth++; } if(OPEN)//如有解,則打印出解的步驟 { TEMP->path=NULL; while(TEMP->parent)//每次回溯父節(jié)點，生成路徑 { TEMP->parent->path=TEMP; TEMP=TEMP->parent; } j=0; while(TEMP->path) { setboard(sgoal,TEMP->jiedian.shuzu,1); printf("第%d步：\n",j); for(i=0;i<=2;i++) printf("%d",sgoal[i]); printf("\n"); for(i=3;i<=5;i++) printf("%d",sgoal[i]); printf("\n"); for(i=6;i<=8;i++) printf("%d",sgoal[i]); printf("\n"); TEMP=TEMP->path; j++; } setboard(sgoal,TEMP->jiedian.shuzu,1); printf("第%d步：\n",j); for(i=0;i<=2;i++) printf("%d",sgoal[i]); printf("\n"); for(i=3;i<=5;i++) printf("%d",sgoal[i]); printf("\n"); for(i=6;i<=8;i++) printf("%d",sgoal[i]); printf("\n"); } else printf("無法求解！");}(1)以上代碼估價函數(shù)為深度+錯放棋子個數(shù)(2)若估價函數(shù)為深度+每個棋子與其目標(biāo)位置之間的距離總和，則函數(shù)改為intcalvalue(inta[])//不在位棋子數(shù){ intc=0;intb=0; for(inti=0;i<=8;i++)for(intj=0;j<=8;j++)if(a[i]=goal[j]) if(goal[j]!=0)c=c+abs(i%3-j%3)+abs((i-i%3)/3+(j-j%3)/3); returnc;}(3)寬度搜索采用OPEN->jiedian.f=depth;(4)深