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

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

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

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

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

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

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

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

[cc lang=»cpp» lines=»-1″]
#include
using namespace std;
const int inf=1E9,NMAX=16;
int n,i,j,k,m,temp,ans,d[NMAX][NMAX],t[1<>n;
for (i=0;i>d[i][j];
t[1][0]=0; m=1<0 && get(j,i))
{
temp=i^(1<0) t[i][j]=min(t[i][j],t[temp][k]+d[k][j]);
}
}
for (j=1,ans=inf;j0) ans=min(ans,t[m-1][j]+d[j][0]);
if (ans==inf) cout<<-1; else cout<Автор статьи – Сухов Сергей

  • Юра

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

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

  • Евгений

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

  • Kevin Victor Johnson

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

  • Саша

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

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

  • на Delphi

  • на Java

  • на C++