旅行推销员问题

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 ++的代码。如果您打算在现代系统上编译该演示，请记住这一点。

接下来，你正在看的是一个邻接矩阵。我不相信矩阵是输出的一部分;我认为它是所用模型的一部分，用于演示目的。我相信，鉴于你有一个pheromone矩阵，你在这里看到的是Ant Colony Optimisation，一种解决TSP的概率方法和其他可以减少的问题。

从你的输出，不清楚结果的存储位置和方式，因为这是家庭作业，我很懒，你只是要求一个彻头彻尾的答案，我不打算阅读那段代码。蚁群优化的前提是蚂蚁铺设的信息素踪迹随机走动，随着时间的推移衰减（迭代次数）。蚂蚁沿特定顶点（距离）移动所需的时间越长，所沉积的信息素衰减得越多。此时，蚂蚁开始根据沿路径铺设的信息素的强度做出决定。所以会发生什么事情是蚂蚁开始偏爱某些路线而不是其他路线，并且不断地沿着该路径重新强制使用信息素。

因此，在那里的某处，必须有一个像邻接矩阵这样的矩阵，存储每条路线的信息素水平。结合路线的长度，每次迭代都应检测衰减速率。

Answer 2

• 从不使用输入变量a，b，c。
• 您的变量ctr以与同一循环的变量k完全相同的增量方式使用。
• 你的phenomone矩阵表明使用蚁群优化算法，为什么不在你的问题中说出来？
• 这样的“迭代”应该是迭代的，所以你给我们的输出（这不是正常的输出）可能不是确定的解决方案，而是算法的一个附带结果。

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;
    }
}