Исходник решения задачи коммивояжера методом Прима на C++ и Методом ветвей и границ на Pascal

Код на C++
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
 
int wpchk(int w, int *wpts)
{
	int i=0;
	int flg=0;
	while(wpts[i]!=-1)
	{
		if(wpts[i]==w){flg=1;}
		i++;
	}
 
	if (flg==0) {return 0;} else return 1;
}
 
void main()
{
	srand( (unsigned)time( NULL ) );
 
	//int prices[10][10];
	int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};
	int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
	int start=-1;
	int end=-1;
	int min;
	int imin;
 
*///                        0  1  2  3  4  5  6  7  8  9
	int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
			    0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
			    0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
			    0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
			    0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
			    0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
			    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
			    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
			    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
			    0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9
 
	printf("Enter № of start location:");
	scanf("%i",&start);
	printf("Enter № of finish location:");
	scanf("%i",&end);
	waypoint[0]=start;
	int n=0;
	int w;
	while(waypoint[n]!=end)
	{	
		min=0;
		w=waypoint[n];
		for(int i=0;i<10;i++)
		{
			if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;}
		}
		n++;
		waypoint[n]=imin;
	}
 
	printf("\nThe way is:\n");
	int i=0;
	while(waypoint[i]!=-1)
	{
        printf("%i ",waypoint[i]);
		i++;
	}
	getchar();
	getchar();
}
При использовании обязательна ссылка на http://DMTSoft.ru

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3.. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами j принадлежит Т=(1,2,3.. n ). Тур коммивояжера может быть описан циклической перестановкой t =( j 1 , j 2 ,.., j n , j 1 ), причём все j1 .. jn – разные номера; повторяющийся в начале и в конце j 1 , показывает, что перестановка зациклена. Расстояния между парами вершин С ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t , чтобы минимизировать функционал

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

Во-первых, в постановке С ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех j принадлежит Т:

С ij >= 0; C jj =бесконечность

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i , j :

С ij = С ji .

и удовлетворять неравенству треугольника, т.е. для всех:

С ij + С jk >= C ik

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжера все туры t =( j 1 , j 2 ,.., j n , j 1 ) и t '=( j 1 , j n ,.., j 2 , j 1 ) имеют разную длину и должны учитываться оба. Разных туров очевидно ( n -1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j 1 , а оставшиеся n -1 номеров переставим всеми ( n -1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t '.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро ( i , j ) проведено, если С ij =0 и не проведено, если С ij =1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра ( i , j )= С ij . Найти гамильтонов цикл минимальной длины.

В несимметричной задаче коммивояжера вместо “цикл” надо говорить “контур”, а вместо “ребра” - “дуги” или “стрелки”.

Некоторые прикладные задачи формулируются как задача коммивояжера, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматривать не будем.

Решение задачи коммивояжера жадным алгоритмом

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении задачи коммивояжера жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”.

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть f B - настоящий минимум, а f A - тот квазиминимум, который получен по алгоритму. Ясно , что f A / f B >=1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

f A / f B >=1+ n E,

где, как обычно в высшей математике, E>=0, но, против обычая, может быть очень большим. Величина E и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность E.

Предположим теперь, что имеется алгоритм А решения задачи коммивояжера, погрешность которого нужно оценить. Возьмем произвольный граф G ( V , E ) и по нему составим входную матрицу задачи коммивояжера:

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и f B = n . Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+ n E. Но тогда f A E ( n -1)+(1+ n E) так что f A / f B =1+ n E т.е. превосходит погрешность E на заданную неравенством (5). О величине ? в нашем рассуждении мы не договаривались, так что E может быть произвольно велик.

Таким образом доказана следующая теорема.

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

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (4).

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт? Рис.2 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт (рис.3.) одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья – вершинами.

Когда через точку проводится линия, то используется два ребра – одно для входа в вершину, одно – для выхода. Если степень вершины нечетна – то в ней линия должна начаться или кончиться. На рис. 3 вершин нечетной степени две: в одной линия начинается, в другой – кончается. Однако на рис. 4 имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень.

Верно и обратное утверждение: если все вершины имеют четную степень, то фигуру можно нарисовать одной незамкнутой линией. Действительно, процесс проведения линии может кончиться, только если линия придет в вершину, откуда уже выхода нет: все ребра, присоединенные к этой вершине (обычно говорят: инцидентные этой вершине), уже прочерчены. Если при этом нарисована вся фигура, то нужное утверждение доказано; если нет, удалим уже нарисованную часть G '. После этого от графа останется одна или несколько связных компонент; пусть G ' – одна из таких компонент. В силу связности исходного графа G , G ' и G '' имеют хоть одну общую вершину, скажем, v . Если в G '' удалены какие-то ребра, то по четному числу от каждой вершины. Поэтому G '' – связный и все его вершины имеют четную степень. Построим цикл в G '' (может быть, не нарисовав всего G '') и через v добавим прорисованную часть G '' к G '. Увеличивая таким образом прорисованную часть G ', мы добьемся того, что G ' охватит весь G .

Эту задачу когда-то решил Эйлер, и замкнутую линию, которая покрывает все ребра графа, теперь называю эйлеровым циклом. По существу была доказана следующая теорема.

Эйлеров цикл в графе существует тогда и только тогда, когда (1) граф связный и (2) все его вершины имеют четные степени.

Код на Pascal
 
 
const COUNT_POINTS=6;
 
type
  ARRN=array[1..COUNT_POINTS] of integer;
  ARRNN=array[1..COUNT_POINTS,1..COUNT_POINTS] of integer;
 
PROCEDURE FITSP(N,S,INF:INTEGER; VAR W:ARRNN; VAR ROUTE:ARRN; VAR PATH_WEIGHT:INTEGER);
   VAR END1,END2,FARTHEST,I,INDEX,
          INSCOST,J,MAXDIST,NEWCOST,NEXTINDEX :INTEGER;
       CYCLE,DIST                             :ARRN;
BEGIN
   FOR I:=1 TO N DO CYCLE[I]:=0;
   CYCLE[S]:=S;
   FOR I:=1 TO N DO DIST[I]:=W[S,I];
   PATH_WEIGHT:=0;
   FOR I:=1 TO N-1 DO
   BEGIN
      MAXDIST:=-INF;
      FOR J:=1 TO N DO
         IF CYCLE[J] = 0 THEN
            IF DIST[J] > MAXDIST THEN
            BEGIN
               MAXDIST:=DIST[J];  FARTHEST:=J
            END;
      INSCOST:=INF;  INDEX:=S;
      FOR J:=1 TO I DO
      BEGIN
         NEXTINDEX:=CYCLE[INDEX];
         NEWCOST:=W[INDEX,FARTHEST]+W[FARTHEST,NEXTINDEX]-
                  W[INDEX,NEXTINDEX];
         IF NEWCOST < INSCOST THEN
         BEGIN
            INSCOST:=NEWCOST;
            END1:=INDEX;  END2:=NEXTINDEX
         END;
         INDEX:=NEXTINDEX
      END;  { FOR J }
      CYCLE[FARTHEST]:=END2;  CYCLE[END1]:=FARTHEST;
      PATH_WEIGHT:=PATH_WEIGHT+INSCOST;
      FOR J:=1 TO N DO
         IF CYCLE[J] = 0 THEN
            IF W[FARTHEST,J] < DIST[J] THEN DIST[J]:=W[FARTHEST,J]
   END;  { FOR I }
   INDEX:=S;
   FOR I:=1 TO N DO
   BEGIN
      ROUTE[I]:=INDEX;  INDEX:=CYCLE[INDEX]
   END
END;
 
 
procedure THREEOPT(N:integer; var W:ARRNN; var ROUTE:ARRN);
 
   type SWAPTYPE  =(ASYMMETRIC,SYMMETRIC);
        SWAPRECORD=record
                      X1,X2,Y1,Y2,Z1,Z2,GAIN:integer;
                      CHOICE                :SWAPTYPE
                   end;
   var BESTSWAP,SWAP:SWAPRECORD;
       I,INDEX,J,K  :integer;
       PTR          :ARRN;
 
   procedure SWAPCHECK(var SWAP:SWAPRECORD);
      var DELWEIGHT,MAX:integer;
   begin
      with SWAP do begin
         GAIN:=0;
         DELWEIGHT:=W[X1,X2]+W[Y1,Y2]+W[Z1,Z2];
         MAX:=DELWEIGHT-(W[Y1,X1]+W[Z1,X2]+W[Z2,Y2]);
         if MAX > GAIN then begin
            GAIN:=MAX;  CHOICE:=ASYMMETRIC
         end;
         MAX:=DELWEIGHT-(W[X1,Y2]+W[Z1,X2]+W[Y1,Z2]);
         if MAX > GAIN then begin
            GAIN:=MAX;  CHOICE :=SYMMETRIC
         end
      end 
  end;
 
   procedure REVERSE(START,FINISH:integer);
      var AHEAD,LAST,NEXT:integer;
   begin
      if START <> FINISH then begin
         LAST:=START;  NEXT:=PTR[LAST];
         repeat
            AHEAD:=PTR[NEXT];  PTR[NEXT]:=LAST;
            LAST:=NEXT;  NEXT:=AHEAD;
         until LAST = FINISH
      end  { if START <> FINISH }
   end;  { RESERVE }
 
begin                                                   { MAIN BODY }
   for I:=1 to N-1 do PTR[ROUTE[I]]:=ROUTE[I+1];
   PTR[ROUTE[N]]:=ROUTE[1];
   repeat  { until BESTSWAP.GAIN = 0 }
      BESTSWAP.GAIN:=0;
      SWAP.X1:=1;
      for I:=1 to N do begin
         SWAP.X2:=PTR[SWAP.X1];  SWAP.Y1:=SWAP.X2;
         for J:=2 to N-3 do begin
            SWAP.Y2:=PTR[SWAP.Y1];  SWAP.Z1:=PTR[SWAP.Y2];
            for K:=J+2 to N-1 do begin
               SWAP.Z2:=PTR[SWAP.Z1];
               SWAPCHECK(SWAP);
               if SWAP.GAIN > BESTSWAP.GAIN then BESTSWAP:=SWAP;
               SWAP.Z1:=SWAP.Z2
            end;  { for K }
            SWAP.Y1:=SWAP.Y2
         end;  { for J }
         SWAP.X1:=SWAP.X2
      end;  { for I }
      if BESTSWAP.GAIN > 0 then
         with BESTSWAP do begin
            if CHOICE = ASYMMETRIC then begin
               REVERSE(Z2,X1);
               PTR[Y1]:=X1;  PTR[Z2]:=Y2
            end
            else begin
               PTR[X1]:=Y2;  PTR[Y1]:=Z2
            end;
            PTR[Z1]:=X2;
         end  { with BESTSWAP }
   until BESTSWAP.GAIN = 0;
   INDEX:=1;
   for I:=1 to N do begin
      ROUTE[I]:=INDEX;  INDEX:=PTR[INDEX]
   end
end;
 
PROCEDURE TWOOPT( N:INTEGER; VAR W:ARRNN; VAR ROUTE:ARRN; VAR PATH_WEIGHT:INTEGER);
 
   VAR AHEAD,I,I1,I2,INDEX,J,J1,J2,
       LAST,LIMIT,MAX,MAX1,NEXT,S1,S2,T1,T2:INTEGER;
       PTR                                 :ARRN;
BEGIN
   FOR I:=1 TO N-1 DO PTR[ROUTE[I]]:=ROUTE[I+1];
   PTR[ROUTE[N]]:=ROUTE[1];
   REPEAT  { UNTIL MAX = 0 }
      MAX:=0;  I1:=1;
      FOR I:=1 TO N-2 DO
      BEGIN
         IF I = 1 THEN LIMIT:=N-1
         ELSE LIMIT:=N;
         I2:=PTR[I1];  J1:=PTR[I2];
         FOR J:=I+2 TO LIMIT DO
         BEGIN
            J2:=PTR[J1];
            MAX1:=W[I1,I2]+W[J1,J2]-(W[I1,J1]+W[I2,J2]);
            IF MAX1 > MAX THEN
            BEGIN   { BETTER PAIR HAS BEEN FOUND }
               S1:=I1;  S2:=I2;
               T1:=J1;  T2:=J2;
               MAX:=MAX1
            END;
            J1:=J2
         END;  { FOR J }
         I1:=I2
      END;  { FOR I }
      IF MAX > 0 THEN
      BEGIN                    { SWAP PAIR OF EDGES }
         PTR[S1]:=T1;
         NEXT:=S2;  LAST:=T2;
         REPEAT
            AHEAD:=PTR[NEXT];  PTR[NEXT]:=LAST;
            LAST:=NEXT;  NEXT:=AHEAD
         UNTIL NEXT = T2;
         PATH_WEIGHT:=PATH_WEIGHT-MAX
      END  { IF MAX > 0 }
   UNTIL MAX = 0;
   INDEX:=1;
   FOR I:=1 TO N DO
   BEGIN
      ROUTE[I]:=INDEX;  INDEX:=PTR[INDEX]
   END
END;
 
var
  W      :ARRNN=((0, 0, 0, 3, 3, 6),
                 (0, 0, 1, 4, 1, 0),
                 (1, 2, 0, 0, 0, 3),
                 (4, 5, 0, 0, 0, 3),
                 (4, 2, 0, 0, 0, 0),
                 (7, 1, 3, 3, 0, 0)
                 );
 
  PATH_WEIGHT:integer;
  ROUTE  :ARRN;
  i:integer;
begin
    PATH_WEIGHT:=0;
    for i:=1 to COUNT_POINTS do ROUTE[i]:=i;
    FITSP(COUNT_POINTS,1,999999,W,ROUTE,PATH_WEIGHT);
    TWOOPT(COUNT_POINTS,W,ROUTE,PATH_WEIGHT);
    THREEOPT(COUNT_POINTS,W,ROUTE);
    for i:=1 to COUNT_POINTS do write(inttostr(ROUTE[i])+'->');
    write(inttostr(1)+' = '+inttostr(PATH_WEIGHT));
end;
При использовании обязательна ссылка на http://DMTSoft.ru