1、 1、旅行員售貨問(wèn)題    問(wèn)題描述     某售貨員要到若干城市去推銷(xiāo)商品，已知各城市之間的路程（旅費(fèi)），他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線(xiàn)，使總的路程（總旅費(fèi)）最小。    問(wèn)題分析     旅行售貨員問(wèn)題的解空間是一棵排列樹(shù)。對(duì)于排列樹(shù)的回溯法與生成1,2,n的所有排列的遞歸算法Perm類(lèi)似。開(kāi)始時(shí)x=1,2,n,則相應(yīng)的排列樹(shù)有x1:n的所有排列構(gòu)成。     在遞歸算法Backtrack中，

2、當(dāng)i=n時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)是排列樹(shù)的葉節(jié)點(diǎn)的父節(jié)點(diǎn)。此時(shí)算法檢測(cè)圖G是否存在一條從頂點(diǎn)xn-1到頂點(diǎn)xn的邊和一條從頂點(diǎn)xn到頂點(diǎn)1的邊。如果這兩條邊都存在，則找到一條旅行員售貨回路。此時(shí)，算法還需要判斷這條回路的費(fèi)用是否優(yōu)于已找到的當(dāng)前最優(yōu)回流的費(fèi)用bestc。如果是，則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解bestx。     當(dāng)i<n時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)位于排列樹(shù)的第i-1層。圖G中存在從頂點(diǎn)xi-1到頂點(diǎn)xi的邊時(shí)，x1:i構(gòu)成圖G的一條路徑，且當(dāng)x1:i的費(fèi)用小于當(dāng)前最優(yōu)值時(shí)算法進(jìn)入樹(shù)的第i層，否則將剪去相應(yīng)的子樹(shù)。    

3、0;算法具體代碼如下：cpp view plain copy1. /5d9 旅行員售貨問(wèn)題 回溯法求解  2. #include "stdafx.h"  3. #include <iostream>  4. #include <fstream>   5. using namespace std;  6.   7. ifstream&#

4、160;fin("5d9.txt");   8. const int N = 4;/圖的頂點(diǎn)數(shù)    9.   10. template<class Type>  11. class Traveling  12.   13.     template<class Type>  

5、;14.     friend Type TSP(Type *a, int n);  15.     private:  16.         void Backtrack(int i);  17.         int

6、60;n,           / 圖G的頂點(diǎn)數(shù)  18.             *x,          / 當(dāng)前解  19.       

7、60;     *bestx;      / 當(dāng)前最優(yōu)解  20.             Type *a,    / 圖G的領(lǐng)接矩陣  21.          

8、60;  cc,          / 當(dāng)前費(fèi)用  22.             bestc;       / 當(dāng)前最優(yōu)值  23.         

9、;    int NoEdge;  / 無(wú)邊標(biāo)記  24.     25.   26. template <class Type>  27. inline void Swap(Type &a, Type &b);  28.   29. template<class 

10、Type>  30. Type TSP(Type *a, int n);  31.   32. int main()  33.   34.     cout<<"圖的頂點(diǎn)個(gè)數(shù) n="<<N<<endl;  35.   36.     int *a=

11、new int*N+1;  37.     for(int i=0;i<=N;i+)  38.       39.         ai=new intN+1;  40.       41.   42.    &#

12、160;cout<<"圖的鄰接矩陣為:"<<endl;  43.   44.     for(int i=1;i<=N;i+)  45.       46.         for(int j=1;j<=N;j+)  47.    &

13、#160;      48.             fin>>aij;  49.             cout<<aij<<" "  50.     

14、;      51.         cout<<endl;  52.       53.     cout<<"最短回路的長(zhǎng)為："<<TSP(a,N)<<endl;  54.   55.    

15、60;for(int i=0;i<=N;i+)  56.       57.         delete ai;  58.       59.     delete a;  60.   61.     

16、a=0;  62.     return 0;  63.   64.   65. template<class Type>  66. void Traveling<Type>:Backtrack(int i)  67.    68.     if (i = n) &

17、#160;69.       70.         if (axn-1xn != 0 && axn1 != 0 &&   71.             (cc + axn-1

18、xn + axn1 < bestc | bestc = 0)   72.           73.             for (int j = 1; j <= n; j+

19、) bestxj = xj;  74.             bestc = cc + axn-1xn + axn1;    75.           76.      

20、60;77.     else  78.       79.         for (int j = i; j <= n; j+)  80.           81.   

21、;           / 是否可進(jìn)入xj子樹(shù)?  82.              if (axi-1xj != 0 && (cc + axi-1xi < bestc | bestc =

22、 0)  83.                84.                 / 搜索子樹(shù)  85.           

23、;      Swap(xi, xj);  86.                 cc += axi-1xi;  /當(dāng)前費(fèi)用累加  87.             &#

24、160;   Backtrack(i+1);         /排列向右擴(kuò)展,排列樹(shù)向下一層擴(kuò)展  88.                 cc -= axi-1xi;    89.     

25、0;           Swap(xi, xj);  90.                 91.           92.      

26、0;93.   94.   95. template<class Type>  96. Type TSP(Type *a, int n)  97.   98.     Traveling<Type> Y;  99.     Y.n=n;  100.     

27、;Y.x=new intn+1;  101.     Y.bestx=new intn+1;  102.   103.     for(int i=1;i<=n;i+)  104.       105.         Y.xi=i;  106

28、.       107.   108.     Y.a=a;  109.     Y.cc=0;  110.     Y.bestc=0;  111.   112.     Y.NoEdge=0;  113.     Y

29、.Backtrack(2);  114.   115.     cout<<"最短回路為："<<endl;  116.     for(int i=1;i<=n;i+)    117.       118.        

30、0;cout<<Y.bestxi<<" -> "  119.       120.     cout<<Y.bestx1<<endl;  121.   122.     delete  Y.x;  123.     Y.x=0

31、;  124.     delete  Y.bestx;  125.   126.     Y.bestx=0;  127.     return Y.bestc;  128.   129.   130. template <class Type>  131

32、. inline void Swap(Type &a, Type &b)  132.     133.     Type temp=a;   134.     a=b;   135.     b=temp;  136.    

33、60;  算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。      程序運(yùn)行結(jié)果如圖：     2、圓排列問(wèn)題     問(wèn)題描述     給定n個(gè)大小不等的圓c1,c2,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問(wèn)題要求從n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1

34、，1，2時(shí)，這3個(gè)圓的最小長(zhǎng)度的圓排列如圖所示。其最小長(zhǎng)度為。     問(wèn)題分析     圓排列問(wèn)題的解空間是一棵排列樹(shù)。按照回溯法搜索排列樹(shù)的算法框架，設(shè)開(kāi)始時(shí)a=r1,r2,rn是所給的n個(gè)元的半徑，則相應(yīng)的排列樹(shù)由a1:n的所有排列構(gòu)成。    解圓排列問(wèn)題的回溯算法中，CirclePerm(n,a)返回找到的最小的圓排列長(zhǎng)度。初始時(shí)，數(shù)組a是輸入的n個(gè)圓的半徑，計(jì)算結(jié)束后返回相應(yīng)于最優(yōu)解的圓排列。center計(jì)算圓在當(dāng)前圓排列中的橫坐標(biāo)，由x2 = sqrt(r1+r2)2-(r1-r2)2)推導(dǎo)出x =

35、2*sqrt(r1*r2)。Compoute計(jì)算當(dāng)前圓排列的長(zhǎng)度。變量min記錄當(dāng)前最小圓排列長(zhǎng)度。數(shù)組r表示當(dāng)前圓排列。數(shù)組x則記錄當(dāng)前圓排列中各圓的圓心橫坐標(biāo)。     在遞歸算法Backtrack中，當(dāng)i>n時(shí)，算法搜索至葉節(jié)點(diǎn)，得到新的圓排列方案。此時(shí)算法調(diào)用Compute計(jì)算當(dāng)前圓排列的長(zhǎng)度，適時(shí)更新當(dāng)前最優(yōu)值。     當(dāng)i<n時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)位于排列樹(shù)的i-1層。此時(shí)算法選擇下一個(gè)要排列的圓，并計(jì)算相應(yīng)的下界函數(shù)。      算法具體代碼如下：cpp view plai

36、n copy1. /圓排列問(wèn)題 回溯法求解  2. #include "stdafx.h"  3. #include <iostream>  4. #include <cmath>  5. using namespace std;  6.   7. float CirclePerm(int n,float *a); 

37、0;8.   9. template <class Type>  10. inline void Swap(Type &a, Type &b);  11.   12. int main()  13.   14.     float *a = new float4;  15

38、.     a1 = 1,a2 = 1,a3 = 2;  16.     cout<<"圓排列中各圓的半徑分別為："<<endl;  17.     for(int i=1; i<4; i+)  18.       19

39、.         cout<<ai<<" "  20.       21.     cout<<endl;  22.     cout<<"最小圓排列長(zhǎng)度為："  23.     

40、cout<<CirclePerm(3,a)<<endl;  24.     return 0;  25.   26.   27. class Circle  28.   29.     friend float CirclePerm(int,float *);  30.    

41、; private:  31.         float Center(int t);/計(jì)算當(dāng)前所選擇的圓在當(dāng)前圓排列中圓心的橫坐標(biāo)  32.         void Compute();/計(jì)算當(dāng)前圓排列的長(zhǎng)度  33.         void 

42、;Backtrack(int t);  34.   35.         float min,  /當(dāng)前最優(yōu)值  36.               *x,   /當(dāng)前圓排列圓心橫坐標(biāo)  37.   

43、0;           *r;   /當(dāng)前圓排列  38.         int n;      /圓排列中圓的個(gè)數(shù)  39. ;  40.   41. / 計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo)  42.

44、 float Circle:Center(int t)  43.   44.     float temp=0;  45.     for (int j=1;j<t;j+)  46.       47.         /由x2 =&

45、#160;sqrt(r1+r2)2-(r1-r2)2)推導(dǎo)而來(lái)  48.         float valuex=xj+2.0*sqrt(rt*rj);  49.         if (valuex>temp)  50.           51.

46、            temp=valuex;  52.           53.       54.     return temp;  55.   56.   57. / 

47、計(jì)算當(dāng)前圓排列的長(zhǎng)度  58. void Circle:Compute(void)  59.   60.     float low=0,high=0;  61.     for (int i=1;i<=n;i+)  62.       63.      

48、0;  if (xi-ri<low)  64.           65.             low=xi-ri;  66.           67.   68.  

49、       if (xi+ri>high)  69.           70.             high=xi+ri;  71.          &#

50、160;72.       73.     if (high-low<min)  74.       75.         min=high-low;  76.       77.   78.   79

51、. void Circle:Backtrack(int t)  80.   81.     if (t>n)  82.       83.         Compute();  84.       85.    

52、 else  86.       87.         for (int j = t; j <= n; j+)  88.           89.       

53、      Swap(rt, rj);  90.             float centerx=Center(t);  91.             if (centerx+rt+r1<min)/下界約束  92.               93.                 xt=centerx;  94.    &