Целочисленное линейное программирование метод ветвей и границ. Метод ветвей и границ целочисленного программирования. Основные понятия. Решение задачи коммивояжера онлайн
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода для элементов разбиения выполняется проверка для выяснения, содержит данное подмножество оптимальное решение или нет. Для этого вычисляется нижняя оценка целевой функции на данном подмножестве.
Если оценка снизу не меньше рекорда (наилучшего из найденных решений), то подмножество может больше не рассматриваться. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. Если удается отбросить все элементы разбиения, то рекорд - оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д. Вычисление нижней границы является важнейшим элементом данной схемы.
Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.
Рассмотрим реализацию метода ветвей и границ для задачи коммивояжёра и задачи о рюкзаке.
Рассмотрим алгоритм Литтла (методом ветвей и границ) для задачи коммивояжера. Идею можно сформулировать следующим образом. В каждой строке матрицы расстояний находится минимальный элемент и вычитается из всех элементов соответствующей строки. Получается матрица, приведенная по строкам. Аналогично приводится матрица по столбцам. Получается матрица, приведенная по строкам и столбцам. Суммируя при приведении минимальные элементы, получим константу приведения, которая будет нижней границей множества всех допустимых гамильтоновых контуров. После находятся степени нулей для приведенной матрицы (сумма минимальных элементов строки и столбца, соответствующих этому нулю) и выбирается дуга , для которой степень нулевого элемента достигает максимального значения. Множество всех гамильтоновых контуров разбивается на два подмножества, одно из которых содержит дугу , второе эту дугу не содержит. После этого приводятся полученные матрицы гамильтоновых контуров и сравниваются нижние границы подмножества гамильтоновых контуров с целью выбора для дальнейшего разбиения множества с меньшей нижней границей. Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. Сравнивая длину гамильтонова контура с нижними границами оборванных ветвей, выбирается для дальнейшего ветвления подмножество с нижней границей, меньшей полученного контура, до тех пор, пока не получен маршрут с наименьшей длиной или не становится ясно, что такого маршрута не существует.
Пример.
Пусть в задаче коммивояжера задана следующая матрица стоимостей переездов
Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами
.
Если в матрице , приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам. Для этого в каждом столбце матрицы выбираем минимальный элемент , и вычитаем его из всех элементов соответствующего столбца. Получим матрицу
,
каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.
Суммируя элементы и , получим константу приведения:
.
Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:
.
Выбираем дугу , для которой степень нулевого элемента достигает максимального значения
Разбиваем множество всех допустимых маршрутов на два подмножества:
– подмножество, содержащее дугу ;
– подмножество, не содержащее дугу
Для вычисления оценки затрат для маршрутов, включающих дугу , вычеркиваем в матрице строку и столбец и заменяем симметричный элемент на знак . Приводим полученную матрицу и вычисляем сумму констант приведения .
Рассмотрим задачу дискретного программирования в общем виде:
Найти -вектор неизвестных, D- конечное
множество допустимых значений этого вектора, F(x)- заданная целевая функция.
Идея метода состоит в разбиении D на непересекающиеся подмножества Di (эта процедура называется ветвлением) и вычислении верхней и нижней границ целевой функции на каждом из подмножеств. Нижнюю границу будем обозначать Н, а верхнюю Е. Соответственно Hi Eo, то это подмножество не содержит точку оптимума и может быть исключено из дальнейшего рассмотрения. Если верхняя граница Ei H заменяем Н на min Hi. Если Е=Н, то задача решена, иначе надо продолжить процедуру ветвления и вычисления верхней и нижней границ. При этом разбиению на очередном шаге могут подвергаться все или только некоторые подмножества до достижения равенства верхней и нижней границ, причём не на отдельном подмножестве, а для допустимой области в целом.
Простая идея метода ветвей и границ требует дополнительных вычислений для определения границ. Как правило, это приводит к решению вспомогательной оптимизационной задачи. Если эти дополнительные вычисления требуют большого числа операций, то эффективность метода может быть невелика.
Схему динамического программирования при движении от начальной точке к конечной (рис. 5.1) можно представлять как процедуру ветвления.
Множество всех допустимых траекторий (последовательность по-шаговых переходов) - это исходное множество D, на котором мы должны найти нижнюю и верхнюю границы, а также траекторию, на которой целевая функция достигает верхней границы и объявить рекордом соответствующее ей значение целевой функции. Построение множества состояний, получаемых после первого шага, - это первое ветвление.
Рис. 5.1.
Теперь подмножествами Di являются множества траекторий, каждая из которых проходит через соответствующую i-ую точку.
На последующих шагах после отбраковки всех путей, приводящих в любое (i-oe) состояние, кроме одного, соответствующим подмножеством является этот оставшийся путь со всеми его допустимыми продолжениями (рис. 5.1). Для каждого из таких подмножеств надо как-то найти верхнюю и нижнюю границы. Если нижняя граница превышает текущее значение рекорда, соответствующее состояние и все его продолжения отбраковываются. Если верхняя граница достигается на некоторой траектории и она меньше текущего значения рекорда, то получаем новый рекорд.
Эффективность такого подхода зависит от точности получаемых оценок, т.е. от Ei - Hi, и от затрат времени на их вычисление.
Фактически в упрощённом виде мы уже использовали этот метод при решении задачи о защите поверхности (разд. 4.6), когда отбраковывали состояния, для которых текущие затраты превышали суммарные затраты для начального приближения. В этом случае текущие затраты являются нижней границей, если считать нулевыми затраты на весь оставшийся путь, а суммарные затраты, соответствующие начальному приближению, являются рекордом. При таком подходе рекорд не обновлялся, хотя это можно было сделать построением начального приближения (верхней границы) для оставшегося пути подобно тому как это делалось для всей траектории при построении начального приближения. Получаемая без вычислений нижняя граница соответствует нулевым затратам на весь оставшийся путь и является крайне грубой оценкой, но получаемой «бесплатно», т.е. без вычислений.
Покажем как получать и использовать более точные оценки при решении рассмотренных выше и целого ряда других задач. При этом будем стремиться получать авозможно более точные границы при минимуме вычислений.
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.
Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ .
Общий план решения задачи коммивояжера
Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):
- Построение матрицы с исходными данными.
- Нахождение минимума по строкам.
- Редукция строк.
- Нахождение минимума по столбцам.
- Редукция столбцов.
- Вычисление оценок нулевых клеток.
- Редукция матрицы.
- Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
- Вычисление итоговой длины пути и построение маршрута.
Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.
Подробная методика решения задачи коммивояжера
В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».
Итак, методика решения задачи коммивояжера:
1. Построение матрицы с исходными данными
Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:
В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).
Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.
2. Нахождение минимума по строкам
Находим минимальное значение в каждой строке (di ) и выписываем его в отдельный столбец.
3. Редукция строк
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
В итоге в каждой строке будет хотя бы одна нулевая клетка .
4. Нахождение минимума по столбцам
5. Редукция столбцов
Вычитаем из каждого элемента матрицы соответствующее ему dj.
В итоге в каждом столбце будет хотя бы одна нулевая клетка .
6. Вычисление оценок нулевых клеток
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку ». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
И так по всем нулевым клеткам:
7. Редукция матрицы
Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).
Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути , ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9
Если мы еще не нашли все отрезки пути, то возвращаемся ко 2 -му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.
Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .
9. Вычисление итоговой длины пути и построение маршрута
Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.
В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .
Общая длина пути: L = 30 .
Практическое применение задачи коммивояжера
Применение задачи коммивояжера на практике довольно обширно. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.
Решение задачи коммивояжера онлайн
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
Определения
называется непустое конечное множество, состоящее из двух подмножеств и . Первое подмножество
(вершины) состоит из любого множества элементов. Второе подмножество (дуги) состоит из упорядоченных пар элементов первого подмножества 
. Если вершины и такие, что , то это вершины смежные.
Маршрутом в графе
называется последовательность вершин не обязательно попарно различных, где для любого
смежно с . Маршрут называется цепью, если все его ребра попарно различны. Если то маршрут называется замкнутым. Замкнутая цепь называется циклом.
Постановка задачи
Коммивояжер должен объездить 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).
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
