Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из чисел, расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1 < Pi. Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj, j > i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере — 1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.
Нужно понимать, что в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).
Если мы решим, поставленную в примере 1 задачу коммивояжера, методом лексикографического перебора, то получим следующий тур 1-2-6-5-4-3-1 длиной 36.
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве случаев излагается пионерская работа Литтла.
Т.к. желательно усовершенствовать перебор, применив разумную идею, ниже будет описан алгоритм, который реализует простую, но широко применимую и очень полезную идею.
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
Алгоритм метода ветвей и границ предназначен для нахождения минимального гамильтонова контура на графе с N вершинами. В матрице расстояний задачи коммивояжера если между вершинами i и j нет дуги, то ставится символ "бесконечность". Этот же символ ставится по диагонали, что означает запрет на возвращение в вершину, через которую уже проходил контур.
Основная идея метода состоит в том, что вначале строят нижнюю границу длин множества гамильтоновых контуров ω0. Затем множество контуров разбивается на два подмножества таким образом, чтобы первое подмножество ω1ij состояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество ω1not ij не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества гамильтоновых контуров. Полученные нижние границы подмножеств ω1ij и ω1not ij оказываются не меньше нижней границы всего множества гамильтоновых контуров, т.е.
Ф(ω0)<=Ф1ij,
Ф(ω0)<=Ф1not ij
Сравнивая нижние границы Ф1ij и Ф1not ij, можно выделить среди них то, которое с большей вероятностью содержит гамильтонов контур минимальной длины.
Затем одно из подмножеств ω1ij или ω1not ij по аналогичному правилу разбивается на два новых ω2ij и ω2ij. Для них снова отыскиваются нижние границы Ф2ij и Ф2not ij и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный гамильтонов контур. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего гамильтонова контура.
Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины контура. Его называют вторым рекордом. Процесс решения заканчивается, когда будут проанализированы все подмножества.
Для практической реализации метода ветвей и границ применительно к задаче коммивояжера нужно указать прием определения нижних границ подмножеств и разбиения множества гамильтоновых контуров на подмножества (ветвление).
Если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любого гамильтонова контура изменится на данную величину.
Для того, чтобы найти нижнюю границу вычтем из каждой строки число, равное минимальному элементу этой строки, вычтем из каждого столбца число, равное минимальному элементу этого столбца. Полученная матрица называется приведенной по строкам и столбцам. Сумма всех вычтенных чисел называется константой приведения.
Константа приведения может быть выбрана в качестве нижней границы длины гамильтоновых контуров.
Для выделения претендентов на включение в множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени θij нулевых элементов этой матрицы. Степень нулевого элемента cij равна сумме минимальных элементов в строке i и столбце j при блокировании перехода (i,j) бесконечностью. С наибольшей вероятностью искомому гамильтонову контуру принадлежат дуги с максимальной степенью нуля.
Для получения матрицы контуров, включающей дугу (i,j) вычеркиваем в матрице строку i и столбец j, а чтобы не допустить образования не гамильтонова контура заменяем элемент замыкающий текущую цепочку на бесконечность.
Множество контуров, не включающих дугу (i,j) получаем путем замены элемента cij на бесконечность.
| - | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | - | 0 | 0 | 3 | 3 | 6 |
| 2 | 0 | - | 1 | 4 | 1 | 0 |
| 3 | 1 | 2 | - | 0 | 0 | 3 |
| 4 | 4 | 5 | 0 | - | 1 | 3 |
| 5 | 4 | 2 | 0 | 1 | - | 0 |
| 6 | 7 | 1 | 3 | 3 | 0 | - |
| 2 | 1 | 4 | ||||
| табл. 4 | ||||||
| - | 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | - | 2 | 0 | 4 | 3 | 10 | 4 |
| 2 | 0 | - | 1 | 5 | 1 | 4 | 6 |
| 3 | 1 | 4 | - | 1 | 0 | 7 | 3 |
| 4 | 4 | 7 | 0 | - | 1 | 7 | 4 |
| 5 | 4 | 4 | 0 | 2 | - | 4 | 3 |
| 6 | 7 | 3 | 3 | 4 | 0 | - | 7 |
| табл. 3 | |||||||
| - | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | - | 6 | 4 | 8 | 7 | 14 |
| 2 | 6 | - | 7 | 11 | 7 | 10 |
| 3 | 4 | 7 | - | 4 | 3 | 10 |
| 4 | 8 | 11 | 4 | - | 5 | 11 |
| 5 | 7 | 7 | 3 | 5 | - | 7 |
| 6 | 14 | 10 | 10 | 11 | 7 | - |
| табл. 2 | ||||||
Изложим алгоритм Литтла на примере 1 предыдущего раздела…
Повторно запишем матрицу:
Вычитание константы из элементов любой строки или столбца матрицы С, не изменяет минимальный тур.
Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. табл. 3), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам (см. табл.4).
Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.
Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-ый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. В таблице 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.