人工智能《啟發(fā)式搜索》實驗大作業(yè)

《人工智能》實驗大作業(yè)實驗題目：啟發(fā)式搜索一、實驗目的：熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程，并利用A算法求解九宮問題，理解求解流程和搜索順序。二、實驗方法：1.先熟悉啟發(fā)式搜索算法；2.用C、C++或JAVA 語言編程實現(xiàn)實驗內(nèi)容。三、實驗背景知識：1.估價函數(shù)在對問題的狀態(tài)空間進行搜索時，為提高搜索效率需要和被解問題的解有關的大量控制性知識作為搜索的輔助性策略。這些控制信息反映在估價函數(shù)中。估價函數(shù)的任務就是估計待搜索節(jié)點的重要程度，給這些節(jié)點排定次序。估價函數(shù)可以是任意一種函數(shù)，如有的定義它是節(jié)點x處于最佳路徑的概率上，或是x節(jié)點和目標節(jié)點之間的距離等等。在此，我們把估價函數(shù)f(n)定義為從初始節(jié)點經(jīng)過n節(jié)點到達目標節(jié)點的最小代價路徑的代價估計值，它的一般形式是：f(n)=g(n)+h(n)其中g(n)是從初始節(jié)點到節(jié)點n的實際代價，g(n)可以根據(jù)生成的搜索樹實際計算出來；h(n)是從n到目標節(jié)點的最佳路徑的代價估計，h(n)主要體現(xiàn)了搜索的啟發(fā)信息。2.啟發(fā)式搜索過程的特性（1）可采納性當一個搜索算法在最短路徑存在的時候能保證能找到它，我們就稱該算法是可采納的。所有A*算法都是可采納的。（2）單調(diào)性一個啟發(fā)函數(shù)h是單調(diào)的，如果對所有的狀態(tài)ni和nj，其中nj是ni的子孫，h(ni)-h(nj)≤cost(ni,nj),其中cost(ni,nj)是從ni到nj實際代價。目標狀態(tài)的啟發(fā)函數(shù)值為0，即h(Goal)=0.具有單調(diào)性的啟發(fā)式搜索算法在對狀態(tài)進行擴展時能保證所有被擴展的狀態(tài)的f值是單調(diào)遞增（不減）。（3）信息性比較兩個啟發(fā)策略h1和h2，如果對搜索空間中的任何一個狀態(tài)n都有h1(n)≤h2(n)，就說h2比h1具有更多的信息性。一般而言，若搜索策略h2比h1有更多的信息性，則h2比h1考察的狀態(tài)要少。但必須注意的是更多信息性需要更多的計算時間，從而有可能抵消減少搜索空間所帶來的益處。3.常用的啟發(fā)式搜索算法（1）局部擇優(yōu)搜索算法（瞎子爬山法）瞎子爬山法是最簡單的啟發(fā)式算法之一。該算法在搜索過程中擴展當前節(jié)點并估價它的子節(jié)點。最優(yōu)的子節(jié)點別選擇并進一步擴展；該子節(jié)點的兄弟節(jié)點和父節(jié)點都不再被保留。當搜索到達一種狀態(tài)，該狀態(tài)比它的所有子狀態(tài)都要好，則搜索停止。因此，該算法的估價函數(shù)可表示為f(n)=h(n)。在一個限定的環(huán)境下，瞎子爬山法可能會極大的提高搜索的效率，但是對整個搜索空間而言，可能得不到全局最優(yōu)解。（2）最好優(yōu)先搜索法（有序搜索法）該算法的估價函數(shù)采用f(n)=g(n)+h(n)，在搜索過程中算法使用OPEN表和CLOSE表來記錄節(jié)點信息：OPEN表中保留所有已生成而未考察的節(jié)點；CLOSE表中保留所有已訪問過的節(jié)點。算法在每一次搜索過程中都會對OPEN表中的節(jié)點按照每個節(jié)點的f值進行排序，選擇f值最小節(jié)點進行擴展。算法的描述如下：①把起始節(jié)點S放到OPEN表中，計算f(S),并把其值與節(jié)點S聯(lián)系起來。②若OPEN是個空表，則算法失敗退出，無解。③從OPEN表中選擇一個f值最小的節(jié)點i。結果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。④把節(jié)點i從OPEN表中移出，并把它放入到CLOSED的擴展節(jié)點表中。⑤若節(jié)點i是個目標節(jié)點，則成功退出，求得一個解。⑥擴展i，生成其全部后繼節(jié)點。對i的每個后繼節(jié)點j：計算f(j)。如果j既不在OPEN表中，也不在CLOSED表中，則用估價函數(shù)f將其添加到OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。如果j已則OPEN表中或CLOSED表中，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f的值。若新的f值較小，則以此值取代舊值。從j指向i，而不是指向它的父輩節(jié)點。若節(jié)點j在CLOSED表中，則把它移回OPEN表。⑦轉向②。四、實驗內(nèi)容：問題描述：用啟發(fā)式搜索方法求解下列九宮問題2831647512384765實驗原理啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。啟發(fā)中的估價是用估價函數(shù)表示的，如：最佳優(yōu)先搜索的最廣為人知的形式稱為A*搜索(發(fā)音為“A星搜索”).它把到達節(jié)點的耗散g(n)和從該節(jié)點到目標節(jié)點的消耗h(n)結合起來對節(jié)點進行評價：f(n)=g(n)+h(n)因為以g(n)給出了從起始節(jié)點到節(jié)點n的路徑耗散，而h(n)是從節(jié)點n到目標節(jié)點的最低耗散路徑的估計耗散值，因此f(n)=經(jīng)過節(jié)點n的最低耗散解的估計耗散.這樣，如果我們想要找到最低耗散解，首先嘗試找到g(n)+h(n)值最小的節(jié)點是合理的。可以發(fā)現(xiàn)這個策略不只是合理的:倘若啟發(fā)函數(shù)h(n)滿足一定的條件，A*搜索既是完備的也是最優(yōu)的。如果把A*搜索用于Tree-Search,它的最優(yōu)性是能夠直接分折的。在這種情況下，如果h(n)是一個可采納啟發(fā)式--也就是說，倘若h(n)從不會過高估計到達目標的耗散--A*算法是最優(yōu)的?？刹杉{啟發(fā)式天生是最優(yōu)的，因為他們認為求解問題的耗散是低于實際耗散的。因為g(n)是到達節(jié)點n的確切耗散，我們得到一個直接的結論：f(n)永遠不會高估經(jīng)過節(jié)點n的解的實際耗散。啟發(fā)算法有：蟻群算法，遺傳算法、模擬退火算法等，蟻群算法是一種來自大自然的隨機搜索尋優(yōu)方法，是生物界的群體啟發(fā)式行為，現(xiàn)己陸續(xù)應用到組合優(yōu)化、人工智能、通訊等多個領域。蟻群算法的正反饋性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性更使之具有極強的發(fā)展?jié)摿?。從?shù)值仿真結果來看，它比目前風行一時的遺傳算法、模擬退火算法等有更好的適應性。代碼#include<stdio.h>#include<malloc.h>structnode{ inta[3][3];//用二維數(shù)組存放8數(shù)碼inthx;//函數(shù)h（x）的值，表示與目標狀態(tài)的差距 structnode*parent;//指向父結點的指針 structnode*next;//指向鏈表中下一個結點的指針};inthx(ints[3][3]){ inti,j; inthx=0; intsg[3][3]={1,2,3,8,0,4,7,6,5}; for(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++;returnhx;}structnode*extend(node*ex){ inti,j,m,n;//循環(huán)變量 intt;//臨時替換變量 intflag=0; intx[3][3];//臨時存放二維數(shù)組 structnode*p,*q,*head;head=(node*)malloc(sizeof(node));//head p=head; q=head; head->next=NULL;//初始化 for(i=0;i<3;i++){ for(j=0;j<3;j++) if(ex->a[i][j]==0){ flag=1; break; }if(flag==1) break; }for(m=0;m<3;m++)//將ex->a賦給x for(n=0;n<3;n++) x[m][n]=ex->a[m][n];if(i-1>=0){ t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t; flag=0; for(m=0;m<3;m++)//將x賦給a for(n=0;n<3;n++) if(x[m][n]==ex->parent->a[m][n]) flag++; if(flag!=9){ q=(node*)malloc(sizeof(node)); for(m=0;m<3;m++)//將x賦給a for(n=0;n<3;n++) q->a[m][n]=x[m][n];q->parent=ex; q->hx=hx(q->a); q->next=NULL; p->next=q; p=p->next; } }for(m=0;m<3;m++)//將ex->a重新賦給x，即還原x for(n=0;n<3;n++) x[m][n]=ex->a[m][n]; if(i+1<=2){ t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;flag=0; for(m=0;m<3;m++) for(n=0;n<3;n++) if(x[m][n]==ex->parent->a[m][n]) flag++; if(flag!=9){ q=(node*)malloc(sizeof(node)); for(m=0;m<3;m++)//將x賦給a for(n=0;n<3;n++) q->a[m][n]=x[m][n];q->parent=ex; q->hx=hx(q->a); q->next=NULL; p->next=q; p=p->next; } } for(m=0;m<3;m++)//將ex->a重新賦給x，即還原x for(n=0;n<3;n++) x[m][n]=ex->a[m][n]; if(j-1>=0){ t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t; flag=0; for(m=0;m<3;m++) for(n=0;n<3;n++) if(x[m][n]==ex->parent->a[m][n]) flag++; if(flag!=9){ q=(node*)malloc(sizeof(node)); for(m=0;m<3;m++)//將x賦給a for(n=0;n<3;n++) q->a[m][n]=x[m][n];q->parent=ex; q->hx=hx(q->a); q->next=NULL; p->next=q; p=p->next; } } for(m=0;m<3;m++) for(n=0;n<3;n++) x[m][n]=ex->a[m][n]; if(j+1<=2){ t=x[i][j];x[i][j]=x[i][j+1];x[i][j+1]=t; flag=0; for(m=0;m<3;m++) for(n=0;n<3;n++) if(x[m][n]==ex->parent->a[m][n]) flag++; if(flag!=9) {q=(node*)malloc(sizeof(node)); for(m=0;m<3;m++) for(n=0;n<3;n++) q->a[m][n]=x[m][n];q->parent=ex; q->hx=hx(q->a); q->next=NULL; p->next=q; p=p->next; } }head=head->next; returnhead;}node*insert(node*open,node*head){ node*p,*q; inti,j; intflag=0; if(open==NULL){ open=head; q=head; head=head->next; q->next=NULL; if(head->hx<open->hx){ open=head; head=head->next; open->next=q; }else{ q->next=head; head=head->next; q=q->next; q->next=NULL; p=open; } p=open; q=open->next; } while(head!=NULL){ q=open; if(head->hx<open->hx){ open=head; head=head->next; open->next=q; continue; }else{q=q->next;p=open;}//否則，q指像第二個結點，p指向q前一個結點 while(q->next!=NULL){ if(q->hx<head->hx){ q=q->next; p=p->next; }else{ p->next=head; head=head->next; p->next->next=q; break; } } if(q->next==NULL){//將head的一個結點插入到表尾 if(q->hx>head->hx){ p->next=head; head=head->next; p->next->next=q; }else{ q->next=head; head=head->next; q->next->next=NULL; } } } returnopen;}voidmain(){ inti,j; nodes0;node*open,*close; node*p,*q; node*newlist; printf("請輸入初始狀態(tài)的8數(shù)碼（按每行從左往右依次輸入,用0表示空格）：\n");for(i=0;i<3;i++) for(j=0;j<3;j++) scanf("%d",&s0.a[i][j]);s0.parent=(node*)malloc(sizeof(node)); s0.parent->hx=9;s0.hx=hx(s0.a); open=&s0;