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


Добавил:DMT
Дата создания:25 апреля 2008, 14:23
Дата обновления:9 мая 2008, 0:32
Просмотров:64055 последний сегодня, 7:30
Комментариев: 2
Исходник решения задачи коммивояжера методом Прима на C++
Алгоритм:
Пусть n - это количество вершин графа. Тогда в цикле n-1 выбирается самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранным. Для проверки того, что новое ребро не образует цикла с уже выбранными, каждую вершину i окрашивают в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом после выбора n-1 ребер все вершины получают один цвет.
Алгоритм Прима:
1. (ввод). Ввести матрицу расстояний D={dij}, i,j=1,…,n.
2. (инициализация). Приписать разные цвета всем вершинам: coli:=i; длина дерева L:=0.
3. (общий шаг). В цикле по k:=1 to n-1 do найти ребро минимальной длины между вершинами разного цвета: пусть это ребро (i,j).
Запомнить результат: res1[k]:=i; res2[k]:=j;
Перекрасить вершины: I1:=col[i]; j1:=col[j].
В цикле по m:=1 to n do
If col[m]=j1 then col[m]:=i1;
Нарастить длину дерева: L:=L+d[i,j].
Конец цикла по k.
4.(вывод). Вывести res1, res2.
Код на C++
  1. #include <stdlib.h>
  2. #include <time.h>
  3. #include <stdio.h>
  4.  
  5. int wpchk(int w, int *wpts)
  6. {
  7. int i=0;
  8. int flg=0;
  9. while(wpts[i]!=-1)
  10. {
  11. if(wpts[i]==w){flg=1;}
  12. i++;
  13. }
  14.  
  15. if (flg==0) {return 0;} else return 1;
  16. }
  17.  
  18. void main()
  19. {
  20. srand( (unsigned)time( NULL ) );
  21.  
  22. //int prices[10][10];
  23. int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};
  24. int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
  25. int start=-1;
  26. int end=-1;
  27. int min;
  28. int imin;
  29.  
  30. */// 0 1 2 3 4 5 6 7 8 9
  31. int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
  32. 0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
  33. 0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
  34. 0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
  35. 0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
  36. 0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
  37. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
  38. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
  39. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
  40. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9
  41.  
  42. printf("Enter № of start location:");
  43. scanf("%i",&start);
  44. printf("Enter № of finish location:");
  45. scanf("%i",&end);
  46. waypoint[0]=start;
  47. int n=0;
  48. int w;
  49. while(waypoint[n]!=end)
  50. {
  51. min=0;
  52. w=waypoint[n];
  53. for(int i=0;i<10;i++)
  54. {
  55. if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;}
  56. }
  57. n++;
  58. waypoint[n]=imin;
  59. }
  60.  
  61. printf("\nThe way is:\n");
  62. int i=0;
  63. while(waypoint[i]!=-1)
  64. {
  65. printf("%i ",waypoint[i]);
  66. i++;
  67. }
  68. getchar();
  69. getchar();
  70. }
При использовании обязательна ссылка на 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 ) и по нему составим входную матрицу задачи коммивояжера:

С [i,j]={

1,если ребро ( i , j ) принадлежит Е

1+ n 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
  1.  
  2.  
  3. const COUNT_POINTS=6;
  4.  
  5. type
  6. ARRN=array[1..COUNT_POINTS] of integer;
  7. ARRNN=array[1..COUNT_POINTS,1..COUNT_POINTS] of integer;
  8.  
  9. PROCEDURE FITSP(N,S,INF:INTEGER; VAR W:ARRNN; VAR ROUTE:ARRN; VAR PATH_WEIGHT:INTEGER);
  10. VAR END1,END2,FARTHEST,I,INDEX,
  11. INSCOST,J,MAXDIST,NEWCOST,NEXTINDEX :INTEGER;
  12. CYCLE,DIST :ARRN;
  13. BEGIN
  14. FOR I:=1 TO N DO CYCLE[I]:=0;
  15. CYCLE[S]:=S;
  16. FOR I:=1 TO N DO DIST[I]:=W[S,I];
  17. PATH_WEIGHT:=0;
  18. FOR I:=1 TO N-1 DO
  19. BEGIN
  20. MAXDIST:=-INF;
  21. FOR J:=1 TO N DO
  22. IF CYCLE[J] = 0 THEN
  23. IF DIST[J] > MAXDIST THEN
  24. BEGIN
  25. MAXDIST:=DIST[J]; FARTHEST:=J
  26. END;
  27. INSCOST:=INF; INDEX:=S;
  28. FOR J:=1 TO I DO
  29. BEGIN
  30. NEXTINDEX:=CYCLE[INDEX];
  31. NEWCOST:=W[INDEX,FARTHEST]+W[FARTHEST,NEXTINDEX]-
  32. W[INDEX,NEXTINDEX];
  33. IF NEWCOST < INSCOST THEN
  34. BEGIN
  35. INSCOST:=NEWCOST;
  36. END1:=INDEX; END2:=NEXTINDEX
  37. END;
  38. INDEX:=NEXTINDEX
  39. END; { FOR J }
  40. CYCLE[FARTHEST]:=END2; CYCLE[END1]:=FARTHEST;
  41. PATH_WEIGHT:=PATH_WEIGHT+INSCOST;
  42. FOR J:=1 TO N DO
  43. IF CYCLE[J] = 0 THEN
  44. IF W[FARTHEST,J] < DIST[J] THEN DIST[J]:=W[FARTHEST,J]
  45. END; { FOR I }
  46. INDEX:=S;
  47. FOR I:=1 TO N DO
  48. BEGIN
  49. ROUTE[I]:=INDEX; INDEX:=CYCLE[INDEX]
  50. END
  51. END;
  52.  
  53.  
  54. procedure THREEOPT(N:integer; var W:ARRNN; var ROUTE:ARRN);
  55.  
  56. type SWAPTYPE =(ASYMMETRIC,SYMMETRIC);
  57. SWAPRECORD=record
  58. X1,X2,Y1,Y2,Z1,Z2,GAIN:integer;
  59. CHOICE :SWAPTYPE
  60. end;
  61. var BESTSWAP,SWAP:SWAPRECORD;
  62. I,INDEX,J,K :integer;
  63. PTR :ARRN;
  64.  
  65. procedure SWAPCHECK(var SWAP:SWAPRECORD);
  66. var DELWEIGHT,MAX:integer;
  67. begin
  68. with SWAP do begin
  69. GAIN:=0;
  70. DELWEIGHT:=W[X1,X2]+W[Y1,Y2]+W[Z1,Z2];
  71. MAX:=DELWEIGHT-(W[Y1,X1]+W[Z1,X2]+W[Z2,Y2]);
  72. if MAX > GAIN then begin
  73. GAIN:=MAX; CHOICE:=ASYMMETRIC
  74. end;
  75. MAX:=DELWEIGHT-(W[X1,Y2]+W[Z1,X2]+W[Y1,Z2]);
  76. if MAX > GAIN then begin
  77. GAIN:=MAX; CHOICE :=SYMMETRIC
  78. end
  79. end
  80. end;
  81.  
  82. procedure REVERSE(START,FINISH:integer);
  83. var AHEAD,LAST,NEXT:integer;
  84. begin
  85. if START <> FINISH then begin
  86. LAST:=START; NEXT:=PTR[LAST];
  87. repeat
  88. AHEAD:=PTR[NEXT]; PTR[NEXT]:=LAST;
  89. LAST:=NEXT; NEXT:=AHEAD;
  90. until LAST = FINISH
  91. end { if START <> FINISH }
  92. end; { RESERVE }
  93.  
  94. begin { MAIN BODY }
  95. for I:=1 to N-1 do PTR[ROUTE[I]]:=ROUTE[I+1];
  96. PTR[ROUTE[N]]:=ROUTE[1];
  97. repeat { until BESTSWAP.GAIN = 0 }
  98. BESTSWAP.GAIN:=0;
  99. SWAP.X1:=1;
  100. for I:=1 to N do begin
  101. SWAP.X2:=PTR[SWAP.X1]; SWAP.Y1:=SWAP.X2;
  102. for J:=2 to N-3 do begin
  103. SWAP.Y2:=PTR[SWAP.Y1]; SWAP.Z1:=PTR[SWAP.Y2];
  104. for K:=J+2 to N-1 do begin
  105. SWAP.Z2:=PTR[SWAP.Z1];
  106. SWAPCHECK(SWAP);
  107. if SWAP.GAIN > BESTSWAP.GAIN then BESTSWAP:=SWAP;
  108. SWAP.Z1:=SWAP.Z2
  109. end; { for K }
  110. SWAP.Y1:=SWAP.Y2
  111. end; { for J }
  112. SWAP.X1:=SWAP.X2
  113. end; { for I }
  114. if BESTSWAP.GAIN > 0 then
  115. with BESTSWAP do begin
  116. if CHOICE = ASYMMETRIC then begin
  117. REVERSE(Z2,X1);
  118. PTR[Y1]:=X1; PTR[Z2]:=Y2
  119. end
  120. else begin
  121. PTR[X1]:=Y2; PTR[Y1]:=Z2
  122. end;
  123. PTR[Z1]:=X2;
  124. end { with BESTSWAP }
  125. until BESTSWAP.GAIN = 0;
  126. INDEX:=1;
  127. for I:=1 to N do begin
  128. ROUTE[I]:=INDEX; INDEX:=PTR[INDEX]
  129. end
  130. end;
  131.  
  132. PROCEDURE TWOOPT( N:INTEGER; VAR W:ARRNN; VAR ROUTE:ARRN; VAR PATH_WEIGHT:INTEGER);
  133.  
  134. VAR AHEAD,I,I1,I2,INDEX,J,J1,J2,
  135. LAST,LIMIT,MAX,MAX1,NEXT,S1,S2,T1,T2:INTEGER;
  136. PTR :ARRN;
  137. BEGIN
  138. FOR I:=1 TO N-1 DO PTR[ROUTE[I]]:=ROUTE[I+1];
  139. PTR[ROUTE[N]]:=ROUTE[1];
  140. REPEAT { UNTIL MAX = 0 }
  141. MAX:=0; I1:=1;
  142. FOR I:=1 TO N-2 DO
  143. BEGIN
  144. IF I = 1 THEN LIMIT:=N-1
  145. ELSE LIMIT:=N;
  146. I2:=PTR[I1]; J1:=PTR[I2];
  147. FOR J:=I+2 TO LIMIT DO
  148. BEGIN
  149. J2:=PTR[J1];
  150. MAX1:=W[I1,I2]+W[J1,J2]-(W[I1,J1]+W[I2,J2]);
  151. IF MAX1 > MAX THEN
  152. BEGIN { BETTER PAIR HAS BEEN FOUND }
  153. S1:=I1; S2:=I2;
  154. T1:=J1; T2:=J2;
  155. MAX:=MAX1
  156. END;
  157. J1:=J2
  158. END; { FOR J }
  159. I1:=I2
  160. END; { FOR I }
  161. IF MAX > 0 THEN
  162. BEGIN { SWAP PAIR OF EDGES }
  163. PTR[S1]:=T1;
  164. NEXT:=S2; LAST:=T2;
  165. REPEAT
  166. AHEAD:=PTR[NEXT]; PTR[NEXT]:=LAST;
  167. LAST:=NEXT; NEXT:=AHEAD
  168. UNTIL NEXT = T2;
  169. PATH_WEIGHT:=PATH_WEIGHT-MAX
  170. END { IF MAX > 0 }
  171. UNTIL MAX = 0;
  172. INDEX:=1;
  173. FOR I:=1 TO N DO
  174. BEGIN
  175. ROUTE[I]:=INDEX; INDEX:=PTR[INDEX]
  176. END
  177. END;
  178.  
  179. var
  180. W :ARRNN=((0, 0, 0, 3, 3, 6),
  181. (0, 0, 1, 4, 1, 0),
  182. (1, 2, 0, 0, 0, 3),
  183. (4, 5, 0, 0, 0, 3),
  184. (4, 2, 0, 0, 0, 0),
  185. (7, 1, 3, 3, 0, 0)
  186. );
  187.  
  188. PATH_WEIGHT:integer;
  189. ROUTE :ARRN;
  190. i:integer;
  191. begin
  192. PATH_WEIGHT:=0;
  193. for i:=1 to COUNT_POINTS do ROUTE[i]:=i;
  194. FITSP(COUNT_POINTS,1,999999,W,ROUTE,PATH_WEIGHT);
  195. TWOOPT(COUNT_POINTS,W,ROUTE,PATH_WEIGHT);
  196. THREEOPT(COUNT_POINTS,W,ROUTE);
  197. for i:=1 to COUNT_POINTS do write(inttostr(ROUTE[i])+'->');
  198. write(inttostr(1)+' = '+inttostr(PATH_WEIGHT));
  199. end;
При использовании обязательна ссылка на http://DMTSoft.ru
up

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


Пользователь: die_kamille
Сообщений: 1
Статус: Незримый
Зарегистрирован:
12 декабря 2010, 21:51
Был:16 декабря 2010, 22:58
die_kamille
smsup
Дата: 12 декабря 2010, 22:24 Сообщение № 1
простите пожалуйтста, возможно не туда пишу...но помогите реализовать задачу "китайского почтальона"...вотрой месяц с ней сижу(( не знаю что делать(
Пользователь: jhonny_vincent
Сообщений: 2
Статус: Незримый
Зарегистрирован:
17 декабря 2010, 0:06
Был:17 декабря 2010, 0:41
jhonny_vincent
smsup
Дата: 17 декабря 2010, 0:41 Сообщение № 2
пожалуйста скиньте исходники на safatinov@gmail.com