【正文】 se 39。N39。} return false。二 實(shí)驗(yàn)?zāi)康?熟悉和掌握遺傳算法的基本概念和基本思想； 理解和掌握遺傳算法的各個(gè)操作算子，能夠用選定的編程語(yǔ)言設(shè)計(jì)簡(jiǎn)單的遺傳優(yōu)化系統(tǒng)； 通過(guò)實(shí)驗(yàn)培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問(wèn)題求解的基本技能。//基因的排列（即城市的順序，路徑的組織）int adapt。//基因的排列（即城市的順序，路徑的組織）int adapt。在進(jìn)行遺傳操作和種群進(jìn)化的時(shí)候，每個(gè)染色體的適應(yīng)值是決定它是否進(jìn)入下一輪種群進(jìn)化的關(guān)鍵因素。采用的選擇、交叉、變異操作算子的具體操作1）選擇操作我們定義f(xi)為第i（i=1,2,3.....popsize）個(gè)染色體的適應(yīng)度，則每個(gè)個(gè)體被選中的概率popsizefor(i=0。}RanSeTi [i].adapt=sumdistance。i} gradient[0]=group[0].p。} } } //拷貝種群for(i=0。i{point1=rand()%cities。break。}//進(jìn)行基因交配if(point1point2)//保證point1{temp=point1。memset(map2,1,sizeof(map2))。}//斷點(diǎn)兩邊的基因互換for(k=0。}for(k=point2+1。}//處理產(chǎn)生的沖突基因for(k=0。}}for(k=point2+1。}}for(k=0。}}for(k=point2+1。}}temp1=temp2+1。i{bianyip[i]=(rand()%100)。i{if(bianyip[i]{bianyiflag[i]=1。i{if(bianyiflag[i]==1){temp1=rand()%10。group[i].city[temp2]=point。(4)按概率Pc進(jìn)行交叉操作。成功找到種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。但是遺傳算法可以考慮到的問(wèn)題復(fù)雜度更高，更適合應(yīng)用于實(shí)際。因而應(yīng)在學(xué)習(xí)之后及時(shí)進(jìn)行上機(jī)實(shí)驗(yàn)，并且達(dá)到熟練掌握與運(yùn)用的階段。w(n)，f(n)=d(n)+237。⑵ 分析上述⑴中兩種估價(jià)函數(shù)求解8數(shù)碼問(wèn)題的效率差別，給出一個(gè)是p(n)的上界的h(n)的定義，并測(cè)試使用該估價(jià)函數(shù)是否使算法失去可采納性。double f,g。數(shù)碼數(shù)組：記錄棋局?jǐn)?shù)碼擺放狀態(tài)。局部搜索樹(shù)樣例：*搜索過(guò)程搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過(guò)劣質(zhì)節(jié)點(diǎn)）。內(nèi)存泄漏。}Node,*Lnode。Node * Minf(Lstack * Open){//選取OPEN表上f值最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)地址Lstack temp =(*Open)next,min =(*Open)next,minp =(*Open)。}temp = tempnext。free(temp)。i 9。amp。 goaldata[j]!= 0)b++。i 9。if(temp == NULL)return NULL。}void Putinto(Node * suc,Lstack * list){//把節(jié)點(diǎn)放入OPEN 或CLOSED 表中Stack * temp。(*list)next = temp。return w+。i p = p + Distance(suc, goal, i)。}}int error(Node suc,Node goal){//計(jì)算錯(cuò)位個(gè)數(shù)int w,i。} return w。k++){if([k] == i)h1 = k。int flag = 0。tempg =(*suc)g。(*suc)f = Fvalue(**suc, goal, m)。i 9。case 2:if(i/3!= 2)flag = 1。case 4:if(i%3!= 2)flag = 1。}void Spreadchild(Node * child,int n){//擴(kuò)展child節(jié)點(diǎn)的字節(jié)點(diǎn)n表示方向，表示空格向上向下向左向右移int i,loc,temp。for(i = 0。else if(n==1)loc = i%3+(i/3 + 1)*3。childdata[i] = temp。for(i = 0。//算子節(jié)點(diǎn)的g值childparent =(*suc)。} } } ///////////////////////擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)結(jié)束//////////////////////////////////Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m){//總執(zhí)行函數(shù)while(1){if((*Open)next == NULL)return NULL。//如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則成功退出Spread(amp。printf(“第%d步：”,n)。for(int j = 0。}}printf(“n”)。while(i 9){while(((c = getchar())!= 10)){if(c == 39。039。039。j i。}elseif(flag = 0)flag =1。i = 0。s=snext。Lstack Closed =(Stack *)malloc(sizeof(Stack))。//初始狀態(tài)節(jié)點(diǎn)orgf =1。int m。printf(“說(shuō)明:狀態(tài)矩陣由08 九個(gè)數(shù)字表示,n請(qǐng)依次按照九宮格上的行列順序輸入,每個(gè)數(shù)字間用空格隔開(kāi)。Checkinput(org)。scanf(“%d”,amp。Putinto(org,amp。goal, amp。printf(“n”)。printf(“Press Enter key to exit!”)。，掌握基于規(guī)則推理的基本方法。，能根據(jù)輸入的動(dòng)物特征判斷是那種動(dòng)物或給出相應(yīng)的回答。為了便于設(shè)計(jì)，我們把要識(shí)別的動(dòng)物限于7種，這樣所需要的產(chǎn)生式規(guī)則就比較少。216。216。系統(tǒng)的推理過(guò)程如下：先從規(guī)則庫(kù)中取出第一條規(guī)則R1，檢查其前提是否可與事實(shí)庫(kù)中的已知事實(shí)相匹配。下面是程序運(yùn)行的結(jié)果：【實(shí)驗(yàn)程序】include define N 23 void main(){int i,j,k,a,b,c。while(flag==1){ printf(“動(dòng)物的特征如下:n”)。num)。iif(fact[i]==1)scanf(“%d”,amp。num++。amp。break。事實(shí)為: 哺乳。k++。num++。for(i=0。fact[i]=a。for(i=0。printf(“請(qǐng)輸入描述該動(dòng)物特征的個(gè)數(shù):”)。int fact[N],temp[N]。此時(shí)，事實(shí)庫(kù)的內(nèi)容變?yōu)椋河杏鹈⑸骑w、不怕風(fēng)浪、鳥；此后，R4~R14均匹配失敗，接著取R15，該前提“善飛+不怕風(fēng)浪+鳥”與已知事實(shí)相匹配，R15被執(zhí)行，并推出“該動(dòng)物是海燕”。如有多條匹配規(guī)則需從中選一條作為使用規(guī)則，本算法是根據(jù)規(guī)則的順序依次選擇，且規(guī)則中不存在同一組事實(shí)對(duì)應(yīng)多條匹配規(guī)則。216。推理過(guò)程是： 216。如果未識(shí)別出來(lái)，則可以重新選擇，或者退出。在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部分：用事實(shí)表示靜態(tài)知識(shí)；用產(chǎn)生式規(guī)則表示推理過(guò)程和行為。} elseprintf(“程序認(rèn)定該起始狀態(tài)無(wú)法道達(dá)目標(biāo)狀態(tài)!n”)。printf(“擴(kuò)展節(jié)點(diǎn)數(shù)：n”)。Closed, m)。result = Process(amp。while((c = getchar())!= 10)。Checkinput(goal)。printf(“=================================n”)。int k。Node * goal =(Node *)malloc(sizeof(Node))。Node * org =(Node *)malloc(sizeof(Node))。}void main(){//主函數(shù)//初始操作，建立open和closed表Lstack Open =(Stack *)malloc(sizeof(Stack))。} } }int meassure(Lstack s){ int k=0。else if(flag ==2)printf(“輸入的數(shù)字有重復(fù)!n請(qǐng)重新輸入:n”)。i++。flag = 1。amp。){if(flag = 0)flag = 0。} }void Checkinput(Node *suc){//檢查輸入int i = 0,j = 0,flag = 0。j++){if(resultdata[i*3+j]!= 0)printf(“ %d ”,resultdata[i*3+j])。i 3。//當(dāng)前節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)時(shí)擴(kuò)展當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)} }int Shownum(Node * result){//遞歸顯示從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的移動(dòng)方法if(result == NULL)return 0。//從OPEN表中取出f值最小的節(jié)點(diǎn)Putinto(minf, Closed)。//向該方向移動(dòng)空格生成子節(jié)點(diǎn)if(BelongProgram(amp。i++){if(Canspread(**suc, i+1))//判斷某個(gè)方向上的子節(jié)點(diǎn)可否擴(kuò)展{child =(Node *)malloc(sizeof(Node))。}void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m){//擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)int i。elseloc = i%3+1+(i/3)*3。i++)if(childdata[i] == 0)break。i 9。default:break。case 3:if(i%3!= 0)flag = 1。switch(n){ case 1:if(i/3!= 0)flag = 1。}int Canspread(Node suc, int n){//判斷空格可否向該方向移動(dòng)，表示空格向上向下向左向右移int i,flag = 0。flag = 1。else temp = Belong(*suc,Closed)。} return double(fabs(h1/3h2%3))。for(k = 0。for(i=0。//f = h + g。double p = 0。int w=0。tempnpoint = suc。temp = tempnext。return 1。else return 0。if((goaldata[i] goaldata[j])amp。j i。}int Canslove(Node * suc, Node * goal){//判斷是否可解int a = 0,b = 0,i,j。temp = minpnext。while(tempnext!= NULL){if((tempnextnpointf)npointf)){min = tempnext。struct Stack * next。double f,g?，F(xiàn)存在的一些優(yōu)缺點(diǎn)。父節(jié)點(diǎn)：指向父親節(jié)點(diǎn)。//父節(jié)點(diǎn) }Node,*Lnode。該搜索為一個(gè)搜索樹(shù)。238。⑴ 編制程序?qū)崿F(xiàn)求解8數(shù)碼問(wèn)題A*算法，采用估價(jià)函數(shù)236。但一旦應(yīng)用于實(shí)踐時(shí)，發(fā)現(xiàn)雖然每個(gè)部分模塊自己都可以理解并且熟悉，但是對(duì)于實(shí)際應(yīng)用，并且切實(shí)地解決實(shí)際問(wèn)題仍存在較大的困難。通過(guò)每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。(6)沒(méi)有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)；(7)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。要求說(shuō)明是否搜索到了最優(yōu)解，如果沒(méi)有，請(qǐng)分析原因本題中根據(jù)隨機(jī)生成的cities個(gè)城市之間的相互距離、隨機(jī)產(chǎn)生初試群，通過(guò)TSP算法，通過(guò)以下步驟：(1)初始化群體。point=group[i].city[temp1]。}}//變異操作,即交換染色體的兩個(gè)節(jié)點(diǎn)srand((unsigned)time(NULL))。}//確定可以變異的染色體t=0。//隨機(jī)產(chǎn)生變異概率srand((unsigned)time(NULL))。kkif(group[temp2].city[k]==group[temp2].city[kk]){group[temp2].city[k]=map2[group[temp2].city[k]]。kkif(group[temp2].city[k]==group[temp2].city[kk]){group[temp2].city[k]=map2[group[temp2].city[k]]。kkif(group[temp1].city[k]==group[temp1].city[kk]){group[temp1].city[k]=map1[group[temp1].city[k]]。kkif(group[temp1].city[k]==group[temp1].city[kk]){group[temp1].city[k]=map1[group[temp1].city[k]]。group[temp1].city[k]=group[temp2].city[k]。group[temp1].city[k]=group[temp2].city[k]。k{map1[group[temp1].city[k]]=group[temp2].city[k]。point2=temp。jif(jiaopeiflag[j]==1){temp2=j。for(j=t