Задача коммивояжёра. Метод ветвей и границ.

27. (5х5) (Засчитывается за 4 условные задачи) время на исполнение 2 пары) (Презентация КОММИВОЯЖЁР) Самая сложная задача исследования операций

.

Методом ветвей и границ требуется найти Кратчайший маршрут объезда 5 городов с возвратом в исходный, при КОТОРОМ КАЖДЫЙ ГОРОД ПОСЕЩАЕТСЯ в ТОЧНОСТИ 1 раз (в матрице даны цены проезда из «левого» города в «верхний»).

Решение Методом ветвей и границ

11. Шаг №0 Оцениваем цикл 1-2-3-4-5-1 – это первое приближение верхней оценки. Далее, если на любой ветви дерева ветвления нижняя оценка подмножества решений окажется выше верхней эта ветвь «отмирает» , т.к. все её решения хуже уже имеющегося.

12. Шаг №1а) Выписываем константы редуцирования по строкам. Это минимальные числа в строках. Их надо вычесть из элементов своих строк (при этом появится не менее одного нуля в каждой строке).

13. Шаг №1б) В только что полученной на шаге 1а) матрице (с нулями в строках) ровно ту же операцию проводи и по столбцам - ищем столбцы, где минимум е равен 0 и вычитаем его. В формате самопроверки убедитесь, что теперь в каждом столбце и каждой строке матрицы стоимостей проезда имеется хотя бы один ноль.

14. Шаг №1в) Вычисляем сумму констант редуцирования полученных на шагах а) и б). Очевидно, никакой маршрут не может стоить дешевле – поэтому это оценка снизу. Далее мы будем увеличивать эту оценку на величину и(эти величины опишем ниже), где- пара индексов ребра, по которому выбрано производить ветвление.

15. Опишем, как будет происходить ветвление: выбираем ребро i,j(удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).

16. Теоретически можно производить ветвление по любому ребру, но наша задача в том, чтобы на одном множестве нижняя оценка цены маршрута не изменилась, а на другом максимально выросла – это может способствовать тому, что в большинстве случаев комбинаторный перебор, вообще говоря, экспоненциального алгоритма решения NPполной задачи окажется не слишком большой.

17. Для этого: Шаг №2. Вычисляем стоимости обхода для каждого нулевого элемента (если он превратился в бесконечность ∞) - величина на которую увеличиваются константы редуцирования соответствующей строки и столбца.

18. Разбиваем текущее множество решений на два:

    1. Большое – правое на дереве ветвления, где элемент i,jзапрещён – ПОД-задача с матрицей на месте элементаi,jстоит бесконечность и

    2. Малое - левое, где элемент i,jна пути обязателен ПОД-задача, где городаiна въезд иjна выезд отождествлены. В этой второй задаче требуется нетривальная дополнительная подготовка матрицы – в ответ на каждое такое отождествление нужно запретить одно и только одно дополнительное ребро. Это совсем легко и понятно на первом шаге, когда запрещается просто встречное ребро. Общее правило в той же логике. Послеnотождествлений существует набор звеньев обязательных к прохождению. Они могут, так сказать, «полимеризоваться» в длинные и не очень цепочки. Они могут быть однозвеные – тогда как ранее нужно запретить встречное ребро. Если цепочка длинная 3-4-5 – состоит из двух ребер 3-4 и 4-5, одно из которых – не важно какое, только что добавилось, то запрещается ребро, замыкающее всю цепочку – это ребро 5-3 – именно его надо запретить (кстати, встречного ребра, в этот момент, в матрице уже просто нет, Вы его не сможете запретить, даже если захотите: оно исчезло с предыдущими вычеркиваниями строк и столбцов).

    3. Рассчитываются приращения суммы констант редуцирования в каждой задаче. В правой – большой задаче это выбранное . В левой малой задаче- обусловленное, главным образом запрещением замыкающего (встречного или иного) ребра в предыдущем пункте в малой задаче.

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

    5. Ветвить на каждом шаге предстоит наиболее перспективную задачу – таковой считается задача с наименьшей нижней оценкой.

19. Процесс отчасти заканчивается после выбора k-2 ребер, гдеkобщее число вершин. В задаче 2х2 решение однозначно, оно (обычно) приводит к коррекции верхней оценки. Если все (остальные) нижние оценки хуже, ответ получен. В таком примере как приведенный в этом задании как правило имеет место эта ситуация, но в более большом и сложном графе (при создании универсального алгоритма), требуется описать дальнейшие действия. Если всё ещё не все нижние оценки хуже чем скорректированная верхняя оценка, то выжившие нетривиальные множества придется ветвить до тех пор пока либо они не исчезнут из-за высокой, т.е. плохой нижней оценки, либо (что редко) до того как будет получена новая верхняя оценка - новое решение, превосходящее по качеству предыдущее. Процесс продолжается до тех пор, пока полученное решение не останется безальтернативным.

Пример:

Рассмотрим матрицу стоимостей проезда из «левого» города в «верхний»

Начальная глобальная оценка Zверхняя=10+10+20+15+10 = 65 получим по циклу. (соответствующие рёбра, обведены квадратами на рисунке - одно в левом нижнем углу, остальные над диагональю).

Начинаем рисовать дерево ветвления

В полученной матрице

рассчитаем дополнительную цену «объезда» каждого отдельного нуля(то есть, на сколько возрастёт сумма констант редуцирования, если дорога перестанет существовать (цена проезда будет заменена на бесконечность)) и выберем, тот «ноль», цена объездакоторого максимальна.

(1,2)=0

(1,5)=1

(2,1)=0

(2,3)=5 (Максимальная )

(3,1)=0

(3,4)=2

(4,2)=4

(5,2)=2

Итак, максимальная цена объезда  наблюдается при выключении ребра (2,3)=5.

Нашим алгоритмом, естественно разделить все циклы объезда на содержащие ребро (2,3) и не содержащие его. Нижняя оценка стоимости первой группы циклов (мы её посчитаем позже), скорее всего не изменится, нижняя оценка циклов не включающих (2,3) возрастает на величину (2,3)=5.

На отдельной странице начинаем вырисовывать дерево ветвления.

На начальном этапе оно содержит множество всех циклов, которое разбивается на множество содержащее (2,3) (их меньше)– слева и не содержащее (2,3) – справа.

Нижняя оценка (большего) правого множества получается суммой оценки предшествующей вершины Z_min=58 и(2,3)=5:Z_min=58+5=63.

В левом множестве ребро (2,3) (условно говоря путь Санкт-Петербург - Москва) является обязательным – соответственно мы более не имеем выбора куда поехать из города 2 (удалим строку 2) и как приехать в город №3 (удалим столбец).

Итоговое дерево ветвления:

Финал метода.

Получается матрица размера 2х2.

Маломерный пример.

В заключении рассмотрим матрицу 3х3.

Тогда верхняя граница длин всех маршрутов Z_max= 4+9+8 = 21

Таким образом, нижняя оценка Z_нижн=16 (6+3+4+3).

Оцениваем константы обхода:

объединим города 2 и 1 в левой ветке, в правой ветке нижняя оценка стоимости возрастёт с 16 на 5 до 21.

получаем матрицу

Запретим короткое замыкание - во избежание

и редуцируем матрицу

На левой ветке ΔZ_=4, новая оценка целевой функции Z_=16+ ΔZ_=16+4=20.

Выбрано ребро

Остались рёбра .

По принципу домино восстанавливаем минимальный цикл начиная с ребра начинающегося с 1, у на с это ребро , как бы идущего "паровозиком".

Это конкретный путь длина 20 в этот момент мы получаем новую верхнюю оценку, что лучше старой верхней оценки 21.

На дереве ветвления множеств перебора исчезает ветвь с более высокой нижней оценкой 21 (правая ветвь).

В нашем случае полученный вариант оказался лучше всех нижних оценок по другим ветвям.

Ответ: .

Проверка

Сумма .

28. (Ком4х4), (3 задачи – засчитывается только 1 из двух задач) Сокращённая задача Коммивояжера 4х4

Презентация КОММИВОЯЖЁР.

Задача проверяется преподавателем по оформлению дерева ветвления. Чтобы на нём была представлена максимально полная необходимая для проверки информация в вершинах дерева отобразить нижние оценки целевых функций, на рёбрах дерева обязательно должны быть отображены все θ (рост суммы констант редуцирования на правом повороте), все ΔZ(рост суммы констант редуцирования при левом повороте). При левом повороте выбирается одно обязательное ребро (отмечается на дереве ветвления) и добавляется одно запрещённое ребро. Для объяснения его выбора рядом с деревом ветвления на соответствующем уровне должна быть изображена цепочка в которой запрещаемое ребро вкупе с ранее выбранными (включая сейчас выбранное) порождает цикл не проходящий через все рёбра (так называемое «короткое замыкание» цикла).

В ответе дается цепочка Рёбер вида (1,k)(k,l)(l,m)..(r,1)(по размеру задачи), стоимость маршрута состоит из начальной нижней оценки и её приращений ΔZ(если были только ВЫЧЁРКИВАНИЯ – левые ПОВОРОТЫ) и – что бывает очень редко - ΔZи θ, если КРОМЕ левых ПОВОРОТОВ присутствовали один или несколько правых поворотов. Провести проверку стоимости ПОЛУЧЕНОГО решения по исходной матрице, объяснить причины несовпадения – если имелись (не совпадений быть не должно).