旅行推銷員問題

Question

我想從旅行推銷員問題算法開發C++程序。我需要一個距離矩陣和一個成本矩陣。使用所有公式後，我得到一個新的合成矩陣。但我不明白矩陣顯示的是什麼。 假設產生的矩陣是：

1 2 3 
4 5 6 
7 8 9 

現在我想知道這是什麼矩陣節目嗎？假設我有3個城市可以穿越。

請告訴我流。該算法的示例程序將更加有利.. 謝謝。

我的計劃是：

#include<iostream.h> 
#include<conio.h> 
#include <stdlib.h> 

void main() 
{ 
    clrscr(); 
    int a,b,c,d,ctr,j,Q=1,K=1 ; 
    float q0=0.7, p = 0.5 ; 
    int phe[3][3]; 
    double dist[3][3] , mem[3][3],exp[3][3],eplt[3][3], rnd; 
    cout<<"enter the iterations, cities , ants "; 
    cin>>a>>b>>c; 
    for (int i=0;i<3;i++) 
    { 
     for (j=0;j<3;j++) 
     { 
      dist[i][j]=(double)rand()/(double)RAND_MAX; 
      if (i==j) 
      dist[i][j]=0; 
     } 
    } 
    for (i=0;i<3;i++) 
    { 
     for (j=0;j<3;j++) 
     { 
      cout<< dist[i][j]<<"\t"; 
     } 
     cout<<"\n"; 
    } 

    cout<<"pheromone matrix "<<endl; 
    for (i=0;i<3;i++) 
    { 
     for (j=0;j<3;j++) 
     { 
      if (i==j) 
       phe[i][j]=0; 
      else 
       phe[i][j]=1; 
     } 
    } 

    for (i=0;i<3;i++) 
    { 
     for (j=0;j<3;j++) 
     { 
      cout<< phe[i][j]<<"\t"; 
     } 
     cout<<"\n"; 
    } 

    cout<< "after iteration "<<endl; 
    for (i=0;i<3;i++) 
    { 
     ctr=0; 
     for (int k=0;k<3;k++) 
     { 
      // mem[i][k]=(rand()%b)+1; 
      // cout<<"memory"<<mem[i][k]<<"\n"; 
      rnd= (double)rand()/(double)RAND_MAX; 
      cout<<"hhhhhhh"<<rnd; 
      if (rnd<=q0) 
      { 
       cout<<"Exploitation\n"; 
       eplt[i][ctr] =(p*phe[i][k])+(Q/K); 
      } 
      else 
      { 
       cout<<"EXPLORATION\n"; 
       eplt[i][ctr]= phe[i][k]/dist[i][k]; 
      } 
      ctr++; 
     } 
    } 
    for (i=0;i<3;i++) 
    { 
     for (int k=0;k<3;k++) 
     { 
      cout <<eplt[i][k]<<"\t"; 
     } 
     cout<<"\n"; 
    } 
    getch(); 
} 

OUTPUT：

enter the iterations, cities , ants 3 
4 
4 
0  0.003967  0.335154 
0.033265  0  0.2172 
0.536973  0.195776  0 
pheromone matrix 
0  1  1 
1  0  1 
1  1  0 
after iteration 
hhhhhhh0.949919EXPLORATION 
hhhhhhh0.356777EXPLOITATION 
hhhhhhh0.356777EXPLOITATION 
hhhhhhh0.356777EXPLOITATION 
hhhhhhh0.356777EXPLOITATION 
hhhhhhh0.356777EXPLOITATION 
hhhhhhh0.949919EXPLORATION 

Answer 1

先上去，當你說My Program你的意思The program in the paper，因爲它基本上是過時的C++我猜。標準庫頭文件沒有附加.h，並且conio.h是MS-DOS頭文件 - 我見過的大多數代碼都是使用來自Borland Turbo C++的代碼。值得注意的是，如果您要嘗試在現代系統上編譯該演示版。

接下來，你看什麼是adjacancy矩陣。我不相信矩陣是所有輸出的一部分;爲了演示目的，我相信它是正在使用的模型的一部分。我相信，鑑於你有pheromone矩陣，那你看這裏是什麼Ant Colony Optimisation，解決了TSP，並可以減少它的其他問題的概率方法。

從您的輸出中，不清楚結果存儲在哪裏或如何，因爲這是作業，我很懶惰，你只是要求一個徹底的答案，我不會讀那個碼。蟻羣優化的前提是螞蟻放置的信息素軌跡隨時間推移（迭代次數）隨着圖形隨機走動。螞蟻沿着一個特定的頂點（距離）移動的時間越長，信息素的衰落就越多。在這一點上，螞蟻開始根據信息素在路徑上的力量做出決定。那麼螞蟻會開始喜歡某些路線而不是其他的路線，並且會不斷地沿着這條路線重新加入信息素。

所以，在某個地方，就必須有像adjacancy矩陣的矩陣，存儲每個路線的信息素水平。結合路線的長度，每次迭代應檢測到衰減率。

Answer 2

• 您的輸入變量a，b，c從不使用。
• 您的變量ctr的使用方式與同一循環的變量k完全相同。
• 您的phenomone矩陣表示使用蟻羣優化算法，爲什麼不在您的問題中說出來？
• 這種「重複」是應該的，好了，重複，所以有可能你給我們（這是不正常輸出）輸出是不明確的解決方案，而該算法的provisory結果。

Answer 3

在這篇文章中，實施簡單的解決方案進行了討論。

• 考慮城市1或0作爲起點和終點。由於路線是循環的 ，我們可以考慮任何一點作爲起點。

• 生成所有（N-1）！城市排列。每種排列的

• 計算成本，並保持最小的跟蹤成本 排列。

• 返回以最小的成本置換。

#include <bits/stdc++.h> using namespace std;

int main(void){ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     int n; 
     scanf("%d",&n); 
     int graph[n][n]; 
     for(int i =0;i<n;i++){ 
      for(int j =0;j<n;j++){ 
       scanf("%d",&graph[i][j]); 
      } 
     } 
     vector<int> v; 
     int s = 0; 
     for(int i =0;i<n;i++){ 
      if(i!=s){ 
       v.push_back(i); 
      } 
     } 
     int ans = INT_MAX; 
     do{ 
      int current_pathsum = 0; 
      int k = s; 
      for(int i = 0;i<v.size();i++){ 
       current_pathsum += graph[k][v[i]]; 
       k = v[i]; 
      } 
      current_pathsum += graph[k][s]; 
      ans = min(ans,current_pathsum); 
     }while(next_permutation(v.begin(),v.end())); 
     cout<<ans<<endl; 
    } 
}