2

我正在尝试从旅行推销员问题算法中用 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
4

3 回答 3

3

首先，我猜My Program你的意思是The program in the paper因为它基本上是过时的 C++。标准库头文件没有.h附加，它conio.h是一个 MS-DOS 头文件——我见过的大多数代码都来自 Borland Turbo C++。如果您要尝试在现代系统上编译该演示，请记住这一点。

接下来，您正在查看的是邻接矩阵。我根本不相信矩阵是输出的一部分。我相信它是正在使用的模型的一部分，用于演示目的。我相信，鉴于您有一个pheromone矩阵，您在这里看到的是Ant Colony Optimization，这是一种解决 TSP 和其他可以简化为它的问题的概率方法。

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

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

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

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

  • 考虑城市 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;
    }
}
于 2018-01-02T04:46:52.953 回答