Определения
называется непустое конечное множество, состоящее из двух подмножеств и . Первое подмножество
(вершины) состоит из любого множества элементов. Второе подмножество (дуги) состоит из упорядоченных пар элементов первого подмножества 
. Если вершины и такие, что , то это вершины смежные.
Маршрутом в графе
называется последовательность вершин не обязательно попарно различных, где для любого
смежно с . Маршрут называется цепью, если все его ребра попарно различны. Если то маршрут называется замкнутым. Замкнутая цепь называется циклом.
Коммивояжер должен объездить 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).
При рассмотрении целого ряда задач, необходимо учитывать требование целочисленности используемых переменных. Методы решения задач линейного программирования не гарантируют целочисленности решения.
Иногда задачи целочисленного линейного программирования решают приближенно. Для этого решают задачу без учета целочисленности переменных, затем в полученном оптимальном решении округляют результаты до ближайших целых значений. Использование таких решений допустимо в тех ситуациях, где значения переменных достаточно велики, и погрешностью округления можно пренебречь. Если значения переменных невелики, то округление может привести к значительному расхождению с оптимальным решением.
Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, впервые, он был предложен Ленд и Дойг в 1960 г.
ветвь граница линейное программирование
Алгоритм метода ветвей и границ предусматривает декомпозицию исходной задачи линейного программирования (ЗЛП) на последовательность задач, содержащих дополнительные ограничения на переменные, которые затем оптимизируются.
1. Процесс начинают с решения задачи симплексным или графическим методом без учета требования на целочисленность переменных. Эту задачу называют ЗЛП-0. Если все переменные оптимального плана целые, то этот план также является оптимальными для задач целочисленного программирования.
2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа. Вторая образуется путем добавления к задаче ЗЛП-0 ограничения. Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:
по возрастанию или убыванию индексов;
переменная представляет важное решение принимаемое в рамках данной задачи;
коэффициент в целевой функции при этой переменной существенно превосходит все остальные.
3. Задачи ЗЛП-1 и ЗЛП-2 решаются самостоятельно. Ветвь оканчивается, если область допустимых решений пуста, либо её оптимальное решение полностью целочисленное. В противном случае возникает необходимость ветвления с п.2, обозначая следующие номера задач ЗЛП в естественном порядке ЗЛП-3, ЗЛП-4.
Процесс решения можно представить в виде дерева, в котором вершина ЗЛП-0 отвечает начальному плану решения задачи, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи.
Рассмотрим следующий пример. Максимизировать целевую функцию
при ограничениях
Воспользуемся графическим методом решения задачи линейного программирования.
1. Решим исходную задачу без учета требования целочисленности переменных.
Обозначим эту задачу линейного программирования ЗЛП-0.
На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.
Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений. Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.
Рисунок 1.1 Решение задачи ЗЛП-0
2. Решим задачу ЗЛП-1 графически.
На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке. Решение задачи нецелочисленное.
Рисунок 1.2 Решение задачи ЗЛП-1
3. Решим задачу ЗЛП-2 графически.
В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.
Рисунок 1.3 Решение задачи ЗЛП-2
Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и. В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.
5x 1 + 2x 2 ≤ 14
2x 1 + 5x 2 ≤ 16
x 1 , x 2 – целые числа
Z = 3x 1 + 5x 2 → max
Решение находим с помощью калькулятора .:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 3x 1 +5x 2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 3x 1 +5x 2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const
(1)
и (2)
5x 1 +2x 2 ≤14
2x 1 +5x 2 ≤16
Решив систему уравнений, получим: x 1 = 1.8095, x 2 = 2.4762
F(X) = 3*1.8095 + 5*2.4762 = 17.8095
Оптимальное значение переменной x 1 =1.81 оказалось нецелочисленным.
В первой из них к условиям задачи 11 добавляется условие х 1 ≥ 2, а к задаче 12 - условие х 1 ≤ 1.
Эта процедура называется ветвлением
по переменной х 1 .
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≥2 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16
Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом
или просто рекордом, а оптимальное значение целочисленной задачи - текущим значением рекорда
. Это значение является нижней границей оптимального значения исходной задачи Z*.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Решив систему уравнений, получим: x 1 = 1, x 2 = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17
Оптимальное значение переменной x 2 =2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х 2 ≥ 3, а к задаче 122 - условие х 2 ≤ 2.
Решим графически задачу 121 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≥3 | (4) |
x 1 ≥0 | (5) |
x 2 ≥0 | (6) |
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5
Решим графически задачу 122 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≤2 | (4) |
x 1 ≥0 | (5) |
x 2 ≥0 | (6) |
Решив систему уравнений, получим: x 1 = 1, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2 = 13
Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины
Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х 1 ≥ 1, а к задаче 1212 - условие х 1 = 0.
Решим графически задачу 1211 как задачу ЛП.
Задача не имеет допустимых решений. ОДР представляет собой пустое множество.
Задача 1211 не имеет решения, поэтому для нее процесс ветвления прерываем.
Решим графически задачу 1212 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 1 ≤1 | (3) |
x 2 ≥3 | (4) |
x 1 =0 | (5) |
x 1 ≥0 | (6) |
x 2 ≥0 | (7) |
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16
Оптимальное значение переменной x 2 =2.48 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х 2 ≥ 3, а к задаче 12 - условие х 2 ≤ 2.
Эта процедура называется ветвлением
по переменной х 2 .
Решим графически задачу 11 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 2 ≥3 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Решив систему уравнений, получим: x 1 = 0.5, x 2 = 3
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5
Решим графически задачу 12 как задачу ЛП.
5x 1 +2x 2 ≤14 | (1) |
2x 1 +5x 2 ≤16 | (2) |
x 2 ≤2 | (3) |
x 1 ≥0 | (4) |
x 2 ≥0 | (5) |
Решив систему уравнений, получим: x 1 = 2, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16
Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x 1 =0.5 оказалось нецелочисленным.
Разбиваем задачу 11 на две подзадачи 111 и 112.
В первой из них к условиям задачи 111 добавляется условие х 1 ≥ 1, а к задаче 112 - условие х 1 = 0.
Решим графически задачу 111 как задачу ЛП.
Прямая F(x) = const
пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2)
и (6)
, то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 1 =0
Решив систему уравнений, получим: x 1 = 0, x 2 = 3.2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16
Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
F(X) = 16
x 1 = 2
x 2 = 2
Дерево решения задачи
Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию , предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:
Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.
Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.
Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.
Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.
Исправленный алгоритм, для нахождения действительно минимального маршрута
А) Ищем все нулевые элементы в приведенной матрице
б) Для каждого из них считаем его штраф за неиспользование.
в) Выбираем элемент, которому соответствует максимальный штраф (любой, если их несколько)
2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w) и не содержащие это ребро(S w/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества S w/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества S w примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h,k), где r(h,k) - сумма констант приведения для измененной матрицы затрат.
4. Из всех
неразбитых множеств выбирается то, которое имеет наименьшую оценку.
Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.
Небольшая оптимизация - подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей - Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
Вернемся к картинке в начале поста:
Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать
График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:
График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.
Попробовать с подробным решением можно
Коммивояжер (бродячий торговец) желает посетить ряд городов и вернуться в исходный город, минимизируя суммарную длину (стоимость) переездов. Эта задача в математической форме формулируется как задача нахождения во взвешенном графе гамильтонова цикла минимальной длины и называется задачей коммивояжера.
В качестве её практического приложения можно указать следующее. Пусть имеется станок, способный выполнять несколько операций. Его перенастройка с одной операции на другую требует определенных затрат. Требуется использовать станок в циклическом режиме, минимизируя суммарные затраты на перенастройку.
В данной задаче перенастройка с одной операции на другую и обратная перенастройка могут требовать, вообще говоря, различных затрат. Поэтому и в общем случае в задаче коммивояжера рассматривается взвешенный ориентированный граф, дуги которого в прямом и обратном направлении могут иметь различные веса.
Для решения задачи коммивояжера можно попытаться использовать «жадный алгоритм», успешно примененный в задаче о минимальном остовном дереве. Упорядочим предварительно дуги по весам и будем включать дуги минимального веса, следя за тем, чтобы не возникли вершины, полустепень исхода или захода которых превышает единицу, и не появились негамильтоновы циклы. Однако, как легко убедиться, данный подход не гарантирует получение оптимального решения. В качестве простейшего контрпримера можно рассмотреть следующий граф.
Здесь каждому ребру соответствует две дуги такого же веса.
«Жадный
алгоритм» прежде всего включит в цикл
ребро
,
как имеющее минимальный вес. Включение
этого ребра, как непосредственно легко
проверить, необходимо ведет к гамильтонову
циклу
веса 29. Оптимальный
же
гамильтонов цикл
имеет вес 12. Поэтому «жадный алгоритм»
не гарантирует получения оптимального
решения, хотя он может быть использован
на практике в качестве полезной эвристики,
во многих случаях приводящей к решениям,
близким к оптимальным.
Для задачи коммивояжера не известно какого – либо эффективного алгоритма. Весьма вероятно, что такого алгоритма не существует, хотя это и не удалось до сих пор доказать. Подобные задачи не редки в дискретной математике. В случае небольшой размерности их точные решения удается получать на компьютере с помощью метода «ветвей и границ».
Под методом «ветвей и границ» понимается широкий класс методов сокращенного перебора, суть которых сводится к следующему. Множество допустимых решений А разбивается на два подмножества А 0 и А 1 , затем каждое из подмножеств также разбивается на два подмножества и т.д. Схематически это можно представить в виде дерева, начинающегося с множества всех решений и заканчивающегося его одноэлементными подмножествами, т.е. допустимыми решениями, которыми в нашем случае являются гамильтоновы циклы.
Среди допустимых решений выбирается оптимальное по функционалу качества, которым в нашем случае является длина гамильтонова цикла. Смысл метода «ветвей и границ» состоит, однако, в том, чтобы не просматривать все допустимые решения, а отсекать большинство ветвей на возможно более раннем этапе. Для этого с помощью эвристических соображений стараются сразу пойти по ветви, ведущей к решению, близкому по качеству к оптимальному. После этого большинство других ветвей отсекают с помощью границ для функционала качества, когда удается показать, что в подмножестве решений не содержится решения, лучшего по качеству, чем уже имеющееся.
Рассмотрим метод «ветвей и границ» на примере задачи коммивояжера. Пусть взвешенный орграф задан матрицей расстояний. Если некоторая дуга в графе отсутствует, то соответствующий элемент матрицы будем полагать равным ∞. Заметим, что если длины всех дуг, входящих в некоторую вершину, уменьшить на одно и то же число, то и длина оптимального гамильтонова цикла уменьшится на это же число. То же самое относится и к множеству выходящих дуг. Будем последовательно вычитать из строк и столбцов матрицы расстояний положительные числа так, чтобы элементы матрицы оставались неотрицательными. Так как длина оптимального гамильтонова цикла для графа с неотрицательной матрицей расстояний также неотрицательна, то сумма вычтенных количеств будет нижней границей для длины оптимального цикла исходного графа.
Рассмотрим пример. Пусть задан граф G с симметрической матрицей расстояний.
Значки « ∞ » на диагонали соответствуют отсутствию в графе петель – дуг, ведущих из вершины в эту же вершину. Получим, прежде всего, нижнюю границу для длины кратчайшего гамильтонового цикла. Из первой, второй, третьей и четвертой строк можно вычесть по единице, из пятой строки – два, а из пятого столбца можно вычесть ещё единицу. Это дает нижнюю границу 7, а матрица расстояний приобретает вид
Теперь выберем дугу для ветвления, т.е. разобьем множество гамильтоновых циклов на два подмножества: включающих и не включающих эту дугу. Мы рассчитываем, что данная дуга будет входить в оптимальный или близкий к оптимальному цикл. Для этого будем следовать следующему эвристическому правилу: из множества дуг нулевой длины выбирать ту, исключение которой ведет к максимальному росту нижней оценки. В нашем случае такой дугой является дуга (1,2). Запрещение этой дуги приводит к матрице
из первой строки и второго столбца которой можно вычесть по единице, что увеличивает нижнюю границу на 2 и делает её равной 9.
Включение же дуги (1,2) приводит к тому, что исключаются все остальные дуги, ведущие в вершину 2, и все остальные дуги, выходящие из вершины 1. Поэтому первую строку и второй столбец матрицы можно далее не рассматривать, и они вычеркиваются из матрицы. Кроме того, исключается дуга (2,1). Матрица принимает вид
Из её первой строки и первого столбца можно вычесть по единице, что приводит к матрице
Нижняя оценка здесь возрастает на 2 и также становится равной 9.
Нижняя оценка длины оптимального цикла остается неизменной.
Дуга (2,5) должна быть запрещена, как ведущая к появлению негамильтонова цикла, и матрица принимает вид
Нижняя оценка длины гамильтонова цикла остается, по – прежнему, равной 9.
Схематически представим проведенный анализ в виде дерева, где в кружочках стоят нижние оценки длины гамильтонова цикла.
Взглянув на это дерево, непосредственно убеждаемся, что полученный гамильтонов цикл является кратчайшим, т.к. движение по любой другой ветви дерева не может привести к более короткому циклу.
Существует ли эффективный алгоритм для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.
Является ли описанный метод « ветвей и границ» эффективным алгоритмом для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.
