Задача коммивояжёра (реализация на C++)

C++   18 Январь 2012  Автор статьи:  

На территории государства X расположено n городов, между некоторыми парами которых проложены дороги (не обязательно двунаправленные). Каждая из них характеризуется положительным числом – своей длиной. Из одного города в другой ведёт не более одной дороги. Бродячий торговец хочет обойти все города ровно по одному разу и вернуться в исходный пункт (начинать движение можно в произвольном городе). Необходимо найти минимальное расстояние, которое ему придётся пройти, или выяснить, что искомого маршрута не существует.

Входные данные:

Натуральное число N (1\le N \le 16) и квадратная матрица D порядка N, содержащая длины дорог между всеми парами городов. Если какой-либо дороги не существует, соответствующий элемент матрицы равен нулю.

Выходные данные:
Минимальная длина пути.

Реализация решения

Подробный разбор алгоритма см. в этой статье. Обратите внимание, что значение константы NMAX можно увеличить.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int inf=1E9,NMAX=16;
int n,i,j,k,m,temp,ans,d[NMAX][NMAX],t[1<<NMAX][NMAX];
bool get(int nmb,int x)
{ return (x&(1<<nmb))!=0; }
int main()
{
 cin >>n;
 for (i=0;i<n;++i)
  for (j=0;j<n;++j) cin>>d[i][j];
 t[1][0]=0; m=1<<n;
 for (i=1;i<m;i+=2)
  for (j=(i==1)?1:0;j<n;++j)
  {
   t[i][j]=inf;
   if (j>0 && get(j,i))
   {
    temp=i^(1<<j);
    for (k=0;k<n;++k)
     if (get(k,i) && d[k][j]>0) t[i][j]=min(t[i][j],t[temp][k]+d[k][j]);
   }
  }
 for (j=1,ans=inf;j<n;++j)
  if (d[j][0]>0) ans=min(ans,t[m-1][j]+d[j][0]);
 if (ans==inf) cout<<-1; else cout<<ans;
}

Автор статьи – Сухов Сергей

  • Юра

    поскажите пожалуйста по этапно как создавать проект (где и как),видает слишком много ошыбок при вводе вашего кода

    • http://cybern.ru/ lordrp

      Ну это слишком сложная задача для вас, если вы ее запустить не можете… Начните с уроков для начинающих, там все это поэтапно расписано.

  • Евгений

    При написании кода был использован жадный алгоритм?

  • Kevin Victor Johnson

    Не понимаю как,но оно работает…

  • Саша

    Скажите пожалуйста, что может быть? программа запускается, и когда я ввожу матрицу, программа выключается. Побывал в конце кода ставить cin.get(), но результат все ровно не выдает

Научиться программировать

  • на Delphi

  • на Java

  • на C++