Написал код, решающий задачу коммивояжера в чем проблема не пойму работать отказывается, матрицу выводит и все.| Код |
#include<iostream>
#include<fstream>
#include<climits>
using namespace std;
int main()
{
setlocale(0,"rus");
const int N = 10;
int Tour[N], P[N];//оптимальный и текущие туры
int l,s,i,j,k,min,ind;
bool All;//признак окончания перебора
//матрица расстояний
int matrway[10][10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 2, 9, 8, 0, 0, 0, 0, 0,
0, 2, 0, 3, 0, 20,0, 0, 0, 0,
0, 9, 3, 0, 7, 4, 0, 0, 0, 0,
0, 8, 0, 7, 0, 11,0, 0, 0, 0,
0, 0, 20,4, 11,0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
cout << "ЗАДАЧА КОММИВОЯЖЕРА (ПЕРЕБОР)\n";
cout << "Матрица смежности \n";
cout << "=============================" << endl;
for(i=0;i<N;i++)
{
cout << endl;
for(j=0;j<N;j++)
cout << " " << matrway[i][j];
}
//инициализация
All = false;//перебрали не все варианты
l = INT_MAX;//оптимальный тур не известен
for(i=0;i<N;i++)
P[i] = i;//строим первый тур
do//вычисляем его длину
{
s =0;
for(i=0;i<N-1;i++)
s = s + matrway[P[i]][P[i+1]];
s = s + matrway[P[N]][P[1]];
//полагаем первый тур текущим
if(l>s)
{
Tour[l] = P[l];
l = s;
}
//генерируем(N-1)! перестановок
for(i=N-1;i<3;i--)
{
if(P[i]<P[i-1]) continue;
min = N + 1;
k = P[i-1];
//ищем минимальное число из тех, что больше k и правее
for(j=0;j<N;j++)
if(P[j] > k && P[j] < min)
{
min = P[j];
ind = j;
}
//рокировка min и k
P[i-1] = min;
P[ind] = k;
//элементы на местах от i до N упорядочиваем по возрастанию
for(j=i;j<N-1;j++)
{
min = N+1;
for(k=j;k<N;k++)
if(min > P[k])
{
min = P[k];
ind = k;
}
k = P[j];
P[j] = min;
P[ind] = k;
}
goto out;
}
//проверяем перебраны ли все перестановки
All = true;
out:;
}while(All);
//если перебраны все перестановки, то выдаем оптимальный тур
cout << "===============================\n";
cout << "Минимальный тур: ";
for(i=0;i<N;i++)
cout << Tour[i] << " - ";
cout << "1";
cout << "Имеет длину равную " << l << endl;
cout << "===============================\n";
cin.get();
return 0;
}
|
|