[教學(xué)]人工智能實驗大作業(yè)

1、? 人工智能 ?實驗大作業(yè)實驗題目： 啟發(fā)式搜索 專業(yè) 信息與計算科學(xué) 年級 091001 姓名 賈凡 學(xué)號 091001103 指導(dǎo)老師 時華 日 期 2021年12月11日 一、實驗?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價函數(shù)和算法過程，并利用算法求解九宮問題，理解求解流程和搜索順序。二、實驗方法：1.先熟悉啟發(fā)式搜索算法； 2.用C、C+或JV語言編程實現(xiàn)實驗內(nèi)容。三、實驗背景知識：在對問題的狀態(tài)空間進(jìn)行搜索時，為提高搜索效率需要和被解問題的解有關(guān)的大量控制性知識作為搜索的輔助性策略。這些控制信息反映在估價函數(shù)中。估價函數(shù)的任務(wù)就是估計待搜索節(jié)點(diǎn)的重要程度，給這些節(jié)點(diǎn)排定次序。估價函數(shù)可以

2、是任意一種函數(shù)，如有的定義它是節(jié)點(diǎn)x處于最正確路徑的概率上，或是x節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離等等。在此，我們把估價函數(shù)(n)定義為從初始節(jié)點(diǎn)經(jīng)過n節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價路徑的代價估計值，它的一般形式是： (n) = g(n) + h(n)其中g(shù)(n)是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的實際代價，g(n)可以根據(jù)生成的搜索樹實際計算出來；h(n)是從n到目標(biāo)節(jié)點(diǎn)的最正確路徑的代價估計，h(n)主要表達(dá)了搜索的啟發(fā)信息。2. 啟發(fā)式搜索過程的特性1可采納性當(dāng)一個搜索算法在最短路徑存在的時候能保證能找到它，我們就稱該算法是可采納的。所有*算法都是可采納的。2單調(diào)性一個啟發(fā)函數(shù)h是單調(diào)的，如果a） 對所有的狀態(tài)n

3、i和 nj，其中nj是ni的子孫，h(ni )- h(nj )cost(ni,nj ),其中cost(ni,nj )是從ni到nj 實際代價。b） 目標(biāo)狀態(tài)的啟發(fā)函數(shù)值為0，即h(Gol)=0.具有單調(diào)性的啟發(fā)式搜索算法在對狀態(tài)進(jìn)行擴(kuò)展時能保證所有被擴(kuò)展的狀態(tài)的值是單調(diào)遞增不減。3信息性比擬兩個啟發(fā)策略h1和h2，如果對搜索空間中的任何一個狀態(tài)n都有h1(n) h2(n)，就說h2比h1具有更多的信息性。一般而言，假設(shè)搜索策略h2比h1有更多的信息性，那么h2比h1考察的狀態(tài)要少。但必須注意的是更多信息性需要更多的計算時間，從而有可能抵消減少搜索空間所帶來的益處。1局部擇優(yōu)搜索算法瞎子爬山法瞎

4、子爬山法是最簡單的啟發(fā)式算法之一。該算法在搜索過程中擴(kuò)展當(dāng)前節(jié)點(diǎn)并估價它的子節(jié)點(diǎn)。最優(yōu)的子節(jié)點(diǎn)別選擇并進(jìn)一步擴(kuò)展；該子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)都不再被保存。當(dāng)搜索到達(dá)一種狀態(tài)，該狀態(tài)比它的所有子狀態(tài)都要好，那么搜索停止。因此，該算法的估價函數(shù)可表示為(n) = h(n)。在一個限定的環(huán)境下，瞎子爬山法可能會極大的提高搜索的效率，但是對整個搜索空間而言，可能得不到全局最優(yōu)解。2最好優(yōu)先搜索法有序搜索法該算法的估價函數(shù)采用(n) = g(n) + h(n)，在搜索過程中算法使用OPEN表和CLOSE表來記錄節(jié)點(diǎn)信息：OPEN表中保存所有已生成而未考察的節(jié)點(diǎn)；CLOSE表中保存所有已訪問過的節(jié)點(diǎn)。算法

5、在每一次搜索過程中都會對OPEN表中的節(jié)點(diǎn)按照每個節(jié)點(diǎn)的值進(jìn)行排序，選擇值最小節(jié)點(diǎn)進(jìn)行擴(kuò)展。算法的描述如下： 把起始節(jié)點(diǎn)S放到OPEN表中，計算(S),并把其值與節(jié)點(diǎn)S聯(lián)系起來。 假設(shè)OPEN是個空表，那么算法失敗退出，無解。 從OPEN表中選擇一個值最小的節(jié)點(diǎn)i。結(jié)果有幾個節(jié)點(diǎn)合格，當(dāng)其中有一個為目標(biāo)節(jié)點(diǎn)時，那么選擇此目標(biāo)節(jié)點(diǎn)，否那么就選擇其中任一個節(jié)點(diǎn)作為節(jié)點(diǎn)i 。 把節(jié)點(diǎn)i從OPEN表中移出，并把它放入到CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 假設(shè)節(jié)點(diǎn)i是個目標(biāo)節(jié)點(diǎn)，那么成功退出，求得一個解。 擴(kuò)展i，生成其全部后繼節(jié)點(diǎn)。對i的每個后繼節(jié)點(diǎn)j：（a） 計算(j)。（b） 如果j既不在OPEN表中，

6、也不在CLOSED表中，那么用估價函數(shù)將其添加到OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時記住一個解答路徑。（c） 如果j已那么OPEN表中或CLOSED表中，那么比擬剛剛對j計算過的值和前面計算過的該節(jié)點(diǎn)在表中的的值。假設(shè)新的值較小，那么（i） 以此值取代舊值。（ii） 從j指向i，而不是指向它的父輩節(jié)點(diǎn)。（iii） 假設(shè)節(jié)點(diǎn)j在CLOSED表中，那么把它移回OPEN表。 轉(zhuǎn)向。四、實驗內(nèi)容：問題描述：用啟發(fā)式搜索方法求解以下九宮問題283164 7512384 7655、 實驗原理啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進(jìn)行評估，得到最好的位置，再從這個位

7、置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。啟發(fā)中的估價是用估價函數(shù)表示的，如：最正確優(yōu)先搜索的最廣為人知的形式稱為*搜索(發(fā)音為“星搜索).它把到達(dá)節(jié)點(diǎn)的耗散g(n)和從該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的消耗h(n)結(jié)合起來對節(jié)點(diǎn)進(jìn)行評價：(n)=g(n)+h(n)因為以g(n)給出了從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的路徑耗散，而h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的估計耗散值，因此(n)=經(jīng)過節(jié)點(diǎn)n的最低耗散解的估計耗散.這樣，如果我們想要找到最低耗散解，首先嘗試找到g(n)+h(n)值最小

8、的節(jié)點(diǎn)是合理的?？梢园l(fā)現(xiàn)這個策略不只是合理的:倘假設(shè)啟發(fā)函數(shù)h(n)滿足一定的條件，*搜索既是完備的也是最優(yōu)的。如果把*搜索用于Tree-Serch,它的最優(yōu)性是能夠直接分折的。在這種情況下，如果h(n)是一個可采納啟發(fā)式-也就是說，倘假設(shè)h(n)從不會過高估計到達(dá)目標(biāo)的耗散-*算法是最優(yōu)的?？刹杉{啟發(fā)式天生是最優(yōu)的，因為他們認(rèn)為求解問題的耗散是低于實際耗散的。因為g(n)是到達(dá)節(jié)點(diǎn)n確實切耗散，我們得到一個直接的結(jié)論：(n)永遠(yuǎn)不會高估經(jīng)過節(jié)點(diǎn)n的解的實際耗散。啟發(fā)算法有： 蟻群算法，遺傳算法、模擬退火算法等，蟻群算法是一種來自大自然的隨機(jī)搜索尋優(yōu)方法，是生物界的群體啟發(fā)式行為，現(xiàn)己陸續(xù)應(yīng)用

9、到組合優(yōu)化、人工智能、通訊等多個領(lǐng)域。蟻群算法的正反應(yīng)性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性更使之具有極強(qiáng)的開展?jié)摿?。從?shù)值仿真結(jié)果來看，它比目前風(fēng)行一時的遺傳算法、模擬退火算法等有更好的適應(yīng)性。6、 代碼#include <stdio.h>#include<mlloc.h>struct nodeint 33;/用二維數(shù)組存放8數(shù)碼 int hx;/函數(shù)hx的值，表示與目標(biāo)狀態(tài)的差距struct node *prent;/指向父結(jié)點(diǎn)的指針struct node *next;/指向鏈表中下一個結(jié)點(diǎn)的指針;int hx(int s33)int i,j;int hx=0

10、;int sg33=1,2,3,8,0,4,7,6,5;or(i=0;i<3;i+)or(j=0;j<3;j+)i(sij!=sgij)hx+; return hx;struct node *extend(node *ex)int i,j,m,n; /循環(huán)變量int t; /臨時替換變量int lg=0; int x33;/臨時存放二維數(shù)組struct node *p,*q,*hed; hed=(node *)mlloc(sizeo(node);/hedp=hed;q=hed;hed->next=NULL;/初始化or(i=0;i<3;i+)or(j=0;j<3;

11、j+)i(ex->ij=0)lg=1;brek;i(lg=1)brek; or(m=0;m<3;m+)/將ex->賦給xor(n=0;n<3;n+)xmn=ex->mn; i(i-1>=0)t=xij;xij=xi-1j;xi-1j=t; lg=0;or(m=0;m<3;m+)/將x賦給 or(n=0;n<3;n+) i(xmn=ex->prent->mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node); or(m=0;m<3;m+)/將x賦給 or(n=0;n<3;n+) q->

12、;mn=xmn; q->prent=ex; q->hx=hx(q->); q->next=NULL; p->next=q; p=p->next; or(m=0;m<3;m+)/將ex->重新賦給x，即復(fù)原xor(n=0;n<3;n+)xmn=ex->mn;i(i+1<=2)t=xij;xij=xi+1j;xi+1j=t; lg=0;or(m=0;m<3;m+) or(n=0;n<3;n+) i(xmn=ex->prent->mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(n

13、ode); or(m=0;m<3;m+)/將x賦給 or(n=0;n<3;n+) q->mn=xmn; q->prent=ex; q->hx=hx(q->); q->next=NULL; p->next=q; p=p->next; or(m=0;m<3;m+)/將ex->重新賦給x，即復(fù)原xor(n=0;n<3;n+)xmn=ex->mn;i(j-1>=0) t=xij;xij=xij-1;xij-1=t;lg=0;or(m=0;m<3;m+) or(n=0;n<3;n+) i(xmn=ex->

14、;prent->mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node); or(m=0;m<3;m+)/將x賦給 or(n=0;n<3;n+) q->mn=xmn; q->prent=ex; q->hx=hx(q->); q->next=NULL; p->next=q; p=p->next; or(m=0;m<3;m+)or(n=0;n<3;n+)xmn=ex->mn;i(j+1<=2) t=xij;xij=xij+1;xij+1=t; lg=0;or(m=0;m<3;

15、m+) or(n=0;n<3;n+) i(xmn=ex->prent->mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node); or(m=0;m<3;m+) or(n=0;n<3;n+) q->mn=xmn; q->prent=ex; q->hx=hx(q->); q->next=NULL; p->next=q; p=p->next; hed=hed->next;return hed;node* insert(node *open,node * hed)node *p,*q;in

16、t i,j;int lg=0;i(open=NULL) open=hed;q=hed; hed=hed->next;q->next=NULL; i(hed->hx<open->hx)open=hed;hed=hed->next;open->next=q;else q->next=hed; hed=hed->next; q=q->next; q->next=NULL; p=open;p=open;q=open->next;while(hed!=NULL)q=open;i(hed->hx<open->hx)

17、open=hed;hed=hed->next;open->next=q;continue;else q=q->next;p=open; /否那么，q指像第二個結(jié)點(diǎn)，p指向q前一個結(jié)點(diǎn)while(q->next!=NULL) i(q->hx<hed->hx) q=q->next;p=p->next;elsep->next=hed;hed=hed->next;p->next->next=q; brek;i(q->next=NULL) /將hed的一個結(jié)點(diǎn)插入到表尾i(q->hx>hed->hx)p

18、->next=hed;hed=hed->next;p->next->next=q;elseq->next=hed;hed=hed->next;q->next->next=NULL;return open; void min()int i,j;node s0; node *open,*close;node *p,*q;node *newlist;print("請輸入初始狀態(tài)的8數(shù)碼按每行從左往右依次輸入,用0表示空格：n"); or(i=0;i<3;i+)or(j=0;j<3;j+)scn("%d",&s0.ij); s0.prent=(node *)mlloc(sizeo(node);s0.prent->hx=9; s0.hx=hx(s0.);open=&s0;p=&s0;i(open->hx=0)print("該狀態(tài)已為最終狀態(tài)！n");return;q=&s0;close=&s0;open=