旅行商问题 [英] Travelling Salesman Problem

查看:162
本文介绍了旅行商问题的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在尝试从Traveling Salesman问题算法开发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;
浮点数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<输入迭代次数,城市,蚂蚁;
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<<信息素矩阵<< 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;
}
}

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

cout<< 在迭代之后<< endl; (i = 0; i <3; i ++)的

{
ctr = 0;
for(int k = 0; k< 3; k ++)
{
// mem [i] [k] =(rand()%b)+1;
// cout<<内存<< 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);
}
其他
{
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();
}

输出:

 输入迭代次数,城市,蚂蚁3 
4
4
0 0.003967 0.335154
0.033265 0 0.2172
0.536973 0.195776 0
信息素矩阵
0 1 1
1 0 1
1 1 0
迭代后
hhhhhhh0.949919EXPLORATION
hhhhhhh0.356777EXPLOITATION
hhhhhhh0.356777EXPLOITATION
hhhhhh0.356777EXPLOITATION
hhhhhhh0.356777EXPLOITATION
hhhhhhc0.949919EXPLOITATION
$ b

解决方案

首先,我猜您在说我的程序时,您的意思是本文中的程序,因为它基本上已经过时了C ++。标准库头文件没有附加 .h ,而 conio.h 是MS-DOS头文件-大多数代码我已经看到这种用法来自Borland Turbo C ++。如果您要尝试在现代系统上编译该演示,那么请牢记。



接下来,您要看的是一个邻接矩阵。我完全不相信矩阵是输出的一部分;我相信它是用于演示目的的模型的一部分。我相信,假设您有一个信息素矩阵,那么您在这里看到的是蚁群优化,一种解决TSP和其他问题的概率方法。



从您的输出,目前尚不清楚结果存储在何处或如何存储,并且由于这是家庭作业,因此我很懒惰,而您只是要求一个完整的答案,因此我不打算阅读该代码。蚁群优化的前提是,蚂蚁放置的信息素踪迹随时间(迭代数)随时间衰减而随机分布。蚂蚁沿着特定顶点(距离)移动所需的时间越长,放置的信息素的衰减就越大。此时,蚂蚁开始根据沿路径放置的信息素的强度做出决策。因此,发生的事情是蚂蚁开始偏爱某些路线而不是其他路线,并不断沿该路径增强信息素。



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


I am trying to develop a program in C++ from Travelling Salesman Problem Algorithm. I need a distance matrix and a cost matrix. After using all the formulas, i get a new resultant matrix. But I dont understand what that matrix shows. Suppose the resultant matrix is:

1 2 3
4 5 6
7 8 9

Now I want to know what this matrix shows? Assume I have 3 cities to traverse.

Please tell me the flow. A sample program of this algorithm will be more favorable.. Thank you.

My Program is:

#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

解决方案

First up, I'm guessing when you say My Program you mean The program in the paper since it is basically out of date C++. Standard library headers don't have .h appended, and conio.h is an MS-DOS header - most code that I've seen that uses that comes from Borland Turbo C++. Worth bearing in mind if you're going to try to compile that demo on a modern system.

Next up, what you're looking at is an adjacancy matrix. I don't believe that matrix is part of the output at all; I believe it is part of the model being used, for demonstration purposes. I believe, given you have a pheromone matrix, that what you're looking at here is Ant Colony Optimisation, a probabilistic method of solving the TSP and other problems that can be reduced to it.

From your output, it isn't clear where or how the result is being stored, and since this is homework, I am lazy and you're just asking for an outright answer, I'm not going to read that code. The premise of Ant Colony optimisation is that pheromone trails laid by ants, which walk the graph at random, decay over time (number of iterations). The longer it takes an ant to move along a particular vertex (distance), the more the laid pheromone decays. At this point, ants start to make decisions based on the strength of the laid pheromone along a path. So what happens is ants start to prefer certain routes over others, and continually re-inforce the pheromone along that path.

So, somewhere in there, there must be a matrix like the adjacancy matrix, storing the pheromone levels for each route. Combined with the length of the route, each iteration should detect a rate of decay.

这篇关于旅行商问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆