Метод ветвей и границ задача коммивояжера: Метод ветвей и границ. Задача коммивояжера / Хабр

Содержание

Решение задачи коммивояжера методом ветвей и границ

07.12.2019 Artman Математическое программирование

Задача коммивояжёра заключается в разовом посещение всех городов по минимальному пути (маршруту) и возвращение в искомый город.

Рассмотрим пример решения задачи коммивояжёра методом ветвей и границ

Первая итерация

Найдём минимальные значения по строкам d_i

Производим редукцию по строкам путём вычитания минимального значения.

Найдём минимальные значения по столбцам d_j

Аналогично производим редукцию по столбцам.

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

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

Выберем значения в таблице с максимальной оценкой

Сократим матрицу потерь за счёт исключения строки и столбца с наибольшей оценкой в нашем случае 5→3, так как это оптимальный путь, которые соответствует как городу отправления, так и городу назначения, при этом, расстоянии равно нулю.

Получаем новую матрицу потерь

В третьей строке необходимо вместо нуля (минимального значения) поставить ∞, чтобы отсечь посещённые города.

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

Максимальная оценка нулевого значения находится в 4 строке и 5 столбце, поэтому их сокращаем. Получаем путь 50 ед. и 4→5. Матрица потерь примет вид

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

Третья итерация решения задачи коммивояжера

Максимальная оценка нулевого значения находится в 1 строке и 2 столбце. Получаем путь 100 ед. и 1→2.

Получим матрицу потерь 2 на 2

В нашем случае имеется обратный путь, поэтому ставим знак ∞ и матрица потерь будет иметь вид.

Города	1	4
2	∞	50
3	0	0

Четвертая итерация задачи коммивояжера методом ветвей и границ

Города	1	4	d_i
2	∞	50	50
3	0	0	0

Города	1	4	d_i
2	∞	0	50
3	0	0	0

Города	1	4
2	∞	0
3	0	0
d_j	0	0

Города	1	4
2	∞	0
3	0	0
d_j	0	0

Города	1	4
2	∞	0⁽^∞⁾
3	0⁽^∞⁾	0⁽⁰⁾

Города	1	4
2	∞	0⁽^∞⁾
3	0⁽^∞⁾	0⁽⁰⁾

Сокращаем с максимальной оценкой нулевого значения — это строка 3 и столбец 1 и получаем примитивную матрицу, в которой отсутствует обратный путь. В нашем случае оптимальный путь равен 50 ед. и 3→1.

Города	4
2	0

Эта матрица говорит о том, что город 2 и город 4 не замкнуты, длина пути равна 50 ед.

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

1→2→4→5→3→1

и длина его равна 250.

См. также

Решение данной задачи коммивояжёра в Excel

5119

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

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

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

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

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

Очевидно, никакой маршрут не может стоить дешевле – поэтому это оценка снизу. Далее мы будем увеличивать эту оценку на величину и(эти величины опишем ниже), где- пара индексов ребра, по которому выбрано производить ветвление.
Опишем, как будет происходить ветвление: выбираем ребро i,j(удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).
Теоретически можно производить ветвление по любому ребру, но наша задача в том, чтобы на одном множестве нижняя оценка цены маршрута не изменилась, а на другом максимально выросла – это может способствовать тому, что в большинстве случаев комбинаторный перебор, вообще говоря, экспоненциального алгоритма решения NPполной задачи окажется не слишком большой.
Для этого: Шаг №2. Вычисляем стоимости обхода для каждого нулевого элемента (если он превратился в бесконечность ∞) — величина на которую увеличиваются константы редуцирования соответствующей строки и столбца.
Разбиваем текущее множество решений на два:
1. Большое – правое на дереве ветвления, где элемент i,jзапрещён – ПОД-задача с матрицей на месте элементаi,jстоит бесконечность и
2. Малое — левое, где элемент i,jна пути обязателен ПОД-задача, где городаiна въезд иjна выезд отождествлены. В этой второй задаче требуется нетривальная дополнительная подготовка матрицы – в ответ на каждое такое отождествление нужно запретить одно и только одно дополнительное ребро. Это совсем легко и понятно на первом шаге, когда запрещается просто встречное ребро. Общее правило в той же логике. Послеnотождествлений существует набор звеньев обязательных к прохождению.
  Они могут, так сказать, «полимеризоваться» в длинные и не очень цепочки. Они могут быть однозвеные – тогда как ранее нужно запретить встречное ребро. Если цепочка длинная 3-4-5 – состоит из двух ребер 3-4 и 4-5, одно из которых – не важно какое, только что добавилось, то запрещается ребро, замыкающее всю цепочку – это ребро 5-3 – именно его надо запретить (кстати, встречного ребра, в этот момент, в матрице уже просто нет, Вы его не сможете запретить, даже если захотите: оно исчезло с предыдущими вычеркиваниями строк и столбцов).
3. Рассчитываются приращения суммы констант редуцирования в каждой задаче. В правой – большой задаче это выбранное . В левой малой задаче- обусловленное, главным образом запрещением замыкающего (встречного или иного) ребра в предыдущем пункте в малой задаче.
4. Полученные матрицы подвергаются редуцированию. На практике сиюминутно редуцировать надо только матрицу, опсывающую лучшее множество, которое и предстоит ветвить.
5. Ветвить на каждом шаге предстоит наиболее перспективную задачу – таковой считается задача с наименьшей нижней оценкой.
Процесс отчасти заканчивается после выбора 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 (правая ветвь).

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

Ответ: .

Проверка

Сумма .

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

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

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

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

Задача коммивояжера с использованием ветвей и границ

следующий → ← предыдущая

Учитывая вершины, проблема здесь в том, что мы должны пройти через каждую вершину ровно один раз и вернуться в начальную точку. Рассмотрим приведенный ниже график:

Как видно из приведенного выше графика, в графе задано 5 вершин. Нам нужно найти кратчайший путь, проходящий через все вершины один раз и возвращающийся обратно в начальную вершину. В основном мы рассматриваем начальную вершину как 1, затем проходим через вершины 2, 3, 4 и 5 и, наконец, возвращаемся к вершине 1.

Смежная матрица задачи приведена ниже:

Теперь посмотрим, как можно решить эту задачу, используя границу ветви n.

Давайте сначала разберемся с подходом, а затем решим вышеуказанную проблему.

Ниже приведен граф, который имеет четыре вершины:

Предположим, мы начинаем путешествие из вершины 1 и возвращаемся обратно в вершину 1. Существуют различные способы пройти через все вершины и вернуться в вершину 1. Нам нужны некоторые инструменты, которые можно использовать для минимизации общих затрат. Чтобы решить эту проблему, мы делаем дерево пространства состояний. Из начальной вершины 1 мы можем перейти к вершинам 2, 3 или 4, как показано на диаграмме ниже.

Из вершины 2 мы можем перейти либо к вершине 3, либо к вершине 4. Если мы рассмотрим вершину 3, мы перейдем к оставшейся вершине, т.е. 4. Если мы рассмотрим вершину 4, показанную на диаграмме ниже:

Из вершины 3 мы можем перейти к остальным вершинам, т.е. 2 или 4. Если мы рассматриваем вершину 2, то переходим к оставшейся вершине 4, а если рассматриваем вершину 4, то переходим к оставшейся вершине, т.е. , 3 показано на диаграмме ниже:

Из вершины 4 можно перейти к остальным вершинам, т. е. к 2 или 3. Если рассматривать вершину 2, то переходим к оставшейся вершине, т. е. к 3, а если рассматривать вершину 3, то переходим к оставшаяся вершина, т. е. 2, показанная на диаграмме ниже:

Выше приведено полное дерево пространства состояний. Дерево состояний показывает все возможности. И поиск с возвратом, и переход с n-связью используют дерево пространства состояний, но их подход к решению проблемы отличается. Branch nbound — лучший подход, чем поиск с возвратом, поскольку он более эффективен. Чтобы решить задачу, используя границу ветвей n, мы используем порядок уровней. Во-первых, мы посмотрим, в каком порядке генерируются узлы. При создании ноды мы одновременно посчитаем стоимость ноды. Если мы обнаружим, что стоимость любого узла превышает верхнюю границу, мы удалим этот узел. Итак, в этом случае мы будем генерировать только полезные узлы, а не все узлы.

Рассмотрим вышеуказанную проблему.

Как видно из соседней матрицы выше, 10 — это минимальное значение в первой строке, 2 — минимальное значение во второй строке, 2 — минимальное значение в третьей строке, 3 — минимальное значение в третьей строке. строке, 3 — минимальное значение в четвертой строке, а 4 — минимальное значение в пятой строке.

Теперь уменьшим матрицу. Мы вычтем минимальное значение из всех элементов строки. Сначала мы оцениваем первую строку. Предположим, что есть две переменные, т. е. i и j, где «i» представляет строки, а «j» представляет столбцы.

Когда i = 0, j = 0

М[0][0] = ∞-10= ∞

Когда i = 0, j = 1

М[0][1] = 20 — 10 = 10

Когда i = 0, j = 2

М[0][2] = 30 — 10 = 20

Когда i = 0, j = 3

М[0][3] = 10 — 10 = 0

Когда i = 0, j = 4

М[0][4] = 11 — 10 = 1

Матрица показана ниже после оценки первой строки:

Рассмотрим вторую строку.

Когда i = 1, j = 0

М[1][0] = 15-2= 13

Когда i = 1, j = 1

М[1][1] = ∞ — 2= ∞

Когда i = 1, j = 2

М[1][2] = 16 — 2 = 14

Когда i = 1, j = 3

М[1][3] = 4 — 2 = 2

Когда i = 1, j = 4

М[1][4] = 2 — 2 = 0

Матрица показана ниже после оценки второй строки:

Рассмотрим третью строку:

Когда i = 2, j = 0

М[2][0] = 3-2= 1

Когда i = 2, j = 1

М[2][1] = 5 — 2= 3

Когда i = 2, j = 2

М[2][2] = ∞ — 2 = ∞

Когда i = 2, j = 3

М[2][3] = 2 — 2 = 0

Когда i = 2, j = 4

М[2][4] = 4 — 2 = 2

Матрица показана ниже после оценки третьей строки:

Рассмотрим четвертую строку:

Когда i = 3, j = 0

М[3][0] = 19-3= 16

Когда i = 3, j = 1

М[3][1] = 6 — 3= 3

Когда i = 3, j = 2

М[3][2] = 18 — 3 = 15

Когда i = 3, j = 3

М[3][3] = ∞ — 3 = ∞

Когда i = 3, j = 4

М[3][4] = 3 — 3 = 0

Матрица показана ниже после оценки четвертой строки:

Рассмотрим пятую строку:

Когда i = 4, j = 0

М[4][0] = 16-4= 12

Когда i = 4, j = 1

М[4][1] = 4 — 4= 0

Когда i = 4, j = 2

М[4][2] = 7 — 4 = 3

Когда i = 4, j = 3

М[4][3] = 16 — 4 = 12

Когда i = 4, j = 4

М[4][4] = ∞ — 4 = ∞

Матрица показана ниже после оценки пятой строки:

Приведенная выше матрица является уменьшенной матрицей по отношению к строкам.

Теперь уменьшим матрицу по столбцам. Прежде чем уменьшать матрицу, мы сначала находим минимальное значение всех столбцов. Минимальное значение первого столбца равно 1, минимальное значение второго столбца равно 0, минимальное значение третьего столбца равно 3, минимальное значение четвертого столбца равно 0 и минимальное значение пятого столбца равно 0, как показано в приведенной ниже матрице:

Теперь уменьшаем матрицу.

Рассмотрим первый столбец.

Когда i = 0, j = 0

М[0][0] = ∞-1= ∞

Когда i = 1, j = 0

М[1][0] = 13 — 1= 12

Когда i = 2, j = 0

М[2][0] = 1 — 1 = 0

Когда i = 3, j = 0

М[3][0] = 16 — 1 = 15

Когда i = 4, j = 0

М[4][0] = 12 — 1 = 11

Матрица показана ниже после оценки первого столбца:

Поскольку минимальное значение первого и третьего столбцов не равно нулю, мы будем оценивать только первый и третий столбцы. Мы оценили первый столбец. Теперь мы оценим третий столбец.

Рассмотрим третий столбец.

Когда i = 0, j = 2

М[0][2] = 20-3= 17

Когда i = 1, j = 2

М[1][2] = 13 — 1= 12

Когда i = 2, j = 2

М[2][2] = 1 — 1 = 0

Когда i = 3, j = 2

М[3][2] = 16 — 1 = 15

Когда i = 4, j = 2

М[4][2] = 12 — 1 = 11

Матрица показана ниже после оценки третьего столбца:

Выше приведена уменьшенная матрица. Минимальное значение строк — 21, а столбцов — 4. Следовательно, общее минимальное значение (21 + 4) равно 25.

Давайте разберемся, как решить эту проблему, используя переход и привязку с помощью дерева в пространстве состояний.

Чтобы создать дерево в пространстве состояний, сначала рассмотрим узел 1. От узла 1 мы можем перейти к узлам 2, 3, 4 или 5, как показано на рисунке ниже. Стоимость узла 1 будет равна стоимости, которую мы получили в сокращенной выше матрице, т. Е. 25. Здесь мы также сохраним верхнюю границу. Изначально верхняя граница была бы бесконечностью.

Теперь рассмотрим узел 2. Это означает, что мы движемся от узла 1 к узлу 2. Сделайте первую строку и второй столбец бесконечными, как показано в приведенной ниже матрице:

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

Так как каждая строка и столбец содержат хотя бы одно нулевое значение; следовательно, мы можем сказать, что приведенная выше матрица была уменьшена. Стоимость сокращения узла 2 равна c(1, 2) + r + r` = 10 + 25 + 0 = 35,9.0006

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

Теперь рассмотрим узел 3. Это означает, что мы движемся от узла 1 к узлу 3. Сделайте первую строку и третий столбец бесконечными, как показано в следующей матрице:

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

Теперь рассмотрим узел 4. Это означает, что мы движемся от узла 1 к узлу 4. Сделайте первую строку и четвертый столбец бесконечностью, как показано в приведенной ниже матрице:

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

Теперь рассмотрим узел 5. Это означает, что мы движемся от узла 1 к узлу 5. Сделайте первую строку и пятый столбец бесконечностью, как показано в следующей матрице:

Как только мы перейдем от узла 1 к узлу 5, мы не сможем вернуться к узлу 1. Следовательно, мы должны сделать 5 к 1 как бесконечность, показанную в приведенной ниже матрице:

Так как каждая строка и столбец содержат хотя бы одно нулевое значение; следовательно, мы можем сказать, что приведенная выше матрица была уменьшена. В этом случае вторая и третья строки отличны от нуля. Следовательно, мы должны сначала найти минимальные значения обеих строк. Минимальное значение второй строки равно 2; поэтому из всех элементов второй строки вычитаем 2. Элементы второй строки будут:

А[1][0] = 12-2 = 10

А [1] [1] = ∞

А[1][2] = 11 — 2 = 9

А[1][3] = 2 — 2 = 0

А[1][4] = ∞ — 2 = ∞

Как мы видим теперь, вторая строка содержит одно нулевое значение.

Стоимость сокращения узла 5 равна c(1, 5) + r + r` = 1 + 25 + 5 = 31

Поскольку узел 4 имеет минимальную стоимость, т. е. 25. Поэтому сначала мы исследуем узел 4. Из вершины 4 мы можем перейти к вершине 2, 3 или 5, как показано на рисунке ниже:

Теперь нам нужно рассчитать стоимость пути от вершины 4 до вершины 2, вершины 4 до вершины 3 и вершины 4 до вершины 5. Здесь мы будем использовать матрицу узла 4, чтобы найти стоимость всех узлов.

Сначала рассмотрим путь из вершины 4 в вершину 2. Обозначим четвертую строку как ∞ и второй столбец как ∞. Поскольку мы не можем вернуться от 2 к 1, поэтому от 1 до 2 также бесконечность, как показано в приведенной ниже матрице:

Так как все строки и столбцы имеют хотя бы одно нулевое значение. Поэтому можно сказать, что эта матрица уже уменьшена. Так что снижения цены не будет. Стоимость сокращения узла 2 равна c(4, 2) + r + r` = 3 + 25 + 0 = 28

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

Теперь проверим, содержит ли каждая строка и столбец хотя бы одно нулевое значение или нет. Сначала наблюдаем за всеми рядами. Так как третья строка не имеет нулевого значения, то сначала находим минимальное значение третьей строки. Минимальное значение третьей строки равно 2, поэтому мы вычитаем 2 из всех элементов третьей строки. Элементы третьей строки будут:

А[2][0] = ∞ — 2 = ∞

А[2][1] = 3 — 2 = 1

А[2][2] = ∞ — 2 = ∞

А[2][3] = ∞ — 2 = ∞

А[2][4] = 2 — 2 = 0

Как мы видим, третья строка содержит одно нулевое значение.

Первый столбец не содержит нулевое значение. Минимальное значение первого столбца равно 11. Из всех элементов первого столбца вычитаем 11. Элементы первого столбца будут:

А[0][0] = ∞ — 11 = ∞

А[1][0] = 12 — 11 = 1

А[2][0] = ∞ — 11= ∞

А[3][0] = ∞ — 11= ∞

А[4][0] = 11 — 11 = 0

Теперь мы видим, что первый столбец содержит одно нулевое значение. Общая минимальная стоимость 11 + 2 равна 13. Стоимость сокращения узла 3 равна c(4, 3) + r + r` = 12 + 25 + 13 = 50,

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

Теперь проверим, содержит ли каждая строка и столбец хотя бы одно нулевое значение или нет. Сначала наблюдаем за всеми рядами. Вторая строка не содержит нулевого значения, поэтому находим минимальное значение второй строки. Минимальное значение равно 11, поэтому мы вычитаем 11 из всех элементов второй строки. Элементы второй строки будут:

А[1][0] = 12 — 11 = 1

А[1][1] = ∞ — 11 = ∞

А[1][2] = 11 — 11 = 0

А[1][3] = ∞ — 11 = ∞

А[1][4] = ∞ — 11 = ∞

Как мы видим теперь, вторая строка содержит одно нулевое значение. Стоимость сокращения узла 5 равна c(4, 5) + r + r` = 0 + 25 + 11 = 36,

Теперь сравним стоимость всех листовых узлов. Узел со стоимостью 28 является минимальным, поэтому мы исследуем этот узел. Узел со стоимостью 28 можно расширить до узлов 3 и 5, как показано на рисунке ниже:

Теперь нам нужно вычислить стоимость обоих узлов, т. е. 3 и 5. Сначала мы рассмотрим путь от узла 2 к узлу 3. Рассмотрим матрицу узла 2, показанную ниже:

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

Теперь проверим, содержит ли какая-либо строка нулевое значение или нет. Поскольку третья строка не содержит нулевого значения, мы найдем минимальное значение третьей строки. Минимальное значение третьей строки равно 2, поэтому мы вычитаем 2 из всех элементов третьей строки. Элементами третьей строки будут:

А[2][0] = ∞ — 2 = ∞

А[2][1] = ∞ — 2 = ∞

А[2][2] = ∞ — 2 = ∞

А[2][3] = ∞ — 2 = ∞

А[2][4] = 2 — 2 = 0

Поскольку пятая строка не содержит нулевого значения, найдем минимальное значение пятой строки. Минимальное значение пятой строки равно 11, поэтому мы вычитаем 11 из всех элементов пятой строки.

А[4][0] = 11 — 11 = 0

А[4][1] = ∞ — 11 = ∞

А[4][2] = ∞ — 11 = ∞

А[4][3] = ∞ — 11 = ∞

А[4][4] = ∞ — 11 = ∞

Общая минимальная стоимость (11 + 2) равна 13. Стоимость сокращения узла 3 равна c(2, 3) + r + r` = 11 + 28 + 13 = 52.

Рассмотрим путь от узла 2 к узлу 5. Сделайте четвертую строку и третий столбец бесконечными. Поскольку мы не можем вернуться от узла 5 к узлу 1, поэтому сделайте от 1 до 5 также бесконечность, как показано в приведенной ниже матрице:

Теперь проверим, содержит ли какая-либо строка нулевое значение или нет. Поскольку каждая строка и столбец содержат нулевое значение; следовательно, приведенная выше матрица является сокращенной матрицей.

Стоимость сокращения узла 5 равна c(2, 5) + r + r` = 0 + 28 + 0 = 28

Теперь мы найдем конечный узел с минимальными затратами. Узел 5 со стоимостью 28 является минимальным, поэтому мы выбираем узел 5 для дальнейшего исследования. Узел 5 можно расширить до узла 3, как показано на рисунке ниже:

Здесь мы будем использовать матрицу узла 5 со стоимостью 28, как показано ниже:

Рассмотрим путь от узла 5 к узлу 3. Сделайте пятую строку и третий столбец бесконечностью. Поскольку мы не можем вернуться от узла 3 к узлу 1, поэтому сделайте от 1 до 5 также бесконечность, как показано в приведенной ниже матрице:

Стоимость сокращения узла 3 равна c(5, 3) + r + r` = 0 + 28 + 0 = 28.

Наконец, мы проходим все узлы. Верхнее значение обновляется с бесконечности до 28. Мы проверим, имеет ли какой-либо конечный узел значение меньше 28. Поскольку ни один конечный узел не содержит значение меньше 28, мы отбрасываем все конечные узлы из дерева, как показано ниже:

Путь тура будет 1->4->2->5->3.

Следующая тема#

← предыдущая следующий →

Задача коммивояжера — решение с помощью метода «Ветви и границы»

Задача коммивояжера — что это такое?

Задача коммивояжера (TSP) — интересная задача. Задача определяется как «данные n городов и расстояние между каждой парой городов, найти путь, который посещает каждый город ровно один раз и возвращается в исходный город, с ограничением минимизации расстояния пути».
TSP имеет множество практических применений. Он используется при проектировании сетей и при проектировании транспортных маршрутов. Цель – сократить расстояние до минимума. Мы можем начать тур с любого случайного города и посетить другие города в любом порядке. С n городами, n! возможны разные перестановки. Изучение всех путей с использованием атак грубой силы может оказаться бесполезным в реальных приложениях.

Ветвь и граница — это эффективный способ найти лучшее, если не лучшее, решение за короткое время путем обрезки некоторых ненужных ветвей дерева поиска.
Работает следующим образом:

Рассмотрим ориентированный взвешенный граф G = (V, E, W), где узел представляет города, а взвешенные ориентированные ребра представляют направление и расстояние между двумя городами.

1. Первоначально, график представлен матрицей затрат C, где

C _IJ = стоимость края, если есть прямой путь от города I до города J

C _IJ = ∞, если есть нет прямого пути из города i в город j.

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

3. Найти стоимость уменьшенной матрицы. Стоимость определяется путем суммирования вычитаемой суммы из матрицы затрат для преобразования ее в матрицу сокращения.

4. Подготовьте дерево пространства состояний для матрицы сокращения

5. Найдите узел A с наименьшей стоимостью (т. е. E-узел), вычислив матрицу узлов уменьшенной стоимости с каждым оставшимся узлом.

6. Если ребро должно быть включено, выполните следующие действия:

(a) Установите для всех значений в строке i и всех значений в столбце j таблицы A значение ∞

(b) Установите A[j , 1] = ∞

7. Вычислите стоимость вновь созданной уменьшенной матрицы, как

8. Если не все узлы посещены, перейдите к шагу 4.

Процедура редукции описана ниже:

Исходная редукция:

Матрица M называется редуцированной матрицей, если каждая ее строка и столбец содержат хотя бы один нулевой элемент или вся строка или весь столбец имеют значение ∞. Пусть M представляет матрицу расстояний 5 городов. M можно сократить следующим образом:

M _RowRed = {M _ij – min {M _ij | 1 ≤ j ≤ n и M _ij < ∞ }}

Рассмотрим следующую матрицу расстояний:

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

Сокращенная матрица будет:

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

Стоимость сокращения строки (M) = 10 + 2 + 2 + 3 + 4 = 21

Сокращение столбца:

Matrix M _RowRed сокращаются строки, но не столбцы. Матрица называется редуцированной по столбцам, если в каждом ее столбце есть хотя бы один нулевой элемент или все ∞ элементы.

M _ColRed = {M _ji – min {M _ji | 1 ≤ j ≤ n, а M _ji < ∞ }}

Для приведенной выше матрицы найдем минимальный элемент из каждого столбца и вычтем его из каждой ячейки матрицы.

Сокращенная матрица столбцов M _ColRed будет выглядеть так:

В каждой строке и столбце M _ColRed есть хотя бы один нулевой элемент, поэтому эта матрица является сокращенной матрицей.

Стоимость уменьшения столбца (M) = 1 + 0 + 3 + 0 + 0 = 4

Дерево пространства состояний для задачи 5 городов изображено на рис. 6.6.1. Число внутри круга указывает порядок, в котором генерируется узел, а число ребер указывает посещаемый город.

Пример

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

Решение:

Процедура динамического сокращения следующая:
Нарисуйте дерево пространства состояний с оптимальной стоимостью сокращения в корневом узле.
Получите стоимость пути от узла i к узлу j, установив для всех записей в строке i ^th и столбце j ^th значение ∞.

Задать M[j][i] = ∞

Стоимость соответствующего узла N для пути от i до j равна сумме оптимальной стоимости + стоимости сокращения + M[j][i]
После исследования всех узлов на уровне i установите узел с минимальной стоимостью в качестве узла E и повторяйте процедуру, пока не будут посещены все узлы.
Данная матрица не уменьшена. Чтобы найти ее сокращенную матрицу, мы сначала найдем сокращенную матрицу строк, а затем, если необходимо, уменьшенную матрицу столбцов. Мы можем найти уменьшенную по строкам матрицу, вычитая минимальный элемент каждой строки из каждого элемента соответствующей строки. Процедура описана ниже: 9{‘} \] не редуцированная матрица. Уменьшите его, вычитая минимальное значение из соответствующего столбца. Делая это, мы получаем,
Стоимость M ₁ = C(1)
=   Стоимость сокращения строки + Стоимость сокращения столбца
=   (10 + 2 + 2 + 3 + 4) + (1 + 3) = 25
Это означает, что все туры в графе имеют длину не менее 25. Это оптимальная стоимость пути.
Дерево пространства состояний
Найдем стоимость ребра от узла 1 до узла 2, 3, 4, 5.
Выбрать ребро 1-2:
Set M ₁ [1] [ ] = M ₁ [ ] [2] = ∞
Set M ₁ [2] [1] = ∞
При необходимости сократите полученную матрицу.
M ₂ уже уменьшен.
Стоимость узла 2 :
C(2) = C(1) + Снижение стоимости + M ₁ [1] [2]
= 25 + 0 + 10 = 35
Выберите ребро 1-3
Набор M ₁ [1][ ] = M ₁ [ ] [3] = ∞
Набор M ₁ [3][1] = ∞
При необходимости сократите результирующую матрицу.
Стоимость узла 3:
C(3) = C(1) + Стоимость уменьшения + M ₁ [1] [3]
= 25 + 11 + 17 = 53
Выберите ребро 1-4 :
Установить M ₁ [1][ ] = M ₁ [ ][4] = ∞
Установить M ₁ [4][1] = ∞
. При необходимости уменьшить полученную матрицу.
Matrix M ₄ уже уменьшен.
Стоимость узла 4:
C(4) = C(1) + Снижение стоимости + M ₁ [1] [4]
= 25 + 0 + 0 = 25
Выбрать кромку 1-5 :
Установить M ₁ [1] [ ] = M ₁ [ ] [5] = ∞
Установите M ₁ [5] [1] = ∞
При необходимости сократите полученную матрицу.
Стоимость узла 5:
C(5) = C(1) + стоимость уменьшения + M ₁ [1] [5]
= 25 + 5 + 1 = 31
Диаграмма пространства состояний:
Узел 4 имеет минимальную стоимость пути 1-4. Мы можем перейти к вершине 2, 3 или 5. Давайте исследуем все три вершины.
Выбрать путь 1-4-2 : (Добавить ребро 4-2)
Установить M ₄ [1] []   =   M ₄ [4] [] = M ₄ [] [2 ] = ∞
Установить M ₄ [2] [1]   =   ∞
При необходимости уменьшить полученную матрицу.
Matrix M ₆ уже уменьшен.
Стоимость узла 6:
C(6) = C(4) + Стоимость уменьшения + M ₄ [4] [2]
= 25 + 0 + 3 = 28
Выберите ребро 4-3 (Путь 1-4-3) : 9{‘} \] не сокращается. Уменьшите его, вычитая 11 из столбца 1.
Стоимость узла 7:
C(7) = C(4) + Стоимость уменьшения + M ₄ [4] [3]
=   25 + 2 + 11 + 12 = 50
Выберите ребро 4-5 (Путь 1-4-5):
Матрица M ₈ уменьшается.
Стоимость узла 8:
C(8) = C(4) + Стоимость сокращения + M ₄ [4][5]
=   25 + 11 + 0 = 36
Дерево пространства состояний
6
Путь 1-4-2 ведет к минимальной стоимости. Найдем стоимость двух возможных путей.
Добавить ребро 2-3 (путь 1-4-2-3):
Set M ₆ [1][ ]   =   M ₆ [4][ ] = M ₆ [2] [ ]
=   M ₆ [][3] = ∞
Установить M ₆ [3][1]   =   ∞
При необходимости уменьшить результирующую матрицу.
Стоимость узла 9:
C(9) = C(6) + Стоимость уменьшения + M ₆ [2][3]
= 28 + 11 + 2 + 11 = 52
Добавить ребро 2 -5 (Путь 1-4-2-5) :
Набор M ₆ [1][ ] = M ₆ [4][ ] = M ₆ [2][ ] = M ₆ [ ][5] = ∞
Набор M ₆ [5] [1] = ∞
Уменьшить результирующую матрицу, если требуется.
Стоимость узла 10:
C(10) = C(6) + Стоимость уменьшения + M ₆ [2][5]
= 28 + 0 + 0 = 28
Дерево пространства состояний
Добавить ребро 5-3 (Путь 1-4-2-5-3):
Стоимость узла 11:
C(11) = C(10) + Стоимость сокращения + M ₁₀ [5][3]
= 28 + 0 + 0 = 28
Пространственное дерево состояний:
- Статическое пространственное дерево — это m-арное дерево. В динамическом дереве пространства состояний левая и правая ветви указывают на включение и исключение ребра соответственно. Вычисление ограничивающей функции такое же, как и в предыдущем методе. Динамическое дерево пространства состояний является бинарным деревом. В каждом узле левая ветвь (i, j) указывает все пути, включая ребро (i, j). Правая ветвь (i, j) указывает на все пути, кроме (i, j).
- На каждом уровне мы выбираем ребро, которое дает наибольшую вероятность минимальной стоимости тура. Это можно сделать, выбрав правый край, который дает наибольшее значение. Мы можем найти такое ребро из матрицы приведенных затрат. Рассмотрим следующий пример TSP.
Матрица стоимости CСокращенная матрица M с L = 25
- Сокращенная матрица вычисляется так же, как и в предыдущем случае. Стоимость сокращения матрицы равна 25. Отсюда следует, что любой маршрут графа стоит не менее 25. Таким образом, корень дерева имеет стоимость 25. Мы выберем следующее ребро так, чтобы его исключение приводило к максимуму. Другими словами, выберите ребро, которое дает максимальную вероятность минимальной стоимости пути при включении этого ребра.
- Этого можно добиться, рассмотрев одно из ребер с уменьшенной нулевой стоимостью в сокращенной матрице. В
  рис. 6.6.2(b) края <1, 4>, <2, 5>, <3, 1>, <3, 4>, <4, 5>, <5, 2> и <5, 3> имеет 0 стоимости уменьшения. Если мы выберем любое ребро из этого списка, то результирующая матрица затрат M будет иметь запись ∞ на позиции M[a][b].
- Если мы включим ребро <1, 4>, установим M[1][4] = ∞ и уменьшим M. Это делается путем вычитания 1 из строки 1. Таким образом, стоимость правого потомка увеличится на 1.
- Если мы включим ребро <2, 5>, установим M[2][5] = ∞ и уменьшим M. Это делается путем вычитания 2 из строки 2. Таким образом, стоимость правого потомка увеличится на 1.
- Если мы включим ребро <3, 1>, установим M[3][1] = ∞ и уменьшим M. Это делается путем вычитания 11 из столбца 1. Таким образом, стоимость правого потомка увеличится на 11.
Таким образом у нас будет,
Край <1, 4> <2, 5> <3, 1> <3, 4> <4, 5> <5, 2> <5, 3>
Увеличение \[ шляпа {c} \] правого потомка 1 2 11 0 3 3 11
Здесь ребро <3, 1> и <5, 3> максимизирует стоимость правого потомка, поэтому мы можем выбрать любое из них. Выделим ребро <3, 1>.
Стоимость матрицы M ₂ = Стоимость узла 2, C(2)
= C(1) + L + M[3][1] = 25 + 0 + 0 = 25
Исключая <3, 1>, получаем
Стоимость матрицы M ₃ = Стоимость узла 3,
C(3) = C(1) + L + M[3][1] = 25 + 11 + 0 = 36
На этом этапе дерево пространства динамических состояний будет выглядеть так:
При включении <3, 1>, получаем матрицу M ₂ . В M ₂ у нас есть ребра <1, 4>, <2, 5>, <4, 5>, <5, 2> и <5, 3> со значением 0. Таким образом, выбор любого ребра из этого списка сделает M ₂ [а][б] = ∞. Повторяя предыдущий шаг, получаем
Edge <1, 4> <2, 5> <4, 5> <5, 2> <5, 3>
Увеличение \[ шляпа {c} \] правого потомка 3 2 3 3 11
Здесь ребро <5, 3> максимизирует правого потомка, поэтому давайте выберем ребро <5, 3>.
Стоимость матрицы M ₄ = Стоимость узла 4,
C(4) = C(2) + L + M ₂ [5][3] = 25 + 3 + 0 = 28
By исключая <5, 3> получаем,
Стоимость матрицы M ₅ = Стоимость узла 5,
C(5) = C(2) + L + M ₂ [5][3] = 25 + 11 + 0 = 36
В этот момент динамическое дерево пространства состояний будет выглядеть так:
При включении <5, 3> мы получим матрицу M ₄ . В M ₄ у нас есть ребра <1, 4>, <2, 5>, <4, 2> и <4, 5> со значением 0. Таким образом, выбор любого ребра из этого списка сделает M ₄ [а][б] = ∞. Повторяя предыдущий шаг, получаем
Edge <1, 4> <2, 5> <4, 2> <4, 5>
Увеличение \[ шляпа {c} \] правого потомка 9 2 7 0
Здесь ребро <1, 4> максимизирует правого потомка, поэтому давайте выберем ребро <1, 4>.
No related posts.