Решение задачи коммивояжера методом ветвей и границ (стр. 2 из 3)

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

11. Если в результате ветвлений получаем матрицу

, то определяем полученный ветвлением гамильтонов контур и его длину.

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

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

Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных

, если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений

(1)

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная

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

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

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

, где , и .

4. Алгоритм решения

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

Табл.1

ji	1	2	3	4	5	6
1	∞	7	16	21	2	17
2	13	∞	21	15	43	23
3	25	3	∞	31	17	9
4	13	10	27	∞	33	12
5	9	2	19	14	∞	51
6	42	17	5	9	23	∞

1) Справа к таблице присоединяем столбец U_i, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы U_i из соответствующих элементов строки матрицы.

ji	1	2	3	4	5	6	Ui
1	∞	7	16	21	2	17	2
2	13	∞	21	15	43	23	13
3	25	3	∞	31	17	9	3
4	13	10	27	∞	33	12	10
5	9	2	19	14	∞	51	2
6	42	17	5	9	23	∞	5

2) Внизу полученной матрицы присоединяем строку V_j, в которой записываем минимальные элементы столбцов. Вычитаем элементы V_j из соответствующих столбцов матрицы.

ji	1	2	3	4	5	6
1	∞	5	14	19	0	15
2	0	∞	8	2	30	10
3	22	0	∞	28	14	6
4	3	0	17	∞	23	2
5	7	0	17	12	∞	49
6	37	12	0	4	18	∞
Vj	0	0	0	2	0	2

3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.

Табл.2

ji	1	2	3	4	5	6
1	∞	5	14	17	019	13
2	03	∞	8	02	30	8
3	22	04	∞	26	14	4
4	3	00	17	∞	23	04
5	7	07	17	10	∞	47
6	37	12	08	2	18	∞

4) Находим константу приведения

Таким образом, нижней границей множества всех гамильтоновых контуров будет число

5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак «∞» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых

.

6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5).

7) Разбиваем множество всех гамильтоновых контуров

на два: и . Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».

ji	1	2	3	4	6
2	0	∞	8	0	8
3	22	0	∞	26	4
4	3	0	17	∞	0
5	∞	0	17	10	47
6	37	12	0	2	∞

8) Матрицу гамильтоновых контуров

получим из таблицы 2 путем замены элемента (1;5) на знак «∞».

ji	1	2	3	4	5	6
1	∞	5	14	17	∞	13	5
2	0	∞	8	0	30	8
3	22	0	∞	26	14	4
4	3	0	17	∞	23	0
5	7	0	17	10	∞	47
6	37	12	0	2	18	∞
14

9) Делаем дополнительное приведение матрицы контуров

: = 0. Нижняя граница множества равна .

10) Находим константу приведения для множества контуров

:

Следовательно, нижняя граница множества

равна

11) Сравниваем нижние границы подмножеств

и . Так как

то дальнейшему ветвлению подвергаем множество

.

На рис.1 представлено ветвление по дуге (1;5).

Рис.1

Переходим к ветвлению подмножества

. Его приведенная матрица представлена в таблице ниже.

ji	1	2	3	4	6
2	03	∞	8	02	8
3	22	04	∞	26	4
4	3	00	17	∞	04
5	∞	010	17	10	47
6	37	12	010	2	∞

12) Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг (5;2) и (6;3). Для дальнейших расчетов выберем дугу (6;3). Разбиваем множество

на два подмножества: и (табл. 3 и 4). Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак «∞»