旅行商A星算法c語言程序

1、 1) 實(shí)驗(yàn)內(nèi)容 “旅行商問題”常被稱為“旅行推銷員問題”，是指一名推銷員要拜訪多個(gè)地點(diǎn)時(shí)，如何找到在拜訪每個(gè)地點(diǎn)一次后再回到起點(diǎn)的最短路徑。旅行商問題在本實(shí)驗(yàn)中的具體化：從a城市出發(fā)，到達(dá)每個(gè)城市并且一個(gè)城市只允許訪問一次，最后又回到原來的城市，尋找一條最短距離的路徑。2) 實(shí)驗(yàn)?zāi)康?加深對(duì)a星算法的理解了解啟發(fā)式圖搜索策略3) a*算法中f(n)=g(n)+h(n)如何選?。?對(duì)于某一已到達(dá)的現(xiàn)行狀態(tài), 如已到達(dá)圖中的n節(jié)點(diǎn), 它是否可能成為最佳路徑上的一點(diǎn)的估價(jià), 應(yīng)由估價(jià)函數(shù)f(n)值來決定。假設(shè)g*(n)函數(shù)值表示從起始節(jié)點(diǎn)s 到任意一個(gè)節(jié)點(diǎn)n 的一條最佳路徑上的實(shí)際耗散值。h*(n

2、)函數(shù)值表示從任意節(jié)點(diǎn)n 到目標(biāo)節(jié)點(diǎn)ti 的最佳路徑的實(shí)際耗散值。其中ti 是一個(gè)可能的目標(biāo)節(jié)點(diǎn)。f*(n)函數(shù)值表示從起始s，通過某一指定的n 到達(dá)目標(biāo)節(jié)點(diǎn)ti的一條最佳路徑的實(shí)際耗散值，并有f*(n)=g*(n)+h*(n)。 假設(shè)f 函數(shù)是對(duì)f* 函數(shù)的一種估計(jì), 并有f(n)=g(n)+h(n)，其中g(shù) 函數(shù)是對(duì)g* 的估計(jì)，h 函數(shù)是對(duì)h* 的一種估計(jì)。f( n) 包括兩個(gè)部分，其中g(shù)(n)表示到達(dá)n 節(jié)點(diǎn)時(shí)，已付出代價(jià)的估計(jì)；而h(n)表示從n 節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)ti 將要付出代價(jià)的估計(jì)。按f(n)=g*(n)+h*(n)的值來排序ff 表的節(jié)點(diǎn)，f 值小者優(yōu)先。通常稱這種算法為a算

3、法。在a 算法的基礎(chǔ)上，進(jìn)一步限制h(n)函數(shù)，使得搜索圖中的每一個(gè)節(jié)點(diǎn)n，能滿足h(n)=h*(n)、稱h 函數(shù)取h* 的下界。這種算法叫a* 算法。對(duì)ff里的每一個(gè)節(jié)點(diǎn)做評(píng)估函數(shù)f分為兩部分g和h：假設(shè)從a城市走到x城市，又走到y(tǒng)城市，所以g可表示為：g = a到x的距離 + x到y(tǒng)的距離；未走的的城市數(shù)=（總城市數(shù)+1）-目前城市的層數(shù)。為什得加1，因?yàn)樽詈蟮米呋爻跏汲鞘?，所以總路徑的城市?shù)為總城市數(shù)+1。h = 未走的城市數(shù)目前的最小距離；f = g + h ;計(jì)算ff表里每個(gè)節(jié)點(diǎn)的f值，f值最小的節(jié)點(diǎn)作為活路徑，把它加到bestpath中。4) 完整的源代碼 （加注釋說明） #inc

4、lude stdio.hconst int max=9999;const int ax=50;int isbest(int i,int bestpath,int p)/檢測(cè)改節(jié)點(diǎn)是否已經(jīng)加入bestpath中 for(int k=1;k=p;k+)if(i=bestpathk)break;if(k!=p+1)/新測(cè)試節(jié)點(diǎn)在a中 return 1;elsereturn 0;void main() int min=max;int minf=max;int num;/城市數(shù)量int mataxax;/城市間距離int bestpathax;/最佳路徑int f=0,g=0,h=0;int ffax;

5、/依次求每個(gè)城市的f值int ggax;/城市的g值printf(城市個(gè)數(shù)為：);scanf(%d,&num);printf(城市間的距離為：n);/輸入各城市間距離的矩陣for(int i=0;inum;i+)for(int j=0;jnum;j+)scanf(%d,&matij); bestpath0=0;/起點(diǎn)為0，即城市afor(int p=0;pnum-1;p+)/依次求每個(gè)最優(yōu)節(jié)點(diǎn)，每次循環(huán)得到一個(gè)新的最優(yōu)城市放到bestpath中for(int kk=0;kknum;kk+)ffkk=max;/便于后面求最小值for(i=1;inum;i+)/起點(diǎn)a不算，從非起點(diǎn)開始找尋最優(yōu)城市

6、if(isbest(i,bestpath,p)/該點(diǎn)已經(jīng)在bestpath中的話，忽略continue;else/計(jì)算該點(diǎn)的g值ggi=g+matbestpathpi;/i點(diǎn)的g值 for(int m=0;mnum;m+)/開始計(jì)算h值 if(isbest(m,bestpath,p)/該點(diǎn)已經(jīng)在bestpath中的話，忽略 continue;for(int t=m+1;tnum;t+)if(isbest(t,bestpath,p)continue;if(m!=0|t!=i|p=num-2)/不是最后一個(gè)點(diǎn)的話，不算a點(diǎn)到這個(gè)點(diǎn)長度if(matmtmin)min=matmt; h=min*(nu

7、m-p-1);/h值ffi=ggi+h;/第i個(gè)節(jié)點(diǎn)的f值min=max;/重新賦值最大，以便下次循環(huán)for(i=0;inum;i+)/找尋最優(yōu)點(diǎn)，即f值最小者if(ffiminf)minf=ffi;bestpathp+1=i;minf=max;/重新賦值最大，以便下次循環(huán)g=g+matbestpathpbestpathp+1;/更新g值printf(最優(yōu)路徑為:); for(i=0;inum;i+) printf(%c ,bestpathi+65);printf(an);printf(總路程為:); int sum=0;for(i=0;inum-1;i+) sum=sum+matbestpa

8、thibestpathi+1;sum=sum+matbestpathnum-10;/總路程最后一個(gè)城市要回到a，所以加上其距離printf(%dn,sum);5) 實(shí)驗(yàn)運(yùn)行過程截圖6) 實(shí)驗(yàn)過程中遇到的問題 1. 程序剛寫好問題還是挺多的，總是得不到正確的結(jié)果，程序不算大，但是循環(huán)比較多，所以發(fā)現(xiàn)錯(cuò)誤還是挺難的，通過程序的分步執(zhí)行，才逐漸發(fā)現(xiàn)錯(cuò)誤所在，比如說 g值要及時(shí)的更新2. 循環(huán)的終點(diǎn)要確定，一開始運(yùn)行時(shí)，一直崩潰。 問題出在if(m!=0|t!=i)這里，計(jì)算h值時(shí)，取余下路徑時(shí)，假設(shè)現(xiàn)在bestpath中有ad現(xiàn)在在測(cè)試b點(diǎn)，那么ba不會(huì)在下面路徑中走到，不用考慮，但是如果b是最后一個(gè)點(diǎn)，那么在剩下路徑中只能走ba，必須考慮。所以在判定條件中必須添加一個(gè) p=num-2，變成 if(m!=0|t!=i|p=num-2)，p=num-2就是在尋找回到a前的最后一個(gè)點(diǎn)7) 實(shí)驗(yàn)心得體會(huì)。 通過本次實(shí)驗(yàn)，我深入了解了一下a星算法，