Номер варианта выбирается по параметру зачетки d 10 соотв. 0 1. 2. 3. 4. 5.6. 7.8. 9 10. Задача Коммивояжёра Имеется n городов, занумерованных числами. - презентация

1 Номер варианта выбирается по параметру зачетки d 10 соотв Задача Коммивояжёра Имеется n городов, занумерованных числами 1,2,...,n. Для любой пары городов (i,j) задано расстояние (время, путевые расходы) C(i,j) 0 между ними. Поэтому в общем случае C(i,j) C(j,i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной. Можно взять задач 5х5, вычеркнув пару строку&столбец по номеру b mod6 По номеру c По особому разрешению преподавателя можно вычеркнуть после этого столбец и строку с mod 5 (Если исп ФИО, то по а)

2 Постановка целочисленная ЗЛП Ограничения требуют, чтобы маршрут образовывал контур Москва Питер Астрахань Минск Киев Ростов Екатеринбург Верный Путь

3 Процедура коррекции длин (ввод субсидий) таможня Можно избрать

4 Пример 3х3 Самая зловредная θ Дерево решения Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 21 - текущее значение Z 0 Нижняя оценка Z нижн =16 ( ) Меньшая оценка соответствует нашей (левой) вершине Ищем путь Ответ: его длина проверка

5 Алгоритм ветвей и границ Допустимый маршрут х представим как множество упорядоченных пар городов: X = (i 1,i 2 ), (i 2,i 3 ),…,(i n-1,i n ), (i n,i 1 ). Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i,j) является дугой маршрута. Длина F(X) маршрута X равна сумме соответствующих элементов C(i,j). Возможно (n-1)! маршрутов !!

6 Флаг Русский Польский Советский для 20 : 20*19*18… для 4 : 4 * 3 * 2 * 1 = … маршрут х X = (i 1,i 2 ), (i 2,i 3 ),…,(i n-1,i n ), (i n,i 1 ). С учётом безразличности выбора начала

7 - Редуцированная матрица. пусть Пусть - сумма констант редуцирования Тогда для любого маршрута Оценка длины с низу! после редукции длины всех маршрутов уменьшаются на одну и ту же величину d(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

8 Построение редуцированных матриц и и вычисление оценок снизу Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х ветвится Х с наименьшей н.оценкой. тогда

9 В качестве начального возьмём Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 Получим редуцированную матрицу Нижняя граница d(x) = =58. в идеальном случае поиск решения заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы такой маршрут нулевой длины мог бы быть найден, то длина оптимального маршрута равнялась бы 58 (1,2)=0, (2,1)=0, (3,1)=0, (4,2)=4, (1,5)=1, (2,3)=5, (3,4)=2, (5,2)=2. Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). вычитаем

10 Верхняя граница Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 Придумаем простой путь

11 (1,2)=0, (2,1)=0, (3,1)=0, (4,2)=4, (1,5)=1, (2,3)=5, (3,4)=2, (5,2)=2. Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). (5,2)=2. (1,2)=0, (2,3)=5, (3,4)=2, (1,5)=1, (2,1)=0, (3,1)=0, (4,2)=4,

12 (5,2)=2. (1,2)=0, (2,3)=5, (3,4)=2, (1,5)=1, (2,1)=0, (3,1)=0, (4,2)=4, Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). «Отъехать» «Приехать» Zmin=58 Zmin=? (2,3), Zmin>= 58+5=63 не(2,3),

13 допустимо Левое подмножество X 1 будет содержать маршруты, которые всегда включают дугу (2,3), и поэтому вторая строка и третий столбец в матрицу C 1 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить дугу с 1 (3,2)=, чтобы запретить подцикл {(2,3),(3,2)}. Оценка снизу для левого подмножества Ветвим множество имеющее меньшую оценку

14 (4,2)=4 С(3,4)= (4,2) запретить подцикл {(4,2)(2,3),(3,4)}. (2,3)(2,3) редуцируем Уже выбранные рёбра

15 Самая зловредная θ

16 Ответ: (3,4) (2,3)(2,3) Уже выбранные рёбра (4,1) ЗАПРЕТИТЬ (1,2) Остались (5,2) и (1,5) (1,5) (5,2) длина (2,3)(2,3)(3,4)(4,1)

17 Проверка / ответ Кратчайшим путём является цикл Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 (1,5) (5,2)(2,3)(2,3)(3,4)(4,1)