1、寧夏師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院算法分析與設(shè)計實驗報告實驗序號：11 實驗項目名稱：用回溯法解決旅行商問題 學(xué)號姓名專業(yè)、班實驗地點指導(dǎo)教師時 間2014.06.23一、實驗?zāi)康募耙螅?） 理解算法復(fù)雜度的概念（2） 掌握算法復(fù)雜度計算的方法二、實驗設(shè)備（環(huán)境）及要求1、環(huán)境要求：硬件：PC（PII以上，128M以上內(nèi)存）、因特網(wǎng)接入；軟件：Windows XP操作系統(tǒng)、Office2003、多媒體播放軟件。三、實驗內(nèi)容與步驟#include#define N 4double cc,/當(dāng)前路徑費用 bestc;/當(dāng)前最優(yōu)解費用double aN+1N+1;/鄰接矩陣，存放圖的信息int be

2、stxN+1;/當(dāng)前最優(yōu)解int xN+1;/當(dāng)前解void inputAjac()int i,j;printf(輸入大于0.0的值表示有邊,小于0.0表示無邊：n);for(i=1;i=N;i+)for(j=i+1;j0.0&axNx10.0)if(bestccc+axN-1xN+axNx1)int j;for(j=1;j=N;j+)bestxj=xj;bestc=cc+axN-1xN+axNx1;elseint j;for(j=i;j0.0)if(bestccc+axi-1xj+axjx1)int temp;cc+=axi-1xj;temp=xi;xi=xj;xj=temp;backtra

3、ck(i+1);temp=xi;xi=xj;xj=temp;cc-=axi-1xj;double tsp()/初始化int i;for(i=1;i=N;i+)xi=i;cc=0.0,bestc=-1.0;inputAjac();backtrack(2);return bestc;void output() int i;for(i=1;i=N;i+)printf(%4d,bestxi); printf(n);void main()printf(走%d個城市最少路費為：%lf,N,tsp();printf(走法為:);output();四、實驗結(jié)果與數(shù)據(jù)處理五、分析與討論 旅行售貨員問題的解空間是

4、一棵排列樹。 在遞歸算法 backtrack中，當(dāng)i=n時，當(dāng)前擴展結(jié)點時排列樹的葉結(jié)點的父結(jié)點。此時算法檢測圖G是否存在一條從頂點xn-1到頂點xn的邊和一條從頂點xn到頂點1的邊。如果這兩條邊都存在，則找到一條旅行售貨員回路。此時，算法還需判斷這條回路的費用是否優(yōu)于當(dāng)前已找到的最優(yōu)回路的費用bestc。如果是，則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解bestx。當(dāng)in時，當(dāng)前擴展結(jié)點位于排列樹的第i-1層。圖G中存在從頂點xi-1到頂點xi的邊時，x1:i構(gòu)成圖G的一條路徑，且當(dāng)x1:i的費用小于當(dāng)前最優(yōu)值時算法進入排列樹的第i層；否則，將剪去相應(yīng)的子樹。算法中用變量cc記錄當(dāng)前路徑x1:i的費用。算法效率：如果不考慮更新bestx所需的計算時間，則算法backtrack需要O(n-1)!)計算時間。由于算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-