【文章內(nèi)容簡介】 //做輸送 n[3]=n[2]+(int) (abs(nn2)*ran3(amp。idum))+1。 n[3]=1+((n[3]1) % ncity)。//輸送到一個不在當(dāng)前路徑上的某處 de=trncst(x,y,iorder,ncity,n)。 //計算代價 ans=metrop(de,t)。 //做預(yù)測 if(ans) { ++nsucc。 path+=de。 trnspt(iorder,ncity,n)。 //輸送工作結(jié)束 }} else { //做段反轉(zhuǎn) de=revcst(x,y,iorder,ncity,n)。 //計算代價 ans=metrop(de,t)。 //作預(yù)測 if (ans){ ++nsucc。 path+=de。 reverse(iorder,ncity,n)。 //完成段反轉(zhuǎn) }}if (nsucc=nlimit) break。 //如果成功的轉(zhuǎn)移超過次數(shù)則提前結(jié)束}printf(\n %s % %s amp。 \n,T=,t, Path Length=,path)。printf(Successful Moves: %6d\n，nsucc)。t*=TFACTR。 //退火進(jìn)程if (nsucc==0) return。 //如果不成功則返回}}include define ALEN(a,b,c,d) sqrt(((b)(a))*((b)(a))+((d)(c))*((d)(c))))float revcst(float x[]，float y[]，intiorder[]，int ncity，int n[])/*該子程序返回的是反轉(zhuǎn)某給定路徑所需的代價函數(shù)值。參數(shù)中ncity為城市數(shù)；數(shù)組x[1..ncity]，y[1..ncity]為這些城市的位置坐標(biāo)；iorder[n.. ncity]為當(dāng)前路線；數(shù)組n的頭兩個元素n[1]和n[2]分別代表將要被反轉(zhuǎn)的路徑段的起點城市和終點城市。子程序的輸出項de為反轉(zhuǎn)所需的代價值，但真正的反轉(zhuǎn)過程并不是由該程序執(zhí)行。*/{float xx[5],yy[5],de。int i,ii。n[3]=1+ ((n[1]+ncity2) % ncity)。 //找出n[1]以前的城市n[4]=1+(n[2] % ncity)。 //..找出n[2]以后的城市for (j=1。j=4。j++) { ii=iorder[n[j]]。 //求四個所涉及到的城市的坐標(biāo) xx[j]=x[ii]。 yy[j]=y[ii]。}de=ALEN(xx[1],xx[3],yy[1],yy[3])。 //計算斷開路徑段兩端所需的代價de=ALEN(xx[2],xx[4],yy[2],yy[4])。 //以及用相反順序重新連接所需的代價de+=ALEN(xx[1],xx[4],yy[1],yy[4])。de+=ALEN(xx[2],xx[3],yy[2],yy[3])。return de。}void reverse (int iorder[]，int ncity，int n[])/*該子程序的作用是執(zhí)行一段路徑的反轉(zhuǎn)過程。輸入?yún)?shù)iorder[l..ncity]給出當(dāng)前的路線順序；向量n的前四個元素中，n[1]和n[2]分別為將要被反轉(zhuǎn)的路徑的起點和終點城市，n[3]和n[4]則分別為緊隨n[1]之前和緊隨n[2]之后的兩個城市的標(biāo)號，其中n[3]和n[4]由函數(shù)revcst給出。在輸出端，iorder又將被作為返回值，它的定義是n[1] 到n[2]路段被反轉(zhuǎn)后的行程路線。*/{int nn,j,k,l,itmp。nn= (1 + ((n[2]n[1]+ncity) % ncity) )/2。 //為實現(xiàn)反轉(zhuǎn)操作，必須交換這么多城市for (j=1。j=nn。j++) { k=1 + ((n[1]+j2) % ncity)。 //從段的端部開始，順序交換城市對， l=1 + ((n[2]j+ncity) % ncity)。 //直至到達(dá)路徑的中心 itmp=iorder[k]。 iorder[k] =iorder [l]。 iorder[l]=itmp。 }} include define ALEN(a,b,c,d) sqrt(((b)(a))*((b)(a))+((d)(c))*((d)(c)))float trncat (float x[], float y[], int iorder[], int ncity, int n[])/*該子程序返回的是輸送某段給定路徑所需的代價函數(shù)值。輸入?yún)?shù)中ncity為城市的個數(shù)；x[1..ncity]和y[1..ncity] 為這些城市的位置坐標(biāo)，數(shù)組n的前三個元索分別為：將要被輸送的路徑段的起、止點城市以及這段路徑將要被插入處的標(biāo)志城市(插在該城市之后)，該子程序的輸出項de為計算出來的輸送代價值，但實際的輸送操作井不由該子程序執(zhí)行。*/{float xx[7],yy[7],de。 int j,ii。n[4]=1+(n[3] % ncity)。 //找出位于n[3]之后的城市..n[5]=1+((n[1]+ncity2) % ncity)。 // ..位于n[1]之前的一個城市..n[6]=1+(n[2] % ncity)。 // ..位于n[2]之后的一個城市..for (j=1。j=6。j++) { ii = iorder[n[j]]。 //求出六個城市的有關(guān)坐標(biāo) xx[j]=x[ii]。 yy[j]=y[ii]。}de = ALEN(xx[2],xx[6],yy[2],yy[6])。 //計算下列操作所需代價，斷開n[1]到n[2]de = ALEN(xx[1],xx[5],yy[l],yy[5])。 //間的路徑。打開n[3]和n[4]之間的空間。de = ALEN(xx[3],xx[4],yy[3],yy[4])。 //連接這個空間中的路徑段。以及連接n[5]、n[6]de += ALEN(xx[1],xx[3],yy[1],yy[3])。de += ALEN(xx[2],xx[4],yy[2],yy[4])。de += ALEN(xx[5],xx[6],yy[5],yy[6])。return de。} include void trnspt(int iorder[], int ncity, int n[])/*該子程序的作用是執(zhí)行真正的段輸送操作，輸入?yún)?shù)iorder[1..ncity]給出當(dāng)前的路徑順序；數(shù)組n共有6個元素，其意義分別為：n[1]和n[2]分別代表將要被輸送的路徑段的起點城市和終點城市；n[3]和n[4]為兩個相鄰的城市，n[1]至n[2]路徑段即將放入它們中間。n[5]和n[6]分別為n[1]之前和n[2]之后的兩個城市。在這六個元索中n [4],n[5]和n[6]由函數(shù)trncst給出。在輸出端，iorder將根據(jù)路徑段的移動和變化作出相應(yīng)的修改。*/{int ml,m2,m3,nn,j,jj,*jorder。jorder=ivector(1,ncity) 。m1=1+((n[2]n[1]+ncity) % ncity)。 //找出位于n[1]和n[2]間城市個數(shù)m2=1+((n[5]n[4]+ncity) % ncity)。 //…n[4]到n[5]間的城市個數(shù)m3=1+((n[3]n[6]+ncity) % ncity)。 //…n[6]和n[3]間的城市個數(shù)nn=l。for(j=1。 j=m1。 j++) { jj=1 + ((j+n[1] 2) % ncity)。 //復(fù)制所選路徑段 jorder[nn++] = iorder[jj]。}if (m20) { for(j=1。j=m2。j++) { //復(fù)制n[4]到n[5]間的路徑段 jj=1+((j+n[4]2) % ncity)。 jorder [nn++] = iorder [jj]。 }}