旅行商问题

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

输出：

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

首先，我猜当你说我的程序时，你的意思是论文中的程序，因为它基本上是过时的C++。标准库头文件没有附加 .h，而 conio.h 是一个 MS-DOS 头文件 - 我见过的大多数代码都使用来自 Borland Turbo 的代码C++。如果您打算尝试在现代系统上编译该演示，请记住这一点。

接下来，您看到的是邻接矩阵。我根本不相信矩阵是输出的一部分；我相信它是用于演示目的的模型的一部分。我相信，鉴于您有一个信息素矩阵，您在这里看到的是蚁群优化，一种解决 TSP 和其他可简化为 TSP 的问题的概率方法。

从你的输出来看，不清楚结果存储在哪里或如何存储，而且由于这是家庭作业，我很懒，你只是要求一个直接的答案，我不会阅读该代码。蚁群优化的前提是蚂蚁在图上随机行走所铺设的信息素轨迹，会随着时间（迭代次数）而衰减。蚂蚁沿着特定顶点（距离）移动的时间越长，所放置的信息素衰减得越多。此时，蚂蚁开始根据沿路径铺设的信息素的强度做出决定。因此，蚂蚁开始比其他路线更喜欢某些路线，并沿着该路线不断强化信息素。

因此，在那里的某个地方，必须有一个类似于邻接矩阵的矩阵，存储每条路线的信息素水平。结合路线的长度，每次迭代都应该检测衰减率。

Answer 2

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

Answer 3

在这篇文章中，讨论了简单解决方案的实现。

• 将城市 1 或 0 视为起点和终点。由于路线是
  循环，可以考虑任意点作为起点。

• 生成所有 (n-1) 个！城市的排列。

• 计算每个排列的成本并跟踪最小成本
  排列。

• 返回具有最小成本的排列。

#include
使用命名空间 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;
    }
}