Задача коммивояжера

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

Во-первых, я предполагаю, что когда вы говорите My Program, вы имеете в виду The program in the paper, поскольку он в основном устарел в C ++. К заголовкам стандартной библиотеки не добавляется .h, а conio.h - это заголовок MS-DOS - большая часть кода, который я видел, использует Borland Turbo C ++. Стоит помнить, если вы собираетесь попытаться скомпилировать эту демонстрацию в современной системе.

Далее, вы смотрите на матрицу смежности. Я не верю, что матрица является частью вывода вообще; Я считаю, что это часть модели, используемой в демонстрационных целях. Я считаю, что если у вас есть матрица pheromone, то, что вы смотрите здесь, это Оптимизация колоний муравьев , вероятностный метод решения TSP и других проблем, которые можно свести к нему. *

Исходя из вашего вывода, неясно, где и как хранится результат, и, поскольку это домашняя работа, я ленив, а вы просто просите прямой ответ, я не собираюсь читать этот код , Предпосылка оптимизации колонии муравьев заключается в том, что следы феромонов, проложенные муравьями, которые ходят по графику случайным образом, затухают с течением времени (количество итераций). Чем дольше муравей движется по определенной вершине (расстоянию), тем больше распадается положенный феромон. В этот момент муравьи начинают принимать решения, основываясь на силе проложенного феромона на пути. Таким образом, происходит то, что муравьи начинают отдавать предпочтение определенным маршрутам по сравнению с другими и постоянно информируют феромон на этом пути.

Итак, где-то там должна быть матрица, подобная матрице смежности, хранящая уровни феромонов для каждого маршрута. В сочетании с длиной маршрута каждая итерация должна определять скорость затухания.

Answer 2

В этом посте обсуждается реализация простого решения.

• Рассмотрим город 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;
    }
}

Answer 3

• Ваши входные переменные a, b, c никогда не используются.
• Ваша переменная ctr используется точно так же, как переменная k того же цикла.
• Ваша матрица феномонов указывает на использование алгоритма оптимизации колонии муравьев, почему бы просто не сказать это в вашем вопросе?
• Такая «итерация» должна быть, ну, в общем, повторной, так что, вероятно, вы дадите нам результат (который не являетсянормальный вывод) - не окончательное решение, а скорее провокационный результат алгоритма.