tsp問(wèn)題算法分析-資料下載頁(yè)
2025-03-24 05:06本頁(yè)面
【正文】 (i = 1。 i = n。 i++) v[i] = 0。 bestc = BBTSP(v)。 printf(\n)。 printf(最優(yōu)路徑為)。 for(i = 1。 i = n。 i++) fprintf(stdout, %c\t, v[i]+64)。 fprintf(stdout, \n)。 fprintf(stdout, 總路程為\n, bestc)。 return 0。 } A*算法include const 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==bestpath[k]) break。 } if(k!=p+1)//新測(cè)試節(jié)點(diǎn)在a[]中 return 1。 else return 0。}void main(){ int min=max。 int minf=max。 int num。//城市數(shù)量 int mat[ax][ax]。//城市間距離 int bestpath[ax]。//最佳路徑 int f=0,g=0,h=0。 int ff[ax]。//依次求每個(gè)城市的f值 int gg[ax]。//城市的g值 printf(城市個(gè)數(shù)為：)。 scanf(%d,amp。num)。 printf(城市間的距離為：\n)。//輸入各城市間距離的矩陣 for(int i=0。inum。i++) for(int j=0。jnum。j++) scanf(%d,amp。mat[i][j])。 bestpath[0]=0。//起點(diǎn)為0，即城市A for(int p=0。pnum1。p++)//依次求每個(gè)最優(yōu)節(jié)點(diǎn)，每次循環(huán)得到一個(gè)新的最優(yōu)城市放到bestpath[]中 { for(int kk=0。kknum。kk++) ff[kk]=max。//便于后面求最小值 for(i=1。inum。i++)//起點(diǎn)A不算，從非起點(diǎn)開(kāi)始找尋最優(yōu)城市 { if(isbest(i,bestpath,p))//該點(diǎn)已經(jīng)在bestpath[]中的話，忽略 continue。 else//計(jì)算該點(diǎn)的g值 gg[i]=g+mat[bestpath[p]][i]。//i點(diǎn)的g值 for(int m=0。mnum。m++)//開(kāi)始計(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==num2)//不是最后一個(gè)點(diǎn)的話，不算A點(diǎn)到這個(gè)點(diǎn)長(zhǎng)度 if(mat[m][t]min) min=mat[m][t]。 } } h=min*(nump1)。//h值 ff[i]=gg[i]+h。//第i個(gè)節(jié)點(diǎn)的f值 min=max。//重新賦值最大，以便下次循環(huán) } for(i=0。inum。i++)//找尋最優(yōu)點(diǎn)，即f值最小者 { if(ff[i]minf) { minf=ff[i]。 bestpath[p+1]=i。 } } minf=max。//重新賦值最大，以便下次循環(huán) g=g+mat[bestpath[p]][bestpath[p+1]]。//更新g值 } printf(最優(yōu)路徑為:)。 for(i=0。inum。i++) printf(%c ,bestpath[i]+65)。printf(A\n)。printf(總路程為:)。 int sum=0。for(i=0。inum1。i++) sum=sum+mat[bestpath[i]][bestpath[i+1]]。sum=sum+mat[bestpath[num1]][0]。//總路程最后一個(gè)城市要回到A，所以加上其距離printf(%d\n,sum)。}4． 結(jié)果截圖 A*算法
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1