Венгерский метод решения задачи о назначениях
Алгоритм нахождения оптимального назначения максимальной стоимости
1 шаг. В каждом столбце выбрать максимальный элемент.
2 шаг. Пересчитать все элементы каждого столбца по правилу: новое значение элемента столбца = максимальный элемент столбца – старое значение элемента столбца.
3 шаг. Если в каждой строке и в каждом столбце имеется нуль, то переходим к шагу 5.
4 шаг. В каждой строке выбрать минимальный элемент и из каждого элемента строки вычесть соответствующие минимальное значение.
5 шаг. В полученной матрице найти строку или столбец с одним нулем.
6 шаг. Строку и столбец, находящиеся на пересечении выбранного нулевого элемента из дальнейшего рассмотрения исключить. Данный нулевой элемент выделить.
7 шаг. В оставшейся матрице найти строку или столбец с одним нулевым значением. Данный нулевой элемент выделить. Строку и столбец, на пересечении которых находится найденный нулевой элемент, вычеркнуть из дальнейшего рассмотрения.
8 шаг. Процесс повторять до тех пор, пока все работы не будут распределены между работниками (при этом выбираются только нулевые назначения).
9 шаг. Если распределить работы не удается, то после шага 4 в полученной матрице минимальным количеством вертикальных и горизонтальных прямых вычеркиваются все нули матрицы.
10 шаг. В оставшейся матрице найти минимальный элемент.
11 шаг. К элементам, лежащим на пересечении вертикальных и горизонтальных прямых, найденный минимальный элемент прибавить.
12 шаг. Из всех невычеркнутых элементов матрицы найденный минимальный элемент вычитается.
13 шаг. Повторить шаги 5–8.
Алгоритм определения назначения минимальной стоимости отличается от описанного двумя первыми шагами. На первом шаге в каждом столбце выбирается минимальный элемент, который вычитается из всех элементов столбца (шаг 2).
Задача 1
На автомойку приехали три машины: Ауди, Пежо и ВАЗ. На автомойке есть три поста, на каждом из которых можно обслужить любую из этих трех машин, но за различную плату (см. таблицу).
Стоимость мойки автомобиля
| Ауди | Пежо | ВАЗ | |
| Пост 1 | |||
| Пост 2 | |||
| Пост 3 |
Распределить машины между постами с максимальным доходом для автосервиса.
Решение
Определим максимальный элемент в каждом столбце.
| Ауди | Пежо | ВАЗ | |
| Пост 1 | |||
| Пост 2 | |||
| Пост 3 | |||
| Максимум по столбцу |
Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.
| Ауди | Пежо | ВАЗ | Минимум по строками | |
| Пост 1 | ||||
| Пост 2 | ||||
| Пост 3 |
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
| Ауди | Пежо | ВАЗ | |
| Пост 1 | |||
| Пост 2 | |||
| Пост 3 |
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это вторая строка и второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.
| Ауди |  Пежо | ВАЗ | |
| Пост 1 | |||
 Пост 2 | |||
| Пост 3 |
В оставшейся матрице в каждой строке и в каждом столбце остались только нулевые значения. Это означает, что данная задача имеет два варианта решения.
1 вариант.
| Ауди | Пежо | ВАЗ | |
| Пост 1 | |||
| Пост 2 | |||
| Пост 3 |
Выделенные нули определяют оптимальное решение: на посту 1 моются машины Ауди, на втором посту– Пежо, на третьем – ВАЗ.
Суммарный доход 3 + 7 + 8 = 18 у.е.
2 вариант.
| Ауди | Пежо | ВАЗ | |
| Пост 1 | |||
| Пост 2 | |||
| Пост 3 |
Выделенные нули определяют оптимальное решение: на посту 1 моются машины ВАЗ, на втором посту– Пежо, на третьем – Ауди.
Суммарный доход 6 + 7 + 5 = 18 у.е.
Задача 2
Время опоздания трех сотрудников на работу (в минутах) в зависимости от коллективов представлено в таблице. Распределить работников в коллективы таким образом, чтобы суммарное время опозданий было минимальным.
| Сотрудник 1 | Сотрудник 2 | Сотрудник 3 | |
| Коллектив 1 | |||
| Коллектив 2 | |||
| Коллектив 3 |
Решение
Определим минимальный элемент в каждом столбце.
| Сотрудник 1 | Сотрудник 2 | Сотрудник 3 | |
| Коллектив 1 | |||
| Коллектив 2 | |||
| Коллектив 3 | |||
| Минимум по столбцу |
Вычтем из элементов столбца минимальный элемент столбца. Определим минимальные элементы по строкам.
| Сотрудник 1 | Сотрудник 2 | Сотрудник 3 | Минимум по строкам | |
| Коллектив 1 | ||||
| Коллектив 2 | ||||
| Коллектив 3 |
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
| Сотрудник 1 | Сотрудник 2 | Сотрудник 3 | |
| Коллектив 1 | |||
| Коллектив 2 | |||
| Коллектив 3 |
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это первая, третья строка и первый, второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.
| Сотрудник 1 |  Сотрудник 2 | Сотрудник 3 | |
| Коллектив 1 | |||
 Коллектив 2 | |||
| Коллектив 3 |
В оставшейся матрице в каждой строке имеется по одному нулю, расположенные в первом и третьем столбце. Таким образом, данная задача имеет один вариант решения.
| Сотрудник 1 | Сотрудник 2 | Сотрудник 3 | |
| Коллектив 1 | |||
| Коллектив 2 | |||
| Коллектив 3 |
Выделенные нули определяют оптимальное решение: в первом коллективе должен работать первый сотрудник, во втором – второй, в третьем коллективе третий сотрудник.
Суммарное время опоздания: 4 + 2 + 3 = 9 минут.
Задача 3
Производительность (тыс. шт.) работников предприятия на соответствующих работах представлена в виде матрицы.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
| Работник 4 |
Распределить работы среди претендентов с максимальной суммарной производительностью для предприятия.
Решение
Определим максимальный элемент в каждом столбце.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
| Работник 4 | ||||
| Максимум по столбцу |
Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | Минимум по строке | |
| Работник 1 | |||||
| Работник 2 | |||||
| Работник 3 | |||||
| Работник 4 |
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
| Работник 4 |
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это третья строка и второй и четвертый столбцы. Выберем элемент (4,4) и вычеркнем четвертую строку и четвертый столбец. Элемент (4,4) выделим.
| Работа 1 | Работа 2 | Работа 3 |  Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
 Работник 4 |
В оставшейся матрице во втором столбце все элементы ненулевые, а, следовательно, в данной матрице нельзя распределить работы между претендентами. Преобразуем таблицу 3, вычеркнув все нули минимальным количеством вертикальных и горизонтальных прямых.
 Работа 1 | Работа 2 |  Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
 Работник 4 |
В оставшейся матрице минимальное значение равно единице. К элементам, лежащим, на пересечении вертикальных и горизонтальных прямых, прибавим минимальное значение, а из невычеркнутых вычтем.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
| Работник 4 |
В полученной матрице третья строка и четвертый столбец содержат один нуль. Выберем элемент (4,4) и вычеркнем четвертую строку и четвертый столбец. Элемент (4,4) выделим.
| Работа 1 | Работа 2 | Работа 3 |  Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
 Работник 4 |
В оставшейся матрице в третьей строке и втором столбце имеется один нуль. Выберем ячейку (3,3) и вычеркнем третью строку и третий столбец. Элемент (3,3) выделим.
| Работа 1 | Работа 2 |  Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
 Работник 3 | ||||
| Работник 4 |
В полученной матрице первая строка имеет два нулевых значения, вторая только один, поэтому данная задача имеет только одно решение.
| Работа 1 | Работа 2 | Работа 3 | Работа 4 | |
| Работник 1 | ||||
| Работник 2 | ||||
| Работник 3 | ||||
| Работник 4 |
Выделенные нули определяют оптимальное решение: первого работника необходимо назначить на вторую работу, второго – на первую, третьего – на третью, четвертого – на четвертую работу.
Суммарная производительность: 4 + 6 + 7 + 5 = 22 тыс. шт.
Задача коммивояжера
Задача коммивояжера решается в случае, когда необходимо посетить n городов по одному разу и вернуться в исходный город. Расстояние между любыми двумя городами i и j известно и равно ci,j (¥, если между городами нет дороги). Цель задачи – найти кратчайший маршрут (гамильтонов контур минимальной длины).
Для точного решения задачи коммивояжера необходимо исследовать все возможные маршруты (все гамильтоновы контуры). Для задачи с n городами общее число гамильтоновых контуров равно (n – 1)! При большом n это число довольно велико, поэтому часто приходится ограничиваться поиском приближенно оптимальных решений.
В настоящее время существует значительное число приближенных методов решения задачи коммивояжера. Одним из наиболее простых является метод ближайшего соседа (ближайшего непосещенного города). Данный метод целесообразно применять при количестве городов более 40. Качество решения зависит от выбора начальной вершины, поэтому замкнутые контуры необходимо строить для каждой вершин, рассматриваемой как начальной. Одним из наиболее распространенных методов решения задачи коммивояжера является метод ветвей и границ.
Метод ближайшего соседа
Алгоритм решения включает следующие шаги.
1 шаг. Выбрать первую вершину.
2 шаг. Для выбранной вершины найти наиболее близкую к ней. Если данная вершина уже вошла в маршрут, то она блокируется, и выбирается следующая по степени близости.
3 шаг. Повторять шаг 2 до тех пор, пока маршрут (путь) не пройдет через все вершины.
4 шаг. Выбрать вторую вершину и повторить шаги 2–3.
5 шаг. Процесс считается законченным, когда гамильтоновы контуры построены для всех вершин, выбранных в качестве начальных.
6 шаг. Рассчитать длину каждого из полученных маршрутов и выбрать минимальное значение.
Задача
Решить задачу коммивояжера со следующей матрицей расстояний.
Символ ¥ на главной диагонали означает фактический запрет на переход вида i ® i (из города в него же).
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
Решение
Решение задачи начнем с рассмотрения первой вершины в качестве начальной. Наиболее близкой к ней вершиной является четвертая. Расстояние между первым и четвертым городом 8 км. Наиболее близкой к четвертой вершине является пятая и шестая. Так как данные вершины еще не входили в маршрут, то далее следует рассматривать два варианта.
10 5
8
1 4
10 6
Для пятой вершины наиболее близкой является первая, которая уже вошла в маршрут. Поэтому выбираем следующую по близости вершину – третью. Для шестой вершины ближайшим соседом является вторая, которую и выбираем для проходящего через нее пути.
1 7
9
10 5 3
1 4
10 6 2
Ближайшей к третьей вершине является шестая (первая, четвертая и пятая вошли в путь). Ко второй – третья (четвертая и шестая вошли в маршрут).
1 4 5
1 13
9 13 4 15
10 5 3 6
1 4
3 7
10 6 2 3
5 3
4 6
Следующей по степени близости к шестой вершине является вторая; к третьей – пятая. Данные вершины были последними в цепи городов, которые необходимо посетить, поэтому для создания замкнутого маршрута вернемся в первый город.
1 4 5
1 13 13 4
9 15 3 21
10 5 3 6 2 1
1 4
3 7 4 7
10 6 2 3 5 1
4 6
Суммарное расстояние для пути:
1 – 4 – 5 – 3 – 6 – 2 – 1 Z = 8 + 10 + 9 + 15 + 3 + 21 = 64 км.
1 – 4 – 6 – 2 – 3 – 5 – 1 Z = 8 + 10 + 3 + 7 + 4 + 7 = 39 км.
Для других вершин замкнутые контуры построены на рисунках.
2 6 2 4 5 6
а)
3 10 10 8 9 11
3 8 10 7 12 19
2 6 4 5 1 3 2
Суммарное расстояние:
2 – 6 – 4 – 5 – 1 – 3 – 2 Z = 3 + 8 + 10 + 7 + 12 + 19 = 59 км.
б) 5 4 6
10 5 3
4 7 8 10 3 7
3 5 1 4 6 2 3
Суммарное расстояние:
3 – 5 – 1 – 4 – 6 – 2 – 3 Z = 4 + 7 + 8 + 10 + 3 + 7 = 39 км.
в)
4 5 2 4
8 9 3 8
10 7 10 3 11 13
4 5 1 2 6 3 4
Суммарное расстояние:
4 – 5 – 1 – 2 – 6 – 3 – 4 Z = 10 + 7 + 10 + 3 +11 + 13 = 54 км.
г) 4 6
5 3
10 3 7 4 7 8
4 6 2 3 5 1 4
Суммарное расстояние:
4 – 6 – 2 – 3 – 5 – 1 – 4 Z = 10 + 3 + 7 + 4 + 7 + 8 = 39 км.
д)
5 4 6
10 5 3
7 8 10 3 7 4
5 1 4 6 2 3 5
Суммарное расстояние:
5 – 1 – 4 – 6 – 2 – 3 – 5 Z = 7 + 8 + 10 + 3 + 7 + 4 = 39 км.
е)
6 6 2 4 5 6
3 10 10 8 9 11
3 5 10 7 12 15
6 2 4 5 1 3 6
Суммарное расстояние:
6 – 2 – 4 – 5 – 1 – 3 – 6 Z = 3 + 5 + 10 + 7 + 12 + 15 = 52 км.
Оптимальными маршрутами следования будут:
1 – 4 – 6 – 2 – 3 – 5 – 1;
3 – 5 – 1 – 4 – 6 – 2 – 3;
4 – 6 – 2 – 3 – 5 – 1 – 4;
5 – 1 – 4 – 6 – 2 – 3 – 5.
Для всех этих маршрутов общее расстояние обхода всех городов является минимальным и составляет 39 км.
Метод ветвей и границ
Метод ветвей и границ относится к комбинаторным оптимизационным методам. Он предполагает направленный перебор вариантов и в ряде случае позволяет уйти от полного перебора. Метод основан на разбиении всего множества решений задачи на подмножества (ветвление) и оценивании стоимости решения на каждом подмножестве.
Рассмотрим общую идею и алгоритм решения задачи коммивояжера методом ветвей и границ с помощью алгоритма Литтла.
Пусть W – множество всех замкнутых маршрутов, проходящих через все города по одному разу. Такие маршруты называют гамильтоновыми контурами. Для каждого маршрута известна его длина. Основная идея метода состоит в том, что вначале находят нижнюю границу длин всех гамильтоновых контуров W0, т.е. число, не большее, чем длина любого гамильтонова контура (нижняя оценка длины маршрута ). Это число может быть найдено до того, как найден сам наиболее короткий маршрут.
Далее все множество гамильтоновых контуров разбивается на два подмножества таким образом, чтобы любой контур в первом множестве 
содержал некоторую дугу (i, j), т.е. переход из города i в город j; второе множество 
состоит из контуров, эту дугу не содержащих. Для каждого из этих подмножеств определяются нижние границы длины входящих в них гамильтоновых контуров (нижняя оценка длины маршрута) аналогично тому, как это определялось для всего множества. Для дальнейшего рассмотрения выбирается подмножество с меньшей оценкой. Это подмножество в свою очередь подвергается ветвлению на два, для каждого из которых определяется нижняя оценка длины маршрута. Из всех не исследованных к данному моменту подмножеств (т. е. таких, которые еще не были подвергнуты разбиению, или ветвлению ) для дальнейшего рассмотрения выбирается подмножество с меньшей оценкой и т. д. пока не будет определен гамильтонов контур минимальной длины. Параллельно расчетам строится дерево ветвления.
Рассмотрим основные шаги решения.
1 шаг. Осуществить приведение матрицы по строкам: определить минимальный элемент каждой строки и вычесть из элементов строк найденный минимальный элемент.
2 шаг. Осуществить приведение матрицы по столбцам: определить минимальный элемент в каждом столбце и вычесть из элементов столбцов найденный минимальный элемент.
3 шаг. Найти константу приведения (j0) как сумму найденных минимальных элементов строк и столбцов. Константа приведения j0 является нижней границей длины для множества гамильтоновых контуров.
4 шаг. Для каждого нуля приведенной матрицы определить его «степень» как сумму минимальных элементов строки и столбца, содержащих этот нуль.
5 шаг. Нулевой элемент с наибольшей степенью задает дугу (t0, j0), по которой проводится разбиение множества гамильтоновых контуров (t0 – строка, а j0 – столбец, на пересечении которых находится выбранный нулевой элемент). В множество 
включаются все контуры, содержащие эту дугу, в множество 
– не содержащие ее.
6 шаг. Матрицу, описывающую множество , получаем из приведенной матрицы путем вычеркивания строки to и столбца jo. На дереве ветвления обозначаем, что рассматриваются контуры, включающие дугу (t0, j0). Вводя в маршрут дугу (to, jo), следует заблокировать все изолированные контуры, которые могут содержать эту дугу. Для блокировки в соответствующую клетку матрицы вводится «¥». В частности, значение элемента (jo, to) в матрице заменяем на ¥, так как рассматриваются маршруты, содержащие переход из города t0 в j0, а значит, обратный переход из города jo в to уже невозможен.
7 шаг. Выполнить приведение матрицы множества по строкам и столбцам и определить нижнюю границу этого множества по формуле:
,
где
– сумма минимальных элементов, используемых для приведения матрицы множества .
8 шаг. Матрицу множества 
получаем из исходной матрицы, рассматриваемой на шаге 4, заменой элемента (to, jo) на ¥.
9 шаг. Для полученной матрицы множества определить константу приведения ( 
) и нижнюю границу множества по формуле
,
выполнить приведение матрицы.
10 шаг. Дальнейшему ветвлению подвергается подмножество, имеющее меньшее значение нижней границы.
11 шаг. Для выбранного множества повторить шаги 4–9.
12 шаг. Процесс считается завершенным, когда остается матрица размера 2х2. Для данной матрицы в гамильтонов контур включаются связи, соответствующие нулевым элементам.
13. шаг. Найти длину полученного гамильтонова контура и сравнить ее с оценками (нижними границами) еще не исследованных множеств. Если все нижние границы не исследованных множеств больше или равны длине найденного контура, задача считается решенной. В противном случае следует продолжить ветвление с множества, имеющего наименьшую нижнюю границу.
Задача
Решить методом ветвей и границ задачу коммивояжера со следующей матрицей расстояний (эта же задача решалась в предыдущем параграфе методом ближайшего соседа).
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
Решение
Осуществим приведение матрицы по строкам, определив минимальное значение в каждой строке (ui).
| Города | ui | ||||||
| ¥ | |||||||
| ¥ | |||||||
| ¥ | |||||||
| ¥ | |||||||
| ¥ | |||||||
| ¥ |
Вычтем минимальные элементы из соответствующих строк и определим сумму минимальных значений.
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
Осуществим приведение матрицы по столбцам, определив минимальное значение в каждом столбце (ni).
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ni |
Вычтем минимальные элементы из соответствующих столбцов и определим сумму минимальных значений.
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
.
Константа приведения: 
Найдем степени нулей для приведенной матрицы. Для этого выберем минимальные элементы в строке и столбце, где расположен нуль, и просуммируем их.
| Города | ||||||
| ¥ | 2 | 03 | ||||
| ¥ | 02 | |||||
| ¥ | 09 | |||||
| ¥ | 00 | 00 | ||||
| 05 | 02 | ¥ | ||||
| 07 | ¥ |
Наибольшая степень нулевого элемента равна девяти и соответствует связи (3,5). Разобьем множество гамильтоновых контуров на два подмножества 
и 
.
Матрицу множества получаем вычеркиванием третьей строки и пятого столбца приведенной матрицы. Элемент (5,3) заменим на ¥.
| Города | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ |
Сделаем приведение полученной матрицы по третьему столбцу (нет нулевого элемента) и определим нижнюю границу множества.
| Города | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ |
Матрицу множества получим путем замены элемента (3,5) на ¥.
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ¥ | |||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
Осуществим приведение матрицы по третьей строке (нет нулевого элемента) и определим нижнюю границу множества.
| Города | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ¥ | |||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
.
Отобразим проделанные действия на дереве ветвления.
W0 j0 = 37
(3,5) 
Для дальнейшего исследования выбираем множество , т. к. ему соответствует меньшая нижняя граница: 
< 
. Множество подвергаем дальнейшему ветвлению
Находим степени нулей матрицы множества .
| Города | |||||
| ¥ | 00 | 02 | |||
| ¥ | 00 | 00 | |||
| 00 | ¥ | 00 | |||
| 010 | ¥ | ||||
| 06 | ¥ |
Ячейка (5,1) содержит наибольшую степень нуля. Разобьем множество на два подмножества 
и 
. Матрицу подмножества получаем из матрицы множества вычеркиванием в последней пятой строки и первого столбца. Кроме того, дуги (3,5) и (5,1), введенные в маршрут, могут породить изолированный контур, поэтому в клетку (1,3) поместим ¥.
(3,5)®(5,1)
| Города | ||||
| ¥ | 0 | |||
| ¥ | 0 | 0 | ||
| 0 | ¥ | 0 | ||
| 0 | ¥ |
В данной матрице все строки и столбцы содержат нулевые элементы, поэтому нижняя граница множества остается равной 39:
Матрицу подмножества получаем из матрицы множества заменой значения элемента (5,1) на ¥.
| Города | |||||
| ¥ | 0 | 0 | |||
| ¥ | 0 | 0 | |||
| 0 | ¥ | 0 | |||
| ¥ | ¥ | ||||
| 0 | ¥ |
Приведем матрицу по первому столбцу (минимальное значение равно 5) и по пятой строке (минимальное значение равно пяти).
| Города | |||||
| ¥ | 0 | 0 | |||
| ¥ | 0 | 0 | |||
| 0 | ¥ | 0 | |||
| ¥ | ¥ | ||||
| 0 | ¥ |
Нижняя граница множества:
.
Сравним нижние границы множеств, еще не подверженных ветвлению. Так как 
< 
< 
, то дальнейшему ветвлению подвергнем множество . Обозначим это на дереве ветвления (см. рис. 3.3.1).
Определим степени нулей матрицы множества .
| Города | ||||
| ¥ | 04 | |||
| ¥ | 00 | 00 | ||
| 00 | ¥ | 00 | ||
| 06 | ¥ |
Ячейка (6,2) имеет наибольшую степень нуля. Разобьем множество на два подмножества 
и 
. Константа приведения для матрицы множества равна нулю.
| Города | |||
| 0 | 0 | ||
| 0 | ¥ | ||
| 0 | ¥ | 0 |
Нижняя граница множества:
.
Подмножество получаем из множества заменой значения элемента (6,2) на ¥.
| Города | ||||
| 0 | 0 | |||
| ¥ | 0 | 0 | ||
| 0 | ¥ | 0 | ||
| ¥ | ¥ |
Сделаем приведение матрицы по столбцу 2 и строке 6. Минимальный элемент равен двум.
| Города | ||||
| 0 | 0 | |||
| ¥ | 0 | 0 | ||
| 0 | ¥ | 0 | ||
| ¥ | ¥ |
Нижняя граница множества равна 45:
.
Из всех множеств, еще не подвергнутых ветвлению ( 
, 
, 
, 
) выбираем как имеющее наименьшую нижнюю границу (см. рис. 3.3.1).
Находим степени нулей матрицы множества .
| Города | |||
| 00 | 02 | ||
| 02 | ¥ | ||
| 00 | ¥ | 03 |
Ячейка (4,6) содержит наибольшую степень нуля. Разобьем множество на два подмножества 
и 
. Множество получим вычеркиванием четвертой строки и шестого столбца множества . Для удаления изолированного контура
(4,6)®(6,2)
введем ¥ в клетку (2,4).
| Города | ||
| 0 | 0 | |
| 0 | ¥ |
Константа приведения данной матрицы равна нулю. Нижняя граница множества равна:
.
Множество получим из множества заменой значения элемента (4,6) на ¥.
| Города | |||
| 0 | 0 | ||
| 0 | ¥ | ||
| 0 | ¥ | ¥ |
Приведение матрицы проведем по шестому столбцу. Минимальный элемент равен трем.
| Города | |||
| 0 | 0 | ||
| 0 | ¥ | ||
| 0 | ¥ | ¥ |
Нижняя граница множества равна:
.
Множество имеет наименьшую нижнюю границу из всех еще не рассмотренных множеств. Поэтому подвергаем множество дальнейшему исследованию. Матрица множество имеет размерность 2х2. В гамильтонов контур включим связи (1,4) и (2,3).
Таким образом, в полученный гамильтонов контур Г входят связи (3,5), (5,1), (6,2), (4,6), (1,4), (2,3), после их упорядочивания получаем маршрут: 3 – 5 – 1 – 4 - 6 – 2 – 3. Полное дерево ветвлений представлено на рисунке (рис. 3.3.1).
Длина гамильтонова контура:
Z = 3 – 5 – 1 – 4 - 6 – 2 - 3 = 4 + 7 + 8 + 10 + 3 + 7 = 39 км.
W0 j0 = 37