久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標(biāo)題: 回溯法之－旅行售貨員問(wèn)題 [打印本頁(yè)]
作者: 51黑tt    時(shí)間: 2016-3-5 20:14
標(biāo)題: 回溯法之－旅行售貨員問(wèn)題
   回溯法有“通用的解題法”之稱(chēng)。應(yīng)用回溯法解問(wèn)題時(shí)，首先應(yīng)該明確問(wèn)題的解空間。一個(gè)復(fù)雜問(wèn)題的解決往往由多部分構(gòu)成，即，一個(gè)大的解決方案可以看作是由若干個(gè)小的決策組成。很多時(shí)候它們構(gòu)成一個(gè)決策序列。解決一個(gè)問(wèn)題的所有可能的決策序列構(gòu)成該問(wèn)題的解空間。解空間中滿(mǎn)足約束條件的決策序列稱(chēng)為可行解。一般說(shuō)來(lái)，解任何問(wèn)題都有一個(gè)目標(biāo)，在約束條件下使目標(biāo)達(dá)優(yōu)的可行解稱(chēng)為該問(wèn)題的最優(yōu)解。在解空間中，前 k 項(xiàng)決策已經(jīng)確定的所有決策序列之集稱(chēng)為 k 定子解空間。 0 定子解空間即是該問(wèn)題的解空間。

    旅行商問(wèn)題：某售貨員要到若干個(gè)城市去推銷(xiāo)商品。已知各個(gè)城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一次，最后回到駐地的路線(xiàn)，使得總的路程（或總旅費(fèi)）最短。


    我們用一個(gè)帶權(quán)圖 G(V, E) 來(lái)表示，頂點(diǎn)代表城市，邊表示城市之間的道路。圖中各邊所帶的權(quán)即是城市間的距離（或城市間的旅費(fèi)）。則旅行商問(wèn)題即是：在帶權(quán)圖 G 中找到一條路程最短的周游路線(xiàn)，即權(quán)值之和最小的 Hamilton 圈。
    如果假定城市 A 是駐地。則推銷(xiāo)員從 A 地出發(fā)，第一站有 3 種選擇：城市 B 、 C 或城市 D ；第一站選定后，第二站有兩種選擇：如第一站選定 B ，則第二站只能選 C 、 D 兩者之一。當(dāng)?shù)谝弧⒌诙䞍烧径歼x定時(shí)，第三站只有一種選擇：比如，當(dāng)?shù)谝弧⒌诙䞍烧鞠群筮x擇了 B 和 C 時(shí)，第三站只能選擇 D 。最后推銷(xiāo)員由城市 D 返回駐地 A 。
用JAVA解決，代碼如下：
  1. public class Traveling {

  3. public  static  int NUM = 4;
  4. public  static  int n  = NUM;
  5. public  static int NoEdge=1000;
  6. public  static int x[]  = new int [NUM+1];
  7. public  static int bestx[]  = new int [NUM+1];
  8. public  static int a[][] ={{},
  9.     {0,0 , 30 , 6 , 4 } ,
  10.     {0,30 , 0 , 5 , 10   } ,
  11.     {0,6 , 5 , 0 , 20   } ,
  12.     {0,4 , 10 , 20, 0} ,
  13.     };
  14. public  static int cc =0;
  15. public  static int bestc=1000;
  16.    
  17. public static  int TSP(int a[][],int v[],int n,int NoEdge){
  18.   return 0 ;
  19.    
  20. }
  21. private static void Backtrack(int i){
  22.   if(i==n){
  23.    if(a[x[n-1]][x[n]] != NoEdge &&
  24.      a[x[n]][1] != NoEdge &&
  25.      (cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc == NoEdge)){
  26.     for(int j=1 ; j<=n; j++)
  27.      bestx[j] = x[j];
  28.     bestc = cc+ a[x[n-1]][x[n]] + a[x[n]][1];
  29.    }
  30.   }
  31.   else{
  32.    for(int j = i ; j<=n ;j++)
  33.     if(a[x[i-1]][x[j]]!= NoEdge && (cc+a[x[i-1]][x[i]] < bestc||bestc == NoEdge)){
  34.      int t = x[i];x[i]=x[j];x[j]=t;
  35.      cc+=a[x[i-1]][x[i]];
  36.      Backtrack(i+1);
  37.      cc -= a[x[i-1]][x[i]];
  38.       t = x[i];x[i]=x[j];x[j]=t;
  39.     }
  40.   }
  41. }
  42. public static void main(String[] args) {
  43.   // TODO Auto-generated method stub
  44. for(int i=1;i<=n;i++)
  45.   x[i] = i;
  46. Backtrack(2);
  47. for(int i=1;i<=n;i++){
  48.   for(int j=1;j<=n;j++)
  49.    System.out.print(a[i][j]+"\t");
  50.   System.out.println();
  51. }

  53. System.out.println("最小費(fèi)用為:"+Traveling.bestc);
  54. System.out.println("所經(jīng)節(jié)點(diǎn)為：");
  55. for(int i=1;i<=n;i++)
  56.   System.out.print(+Traveling.bestx [i]+"\t");
  57. System.out.print("1");
  58. }

  60. }
復(fù)制代碼


作者: 15340814131    時(shí)間: 2020-3-19 12:59
請(qǐng)問(wèn)距離的話(huà)最后的那個(gè)最短路程是什么單位
作者: 15340814131    時(shí)間: 2020-3-19 13:01
您好，請(qǐng)問(wèn)如果是算最短路程，最后輸出的單位是什么



歡迎光臨 (http://www.zg4o1577.cn/bbs/) Powered by Discuz! X3.1
主站蜘蛛池模板： 国产精品九九视频 | 亚洲视频免费在线 | 成人在线视 | a级片网站 | 亚洲欧美日韩精品久久亚洲区 | 亚洲一区精品在线 | 全部免费毛片在线播放网站 | 精品视频一二区 | 久久国产欧美日韩精品 | 亚洲国产精品久久 | 日韩欧美国产成人一区二区 | 精品日韩在线 | 亚洲综合色自拍一区 | 午夜一区二区三区 | 亚洲一区二区三区免费视频 | 国产高潮av | 午夜视频免费 | 欧美一区二区在线视频 | 我想看国产一级毛片 | 久久久久久国产精品 | 日日碰碰 | 欧美女优在线观看 | 国产精品免费高清 | 91精品国产一区二区 | 久久噜噜噜精品国产亚洲综合 | 久久久亚洲综合 | 天天操天天天 | 久久久久亚洲精品国产 | 国产一区二区三区精品久久久 | 91中文字幕在线 | 精品一区二区三区在线观看 | 天天综合网91 | 国产精品久久久久久福利一牛影视 | 国产蜜臀 | 国产精品久久久av | 亚洲国产精品99久久久久久久久 | 免费久久精品视频 | 成人一区二区视频 | 国产精品一区二 | 久久久久九九九女人毛片 | 奇米影视首页 |