Определения

называется непустое конечное множество, состоящее из двух подмножеств и . Первое подмножество (вершины) состоит из любого множества элементов. Второе подмножество (дуги) состоит из упорядоченных пар элементов первого подмножества . Если вершины и такие, что , то это вершины смежные.

Маршрутом в графе

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

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

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длинна (или цена) дуги (i , j ),

. Под маршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0 ÎZ , такой, что l (z 0)= minl (z ), z ÎZ .

Решение задачи

Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу φ длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество

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

Сравнивая нижние границы φ (

) и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

Затем одно из подмножеств

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

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

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

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

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

Константу приведения следует выбирать в качестве нижней границы длины маршрутов.

Разбиение множества маршрутов на подмножества

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

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

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

Пример решения задачи коммивояжера методом ветвей и границ

Коммивояжер должен объездить 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	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

Решение задачи

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

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

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

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

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

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Найдем нижнюю границу φ (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).

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

Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.

Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.

Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.

Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.

Исправленный алгоритм, для нахождения действительно минимального маршрута

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

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

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

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

2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w i) и не содержащие эти ребра(S w i /o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множеств S w i /o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h i ,k i), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h i ,k i)
б) При вычислении затрат для множества S w i примем во внимание, что раз ребро (h i i,k i) входит в маршрут, то значит ребро (k i ,h i) в маршрут входить не может, поэтому в матрице затрат пишем c(k i ,h i)=infinity, а так как из пункта h i мы «уже ушли», а в пункт k i мы «уже пришли», то ни одно ребро, выходящее из h i , и ни одно ребро, приходящее в k i , уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h i и столбец k i . После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h i ,k i), где r(h i ,k i) - сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

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

Небольшая оптимизация - подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h i ,k i) или нет, и вешаем двух и более детей - Sw(h i ,k i) и Sw/o(h i ,k i). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Теперь, собственно, об ошибках в той публикации

Причина у этих ошибок одна - игнорирование возможности появления нескольких нулевых элементов с максимальным штрафом. В таком случае надо делить не на два подмножества, а на большее количество (2n). А также следует выбирать для разбиения множество с минимальной границей из всех возможных путей, а не из двух полученных в результате последнего разбиения детей.

Доказательство

Вернемся к картинке в начале поста:

А вот решение с исправленным алгоритмом.

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений.

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

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

1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
2. венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
5. Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
9. Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

	1	2	3	4
1	-	5	8	7
2	5	-	6	15
3	8	6	-	10
4	7	15	10	-

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	20	18	12	8	8
2	5	M	14	7	11	5
3	12	18	M	6	11	6
4	11	17	11	M	12	11
5	5	5	5	5	M	5

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M
d j	0	0	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	12	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	12	M	0(5)	5	5
4	0(0)	6	0(0)	M	1	0
5	0(0)	0(6)	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	12	10	4	0	0
2	0	M	9	2	6	0
3	6	12	M	0	5	0
4	0	6	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	0	M	1	0
d j	0	0	0	0	0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(5)	4
2	0(2)	9	2	M	2
3	6	M	0(7)	5	5
4	0(0)	0(9)	M	1	0
d j	0	9	2	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	M	M	1	0
d j	0	9	0	0	9

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

После операции приведения сокращенная матрица будет иметь вид:

i j	1	4	5	d i
1	M	4	0	0
2	0	2	M	0
3	6	M	5	5
d j	0	2	0	7

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	M	0	0	M

Операция редукции .

i j	1	2	3	4	5
1	M	6	10	4	0
2	0	M	9	2	6
3	6	6	M	0	5
4	0	0	0	M	1
5	0	M	0	0	M

Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	5	d i
1	M	6	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	6	M	0(5)	5	5
4	0(0)	0(6)	0(0)	M	1	0
5	0(0)	M	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	6	10	4	0	0
2	0	M	9	2	6	0
3	6	6	M	0	5	0
4	0	M	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(9)	4
2	0(6)	9	M	6	6
3	6	M	0(5)	5	5
5	0(0)	0(9)	0(0)	M	0
d j	0	9	0	5	0

d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	M	4
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	5	9

Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	d i
2	0	9	M	0
3	6	M	0	0
5	M	0	0	0
d j	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	d i
2	0(15)	9	M	9
3	6	M	0(6)	6
5	M	0(9)	0(0)	0
d j	6	9	0	0

d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i j	1	3	4	d i
2	M	9	M	9
3	6	M	0	0
5	M	0	0	0
d j	6	0	0	15

Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	d i
3	M	0	0
5	0	0	0
d j	0	0	0

Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

																														1
								(5*,2*), H=41																																												(5,2)
(4*,2*), H=47																	(4,2)																															(4*,3*), H=44								(4,3)
								(1*,5*), H=50																	(1,5)
																(2*,1*), H=56																		(2,1)
																												(3,4)												(3*,4*), H=41
																								(5,3)								(5*,3*), H=41

ЭММиМвЛ, ИСО, МПУР

ЗАДАЧА КОММИВОЯЖЕРА

Определения

Графом называется непустое конечное множество, состоящее из двух подмножестви. Первое подмножество
(вершины) состоит из любого множества элементов. Второе подмножество(дуги) состоит из упорядоченных пар элементов первого подмножества
. Если вершины
и
такие, что
, то это вершины смежные.

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

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

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длина (или цена) дуги (i , j ),
. Подмаршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0  Z , такой, что l (z 0)= min l (z ), z  Z .

Решение задачи

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

Сравнивая нижние границы φ () иφ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

Основная идея метода ветвей и границ состоит в том, что ветвятся не все вершины. Сначала вершины просматриваются, и каждая вершина оценивается. Ветвится та вершина, которая получает лучшую оценку.

Каждой вершине соответствует множество вариантов решений. Каждому варианту решения соответствует определенное значение критерия эффективности
. Лучшее из этих значений (минимальное или максимальное) удобно взять в качестве оценки вершины. Однако подсчитать точное значениекритерия, не перебрав всех вариантов, невозможно. Поэтому используется не точное значениекритерия, а его оценка снизу (в случае минимизации) или сверху (в случае максимизации). Оценка снизу – это оценка нижней границы множества вариантов, оценка сверху – это оценка верхней границы множества вариантов.

Оценка вершины должна удовлетворять следующим свойствам.

Алгоритм метода ветвей и границ

Шаг 1 . Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка нижней (верхней) границы. Ветвится вершина, которой соответствует лучшая (минимальная или максимальная) оценка.

Шаг 2 . Для всех вершин -го уровня (
) подсчитывается оценка. Ветвится та из висячих вершин уровня
, которой соответствует лучшая (минимальная или максимальная) оценка.

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

Метод ветвей и границ не гарантирует того, что в ходе решения задачи не будет произведен полный перебор.

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

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

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

Константу приведения следует выбирать в качестве нижней границы длины маршрутов.

Разбиение множества маршрутов на подмножества

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

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

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

Пример (Г.И. Просветов, 2009, стр. 44)

Решим задачу коммивояжера для пяти пунктов.

Расстояния между населенными пунктами заданы с помощью матрицы

,

где - длина пути от пунктаi до пункта j .

На каждом шаге ребро
либо включается в ответ (обозначение
), либо не включается в ответ (обозначение
).

Шаг 1. Нахождение константы приведения .

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

Найденные минимумы в строке и столбце называются константами приведения строки или столбца соответственно. Сумма всех найденных минимумов равна 18 – константа приведения матрицы. Она дает оценку снизу на данном шаге длины маршрута.

Шаг 2 . Определение дуги, исключение которой максимально увеличивает оценку, полученную на предыдущем шаге.

С этой целью заменяем поочередно каждый из нулей на .

Элемент
имеет наибольшую сумму. Поэтому все множество маршрутов распадается на два класса:
(не содержат дугу
) и
(содержат дугу
).

Шаг 3 . Определение множества дуг для дальнейшего ветвления.

Рассмотрим множество
. Исключение дуги

на:

.

В полученной матрице нужно определить сумму констант приведения:

Нижняя граница множества
, где 18 – оценка предыдущего шага, 3 – оценка текущего шага.

Рассмотрим множество
. Включение дуги
проводится с помощью исключения 1-й строки (в множестве
из пункта 1 мы идем только в пункт 3) и 3-го столбца (в множестве
в пункт 3 мы можем попасть только из пункта 1). Элемент (3,1) заменяем на(исключаем возможность возвращения, зацикливания, образования негамильтонова цикла):

.

Нижняя граница множества , где 18 – оценка предыдущего шага, 1 – оценка текущего шага. Числа над матрицей суть номера столбцов, числа перед матрицей – номера строк.

Так как
, то дальше ветвим множество
.

Для матрицы

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

Для элемента
эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса:
(не содержит дугу
) и
(содержит дугу
).

Рассмотрим множество
. Исключение дуги
проводится с помощью замены элемента
на:

.

Определим в полученной матрице ее константу приведения:

.

Решение будем вести с использованием калькулятора . Возьмем в качестве произвольного маршрута:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	90	80	40	100	40
2	60	M	40	50	70	40
3	50	30	M	60	20	20
4	10	70	20	M	50	10
5	20	40	50	20	M	20

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M
d j	0	10	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .

i j	1	2	3	4	5
1	M	40	40	0	60
2	20	M	0	10	30
3	30	0	M	40	0
4	0	50	10	M	40
5	0	10	30	0	M

Сумма констант приведения определяет нижнюю границу H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	40	40	0(40)	60	40
2	20	M	0(20)	10	30	10
3	30	0(10)	M	40	0(30)	0
4	0(10)	50	10	M	40	10
5	0(0)	10	30	0(0)	M	0
d j	0	10	10	0	30	0

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d 14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	40	40	M	60	40
2	20	M	0	10	30	0
3	30	0	M	40	0	0
4	0	50	10	M	40	0
5	0	10	30	0	M	0
d j	0	0	0	0	0	40

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d 41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

∑d i + ∑d j = 10

i j	1	2	3	5	d i
2	20	M	0	30	0
3	30	0	M	0	0
4	M	50	10	40	10
5	0	10	30	M	0
d j	0	0	0	0	10

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	5	d i
2	20	M	0(20)	30	20
3	30	0(10)	M	0(30)	0
4	M	40	0(30)	30	30
5	0(30)	10	30	M	10
d j	20	10	0	30	0

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d 35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i j	1	2	3	5	d i
2	20	M	0	30	0
3	30	0	M	M	0
4	M	40	0	30	0
5	0	10	30	M	0
d j	0	0	0	30	30

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d 53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 10
После операции приведения сокращенная матрица будет иметь вид:

i j	1	2	3	d i
2	20	M	0	0
4	M	40	0	0
5	0	10	M	0
d j	0	10	0	10

Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	d i
2	20	M	0(20)	20
4	M	30	0(30)	30
5	0(20)	0(30)	M	0
d j	20	30	0	0

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	d i
2	20	M	0	0
4	M	30	0	0
5	0	M	M	0
d j	0	30	0	30

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 20
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	d i
2	20	0	0
4	M	0	0
d j	20	0	20

Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180