【正文】 group[temp2].city[k]。group[temp2].city[k]=temp。}//處理產(chǎn)生的沖突基因for(k=0。k{for(kk=point1。kkif(group[temp1].city[k]==group[temp1].city[kk]){group[temp1].city[k]=map1[group[temp1].city[k]]。break。}}for(k=point2+1。k{for(kk=point1。kkif(group[temp1].city[k]==group[temp1].city[kk]){group[temp1].city[k]=map1[group[temp1].city[k]]。break。}}for(k=0。k{for(kk=point1。kkif(group[temp2].city[k]==group[temp2].city[kk]){group[temp2].city[k]=map2[group[temp2].city[k]]。break。}}for(k=point2+1。k{for(kk=point1。kkif(group[temp2].city[k]==group[temp2].city[kk]){group[temp2].city[k]=map2[group[temp2].city[k]]。break。}}temp1=temp2+1。} 3）變異操作TSP問題中，經(jīng)常采取的變異操作主要有：位點變異、逆轉(zhuǎn)變異、對換變異、插入變異。//隨機(jī)產(chǎn)生變異概率srand((unsigned)time(NULL))。for(i=0。i{bianyip[i]=(rand()%100)。bianyip[i]/=100。}//確定可以變異的染色體t=0。for(i=0。i{if(bianyip[i]{bianyiflag[i]=1。t++。}}//變異操作,即交換染色體的兩個節(jié)點srand((unsigned)time(NULL))。for(i=0。i{if(bianyiflag[i]==1){temp1=rand()%10。temp2=rand()%10。point=group[i].city[temp1]。group[i].city[temp1]=group[i].city[temp2]。group[i].city[temp2]=point。}} 實驗中采用的算法參數(shù)的最佳選擇值是多少define cities 10/30 //城市的個數(shù)define MAXX 150 //迭代次數(shù) define pc //交配概率 define pm //變異概率 define num 20 //種群的大小六 實驗結(jié)果 要求有實驗運(yùn)行結(jié)果截圖，以及必要的說明以上部分是每次迭代的步驟結(jié)果，通過染色體群體中個體的交配、變異，從而更改染色體的具體基因組成，通過不斷進(jìn)行適應(yīng)度計算、存活率的計算，更新已有數(shù)值；以上部分為迭代之后的總結(jié)果，輸出最終的種群評價，從染色體種群里面取出最佳的染色體，并進(jìn)行輸出。要求說明是否搜索到了最優(yōu)解，如果沒有，請分析原因本題中根據(jù)隨機(jī)生成的cities個城市之間的相互距離、隨機(jī)產(chǎn)生初試群，通過TSP算法，通過以下步驟：(1)初始化群體。(2)計算群體上每個個體的適應(yīng)度值。(4)按概率Pc進(jìn)行交叉操作。(5)按概率Pm進(jìn)行變異操作。(6)沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)；(7)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。(3)按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體。成功找到種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。若失敗，分析可得失敗原因為：隨機(jī)生成的cities個城市之間的相互距離、隨機(jī)產(chǎn)生初試群有可能不存在適應(yīng)度值最優(yōu)的染色體七 實驗總結(jié)及體會：對于此類旅行者問題，原在數(shù)據(jù)結(jié)構(gòu)和算法課中學(xué)過迪杰斯特拉算法，也可以高效快速的解決給定好初值的最短路徑問題；在本課中，有學(xué)到了新的算法：TSP算法，此算法從遺傳學(xué)角度，開辟了一個新的視野。通過每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。兩種不同的算法可以求解同一問題，但是角度完全不一樣，從目前自己實驗的結(jié)果而言，對于小數(shù)據(jù)量的輸入均可以快速高效的完成題目。但是遺傳算法可以考慮到的問題復(fù)雜度更高，更適合應(yīng)用于實際。：課堂上講解的遺傳算法較為簡單基礎(chǔ)，對于理論學(xué)習(xí)而言，十分適合。但一旦應(yīng)用于實踐時，發(fā)現(xiàn)雖然每個部分模塊自己都可以理解并且熟悉，但是對于實際應(yīng)用，并且切實地解決實際問題仍存在較大的困難。從理論到實踐，從課本的知識到解決問題，若不及時的加以消化并且切實的應(yīng)用于解決問題，可以看出知識很難為現(xiàn)實提供幫助。因而應(yīng)在學(xué)習(xí)之后及時進(jìn)行上機(jī)實驗，并且達(dá)到熟練掌握與運(yùn)用的階段。第四篇：人工智能實驗報告八數(shù)碼 《人工智能》實驗一題目實驗一啟發(fā)式搜索算法：使用啟發(fā)式搜索算法求解8數(shù)碼問題。⑴ 編制程序?qū)崿F(xiàn)求解8數(shù)碼問題A*算法，采用估價函數(shù)236。239。w(n)，f(n)=d(n)+237。pn239。238。()其中：d(n)是搜索樹中結(jié)點n的深度；w(n)為結(jié)點n的數(shù)據(jù)庫中錯放的棋子個數(shù)；p(n)為結(jié)點n的數(shù)據(jù)庫中每個棋子與其目標(biāo)位置之間的距離總和。⑵ 分析上述⑴中兩種估價函數(shù)求解8數(shù)碼問題的效率差別，給出一個是p(n)的上界的h(n)的定義，并測試使用該估價函數(shù)是否使算法失去可采納性。熟練掌握啟發(fā)式搜索A算法及其可采納性。該搜索為一個搜索樹。為了簡化問題，搜索樹節(jié)點設(shè)計如下： typedef struct Node//棋盤 {//節(jié)點結(jié)構(gòu)體int data[9]。double f,g。struct Node * parent。//父節(jié)點 }Node,*Lnode。int data[9]。數(shù)碼數(shù)組：記錄棋局?jǐn)?shù)碼擺放狀態(tài)。struct Chess * Parent。父節(jié)點：指向父親節(jié)點。下一步可以通過啟發(fā)搜索算法構(gòu)造搜索樹。局部搜索樹樣例：*搜索過程搜索采用廣度搜索方式，利用待處理隊列輔助，逐層搜索（跳過劣質(zhì)節(jié)點）。搜索過程如下：（1）、把原棋盤壓入隊列；（2）、從棋盤取出一個節(jié)點；（3）、判斷棋盤估價值，為零則表示搜索完成，退出搜索；（4）、擴(kuò)展子節(jié)點，即從上下左右四個方向移動棋盤，生成相應(yīng)子棋盤；（5）、對子節(jié)點作評估，是否為優(yōu)越節(jié)點（子節(jié)點估價值小于或等于父節(jié)點則為優(yōu)越節(jié)點），是則把子棋盤壓入隊列，否則拋棄；（5）、跳到步驟（2）；算法的評價 完全能解決簡單的八數(shù)碼問題，但對于復(fù)雜的八數(shù)碼問題還是無能為力?，F(xiàn)存在的一些優(yōu)缺點。可以改變數(shù)碼規(guī)模（N），來擴(kuò)展成N*N的棋盤，即擴(kuò)展為N數(shù)碼問題的求解過程。內(nèi)存泄漏。由于采用倒鏈表的搜索樹結(jié)構(gòu)，簡化了數(shù)據(jù)結(jié)構(gòu)，但有部分被拋棄節(jié)點的內(nèi)存沒有很好的處理，所以會造成內(nèi)存泄漏； 采用了屏蔽方向，有效防止往回搜索（節(jié)點的回推），但沒能有效防止循環(huán)搜索，所以不能應(yīng)用于復(fù)雜度較大的八數(shù)碼問題；源碼：include include include typedef struct Node {//節(jié)點結(jié)構(gòu)體int data[9]。double f,g。struct Node * parent。}Node,*Lnode。typedef struct Stack {//OPEN CLOSED 表結(jié)構(gòu)體Node * npoint。struct Stack * next。}Stack,* Lstack。Node * Minf(Lstack * Open){//選取OPEN表上f值最小的節(jié)點，返回該節(jié)點地址Lstack temp =(*Open)next,min =(*Open)next,minp =(*Open)。Node * minx。while(tempnext!= NULL){if((tempnextnpointf)npointf)){min = tempnext。minp = temp。}temp = tempnext。} minx = minnpoint。temp = minpnext。minpnext = minpnextnext。free(temp)。return minx。}int Canslove(Node * suc, Node * goal){//判斷是否可解int a = 0,b = 0,i,j。for(i = 1。i 9。i++)for(j = 0。j i。j++){if((sucdata[i] sucdata[j])amp。amp。 sucdata[j]!= 0)a++。if((goaldata[i] goaldata[j])amp。amp。 goaldata[j]!= 0)b++。} if(a%2 == b%2)return 1。else return 0。}int Equal(Node * suc,Node * goal){//判斷節(jié)點是否相等，相等，不相等for(int i = 0。i 9。i ++)if(sucdata[i]!= goaldata[i])return 0。return 1。}Node * Belong(Node * suc,Lstack * list){//判斷節(jié)點是否屬于OPEN表或CLOSED表，是則返回節(jié)點地址，否則返回空地址Lstack temp =(*list) next。if(temp == NULL)return NULL。while(temp!= NULL){if(Equal(suc,tempnpoint))return temp npoint。temp = tempnext。} return NULL。}void Putinto(Node * suc,Lstack * list){//把節(jié)點放入OPEN 或CLOSED 表中Stack * temp。temp =(Stack *)malloc(sizeof(Stack))。tempnpoint = suc。tempnext =(*list)next。(*list)next = temp。}///////////////計算f值部分開始////////////////////////////// double Fvalue(Node suc, Node goal, int m){//計算f值switch(m){ case 1:{int error(Node,Node)。int w=0。w=error(suc,goal)。return w+。} case 2:{double Distance(Node,Node,int)。double p = 0。for(int i = 1。i p = p + Distance(suc, goal, i)。return p + 。//f = h + g。} default:break。}}int error(Node suc,Node goal){//計算錯位個數(shù)int w,i。w=0。for(i=0。iif([i]!=[i])w++。} return w。} double Distance(Node suc, Node goal, int i){//計算方格的錯位距離int k,h1,h2。for(k = 0。k 9。k++){if([k] == i)h1 = k。if([k] == i)h2 = k。} return double(fabs(h1/3h2%3))。} ///////////////計算f值部分結(jié)束/////////////////////////////////////////////////////擴(kuò)展后繼節(jié)點部分的函數(shù)開始///////////////// int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,int m){//判斷子節(jié)點是否屬于OPEN或CLOSED表并作出相應(yīng)的處理Node * temp = NULL。int flag = 0。if((Belong(*suc,Open)!= NULL)||(Belong(*suc,Closed)!= NULL)){if(Belong(*suc,Open)!= NULL)temp = Belong(*suc,Open)。else temp = Belong(*suc,Closed)。if(((*suc)g)g)){tempparent =(*suc)parent。tempg =(*suc)g。tempf =(*suc)f。flag = 1。} } else {Putinto(* suc, Open)。(*suc)f = Fvalue(**suc, goal, m)。} return flag。}int Canspread(Node suc, int n){//判斷空格可否向該方向移動，表示空格向上向下向左向右移int i,flag = 0。for(i = 0。i 9。i++)if([i] == 0)break。switch(n){ case 1:if(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 Sp