Реферат: Решение задач коммивояжёра, способов её решения

--PAGE_BREAK--Постановка задачи

Коммивояжер должен объездить n
городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано nвершин и матрица {cij}, где cij≥0 – длинна (или цена) дуги (i, j), <img width=«90» height=«27» src=«ref-2_1939202751-303.coolpic» v:shapes="_x0000_i1071">. Под маршрутом коммивояжера zбудем понимать цикл i1, i2,…, in,
i1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами iи jнет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z– множество всех возможных маршрутов. Начальная вершина i1– фиксирована. Требуется найти маршрут zÎZ, такой, что l(z)= minl(z), zÎZ
.

Решение задачи
Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу φ длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество <img width=«24» height=«30» src=«ref-2_1939203054-118.coolpic» v:shapes="_x0000_i1072"> состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество <img width=«24» height=«31» src=«ref-2_1939203172-122.coolpic» v:shapes="_x0000_i1073"> не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств <img width=«26» height=«30» src=«ref-2_1939203294-120.coolpic» v:shapes="_x0000_i1074"> и <img width=«24» height=«31» src=«ref-2_1939203172-122.coolpic» v:shapes="_x0000_i1075"> оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ (<img width=«26» height=«30» src=«ref-2_1939203294-120.coolpic» v:shapes="_x0000_i1076">), φ(Z) ≤ φ (<img width=«24» height=«31» src=«ref-2_1939203172-122.coolpic» v:shapes="_x0000_i1077">).

Сравнивая нижние границы φ(<img width=«26» height=«30» src=«ref-2_1939203294-120.coolpic» v:shapes="_x0000_i1078">) и φ(<img width=«24» height=«31» src=«ref-2_1939203172-122.coolpic» v:shapes="_x0000_i1079">), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

Затем одно из подмножеств <img width=«26» height=«30» src=«ref-2_1939203294-120.coolpic» v:shapes="_x0000_i1080"> или <img width=«24» height=«31» src=«ref-2_1939203172-122.coolpic» v:shapes="_x0000_i1081"> по аналогичному правилу разбивается на два новых <img width=«28» height=«30» src=«ref-2_1939204262-124.coolpic» v:shapes="_x0000_i1082"> и <img width=«26» height=«31» src=«ref-2_1939204386-123.coolpic» v:shapes="_x0000_i1083">. Для них снова отыскиваются нижние границы φ(<img width=«28» height=«30» src=«ref-2_1939204262-124.coolpic» v:shapes="_x0000_i1084">), и φ(<img width=«26» height=«31» src=«ref-2_1939204386-123.coolpic» v:shapes="_x0000_i1085">) и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный маршрут. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего маршрута.

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

Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).

Для того чтобы найти нижнюю границу воспользуемся следующим соображением: если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любогомаршрутом коммивояжера изменится на данную величину.

Вычтем из каждой строки число, равное минимальному элементу этой строки. Вычтем из каждого столбца число, равное минимальному элементу этого столбца. Полученная матрица называется приведенной по строкам и столбцам. Сумма всех вычтенных чисел называется константой приведения.

Константу приведения следует выбирать в качестве нижней границы длины маршрутов.
Разбиение множества маршрутов на подмножества
Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θij нулевых элементов этой матрицы. Степень нулевого элемента Θij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов cij– не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

Для получения платежной матрицы маршрутов, включающей дугу (i, j) вычеркиваем в матрице строку i и столбец j, а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку на бесконечность.

Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента cijна бесконечность.
    продолжение
--PAGE_BREAK--Пример решения задачи коммивояжера методом ветвей и границ


Коммивояжер должен объездить 6городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:





A

B

C

D

E

F

A

∞

26

42

15

29

25

B

7

∞

16

1

30

25

C

20

13

∞

35

5



D

21

16

25

∞

18

18

E

12

46

27

48

∞

5

F

23

5

5

9

5

∞
Решение задачи
Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r1=15, r2=1, r3=0, r4=16, r5=5, r6=5.

После их вычитания по строкам получим:







1

2

3

4

5

6

1

∞

11

27



14

10

2

6

∞

15



29

24

3

20

13

∞

35

5



4

5



9

∞

2

2

5

7

41

22

43

∞



6

18





4



∞



Минимумы по столбцам: h1=5, h2=h3=h4=h5=h6.

После их вычитания по столбцам получим приведенную матрицу:





1

2

3

4

5

6

1

∞

11

27



14

10

2

1

∞

15



29

24

3

15

13

∞

35

5



4





9

∞

2

2

5

2

41

22

43

∞



6

13





4



∞



Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ14 = 10 + 0,
Θ24 = 1 + 0, Θ36 = 5+0, Θ41 = 0 + 1, Θ42 = 0 + 0, Θ56 = 2 + 0, Θ62 = 0 + 0,
Θ63 = 0 + 9, Θ65 = 0 + 2. Наибольшая степень Θ14 = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества <img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1086"> остается равной 47. Для всех маршрутов множества<img width=«27» height=«30» src=«ref-2_1939204877-126.coolpic» v:shapes="_x0000_i1087"> из города Aмы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ(<img width=«27» height=«30» src=«ref-2_1939204877-126.coolpic» v:shapes="_x0000_i1088">) = 47 + 10.

В матрице, соответствующей <img width=«27» height=«30» src=«ref-2_1939204877-126.coolpic» v:shapes="_x0000_i1089"> полагаем c14= ∞.






1

2

3

4

5

6

1

∞

11

27

∞

14

10

2

1

∞

15



29

24

3

15

13

∞

35

5



4





9

∞

2

2

5

2

41

22

43

∞



6

13





4



∞



После проведения процедуры приведения с r1=10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей <img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1090">, вычеркиваем первую строку и четвертый столбец и положим c41= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c1ij}:





1

2

3

5

6

2

1

∞

15

29

24

3

15

13

∞

5



4

∞



9

2

2

5

2

41

22

∞



6

13







∞



Для приведения надо вычесть минимум по первому столбцу: h1=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы
 φ(<img width=«27» height=«30» src=«ref-2_1939204877-126.coolpic» v:shapes="_x0000_i1091">) = 67 и φ(<img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1092">) =48 < 67 выделяем подмножество маршрутов <img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1093">, которое с большей вероятностью содержит маршрут минимальной длины.
<img width=«360» height=«156» src=«ref-2_1939205744-1672.coolpic» v:shapes="_x0000_i1094">

Рис. 1.4 Ветвление на первом шаге


Приведенная платежная матрица для <img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1095">



1

2

3

5

6

2



∞

15

29

24

3

14

13

∞

5



4

∞



9

2

2

5

1

41

22

∞



6

12







∞



Далее продолжаем процесс ветвления. Найдем степени Θij нулевых элементов этой матрицы Θ21 =16, Θ36 = 5, Θ42 = 2, Θ56 = 2, Θ62 = 0, Θ63 =9, Θ65 = 2. Наибольшая степень Θ21. Затем множество <img width=«29» height=«27» src=«ref-2_1939204756-121.coolpic» v:shapes="_x0000_i1096"> разбивается дуге (2, 1) на два новых <img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1097"> и <img width=«27» height=«30» src=«ref-2_1939207783-125.coolpic» v:shapes="_x0000_i1098">.

В матрице для <img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1099"> вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c42= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.





2

3

5

6

3

13

∞

5



4

∞

9

2

2

5

41

22

∞



6







∞



Для приведения надо вычесть минимум по строке 4: r4=2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для<img width=«27» height=«30» src=«ref-2_1939207783-125.coolpic» v:shapes="_x0000_i1100">, полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ(<img width=«27» height=«30» src=«ref-2_1939207783-125.coolpic» v:shapes="_x0000_i1101">) = 64 и φ(<img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1102">) =50< 64 выбираем для дальнейшего разбиения подмножество маршрутов <img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1103">.


<img width=«343» height=«155» src=«ref-2_1939208533-1885.coolpic» v:shapes="_x0000_i1104">

Рис. 1.5 Ветвление на втором шаге
Приведенная платежная матрица для <img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1105">





2

3

5

6

3

13

∞

5



4

∞

7





5

41

22

∞



6







∞



Степени Θij нулевых элементов этой матрицы Θ36 = 5, Θ45 = 0, Θ56 = 22, Θ62 = 13, Θ63 =7, Θ65 = 0. Наибольшая степень Θ56. Затем множество <img width=«29» height=«27» src=«ref-2_1939207658-125.coolpic» v:shapes="_x0000_i1106"> разбивается дуге (2, 1) на два новых <img width=«29» height=«28» src=«ref-2_1939210668-123.coolpic» v:shapes="_x0000_i1107"> и <img width=«29» height=«30» src=«ref-2_1939210791-128.coolpic» v:shapes="_x0000_i1108">.

Нижняя граница для<img width=«29» height=«30» src=«ref-2_1939210791-128.coolpic» v:shapes="_x0000_i1109"> равна 50 + 22 = 72. В матрице для <img width=«29» height=«28» src=«ref-2_1939210668-123.coolpic» v:shapes="_x0000_i1110"> вычеркиваем строку 5 и столбец 6 и полагаем c65= ∞. Получим матрицу:





2

3

5

3

13

∞

5

4

∞

7



6





∞



Для приведения надо вычесть минимум по строке 3: r3=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов <img width=«29» height=«28» src=«ref-2_1939210668-123.coolpic» v:shapes="_x0000_i1111">.




<img width=«492» height=«156» src=«ref-2_1939211293-1975.coolpic» v:shapes="_x0000_i1113">

Рис. 1.6 Ветвление на третьем шаге
Приведенная платежная матрица для <img width=«29» height=«28» src=«ref-2_1939210668-123.coolpic» v:shapes="_x0000_i1114">





2

3

5

3

8

∞



4

∞

7



6





∞



Степени Θij нулевых элементов этой матрицы Θ35 = 8, Θ45 = 7, Θ62 = 8, Θ63 =7. Выбираем Θ35 = 8. Разбиваем <img width=«29» height=«28» src=«ref-2_1939210668-123.coolpic» v:shapes="_x0000_i1115"> на <img width=«29» height=«28» src=«ref-2_1939213514-123.coolpic» v:shapes="_x0000_i1116"> и <img width=«29» height=«30» src=«ref-2_1939213637-128.coolpic» v:shapes="_x0000_i1117">.

Нижняя граница для<img width=«29» height=«30» src=«ref-2_1939213637-128.coolpic» v:shapes="_x0000_i1118"> равна 55 + 8 = 64. В матрице для <img width=«29» height=«28» src=«ref-2_1939213514-123.coolpic» v:shapes="_x0000_i1119"> вычеркиваем строку 3 и столбец 5 и полагаем c63= ∞. Получим





2

3

4

∞

7

6



∞



Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим





2

3

4

∞



6



∞


Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).<img width=«492» height=«158» src=«ref-2_1939214016-1483.coolpic» v:shapes="_x0000_s3367 _x0000_s3368 _x0000_s3369 _x0000_s3370 _x0000_s3371 _x0000_s3372 _x0000_s3373 _x0000_s3374 _x0000_s3375 _x0000_s3376 _x0000_s3377 _x0000_s3378 _x0000_s3379"><img width=«492» height=«156» src=«ref-2_1939215499-73.coolpic» v:shapes="_x0000_i1112">

Рис. 1.7 Ветвление на четвертом шаге
<img width=«590» height=«468» src=«ref-2_1939215572-4946.coolpic» v:shapes="_x0000_s3332 _x0000_s3333 _x0000_s3334 _x0000_s3335 _x0000_s3336 _x0000_s3337 _x0000_s3338 _x0000_s3339 _x0000_s3340 _x0000_s3341 _x0000_s3342 _x0000_s3343 _x0000_s3344 _x0000_s3345 _x0000_s3346 _x0000_s3347 _x0000_s3348 _x0000_s3349 _x0000_s3350 _x0000_s3351 _x0000_s3352 _x0000_s3353 _x0000_s3354 _x0000_s3355 _x0000_s3356 _x0000_s3357 _x0000_s3358 _x0000_s3359 _x0000_s3360 _x0000_s3361 _x0000_s3362 _x0000_s3363 _x0000_s3364 _x0000_s3365 _x0000_s3366"><img width=«590» height=«468» src=«ref-2_1939220518-73.coolpic» v:shapes="_x0000_i1120">

Рис. 1.8 Дерево ветвления с оценками
Полученный маршрутом коммивояжера z= (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).    продолжение
--PAGE_BREAK--