Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.
Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ .
Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):
Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.
В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».
Итак, методика решения задачи коммивояжера:
1. Построение матрицы с исходными данными
Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:
В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).
Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.
2. Нахождение минимума по строкам
Находим минимальное значение в каждой строке (di ) и выписываем его в отдельный столбец.
3. Редукция строк
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
В итоге в каждой строке будет хотя бы одна нулевая клетка .
4. Нахождение минимума по столбцам
5. Редукция столбцов
Вычитаем из каждого элемента матрицы соответствующее ему dj.
В итоге в каждом столбце будет хотя бы одна нулевая клетка .
6. Вычисление оценок нулевых клеток
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку ». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
И так по всем нулевым клеткам:
7. Редукция матрицы
Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).
Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути , ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9
Если мы еще не нашли все отрезки пути, то возвращаемся ко 2 -му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.
Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .
9. Вычисление итоговой длины пути и построение маршрута
Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.
В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .
Общая длина пути: L = 30 .
Применение задачи коммивояжера на практике довольно обширно. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию , предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:
Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.
Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.
Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.
Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.
Исправленный алгоритм, для нахождения действительно минимального маршрута
А) Ищем все нулевые элементы в приведенной матрице
б) Для каждого из них считаем его штраф за неиспользование.
в) Выбираем элемент, которому соответствует максимальный штраф (любой, если их несколько)
2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w) и не содержащие это ребро(S w/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества S w/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества S w примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h,k), где r(h,k) - сумма констант приведения для измененной матрицы затрат.
4. Из всех
неразбитых множеств выбирается то, которое имеет наименьшую оценку.
Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.
Небольшая оптимизация - подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей - Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
Вернемся к картинке в начале поста:
Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать
График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:
График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.
Попробовать с подробным решением можно
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | M | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | M | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | M | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | M | 20 |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| d j | 0 | 10 | 0 | 0 | 0 |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 40 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 0 | M | 40 | 0 |
| 4 | 0 | 50 | 10 | M | 40 |
| 5 | 0 | 10 | 30 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | M | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | M | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | M | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | M | 0 |
| d j | 0 | 10 | 10 | 0 | 30 | 0 |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | M | 60 | 40 |
| 2 | 20 | M | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | M | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | M | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 0 | 40 |
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | 0 | 0 |
| 4 | M | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 10 |
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | M | 0(30) | 0 |
| 4 | M | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | M | 10 |
| d j | 20 | 10 | 0 | 30 | 0 |
| i j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | M | 0 |
| 4 | M | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 30 | 30 |
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 40 | 0 | 0 |
| 5 | 0 | 10 | M | 0 |
| d j | 0 | 10 | 0 | 10 |
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0(20) | 20 |
| 4 | M | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | M | 0 |
| d j | 20 | 30 | 0 | 0 |
| i j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 30 | 0 | 0 |
| 5 | 0 | M | M | 0 |
| d j | 0 | 30 | 0 | 30 |
| i j | 1 | 3 | d i |
| 2 | 20 | 0 | 0 |
| 4 | M | 0 | 0 |
| d j | 20 | 0 | 20 |
В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений.
Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .
U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n
Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей
| 1 | 2 | 3 | 4 | |
| 1 | - | 5 | 8 | 7 |
| 2 | 5 | - | 6 | 15 |
| 3 | 8 | 6 | - | 10 |
| 4 | 7 | 15 | 10 | - |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 20 | 18 | 12 | 8 | 8 |
| 2 | 5 | M | 14 | 7 | 11 | 5 |
| 3 | 12 | 18 | M | 6 | 11 | 6 |
| 4 | 11 | 17 | 11 | M | 12 | 11 |
| 5 | 5 | 5 | 5 | 5 | M | 5 |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 12 | 10 | 4 | 0 |
| 2 | 0 | M | 9 | 2 | 6 |
| 3 | 6 | 12 | M | 0 | 5 |
| 4 | 0 | 6 | 0 | M | 1 |
| 5 | 0 | 0 | 0 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 12 | 10 | 4 | 0 |
| 2 | 0 | M | 9 | 2 | 6 |
| 3 | 6 | 12 | M | 0 | 5 |
| 4 | 0 | 6 | 0 | M | 1 |
| 5 | 0 | 0 | 0 | 0 | M |
| d j | 0 | 0 | 0 | 0 | 0 |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 12 | 10 | 4 | 0 |
| 2 | 0 | M | 9 | 2 | 6 |
| 3 | 6 | 12 | M | 0 | 5 |
| 4 | 0 | 6 | 0 | M | 1 |
| 5 | 0 | 0 | 0 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 12 | 10 | 4 | 0(5) | 4 |
| 2 | 0(2) | M | 9 | 2 | 6 | 2 |
| 3 | 6 | 12 | M | 0(5) | 5 | 5 |
| 4 | 0(0) | 6 | 0(0) | M | 1 | 0 |
| 5 | 0(0) | 0(6) | 0(0) | 0(0) | M | 0 |
| d j | 0 | 6 | 0 | 0 | 1 | 0 |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 12 | 10 | 4 | 0 | 0 |
| 2 | 0 | M | 9 | 2 | 6 | 0 |
| 3 | 6 | 12 | M | 0 | 5 | 0 |
| 4 | 0 | 6 | 0 | M | 1 | 0 |
| 5 | 0 | M | 0 | 0 | M | 0 |
| d j | 0 | 6 | 0 | 0 | 0 | 6 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | 0 | 0 |
| 2 | 0 | 9 | 2 | M | 0 |
| 3 | 6 | M | 0 | 5 | 0 |
| 4 | 0 | 0 | M | 1 | 0 |
| d j | 0 | 0 | 0 | 0 | 0 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | 0(5) | 4 |
| 2 | 0(2) | 9 | 2 | M | 2 |
| 3 | 6 | M | 0(7) | 5 | 5 |
| 4 | 0(0) | 0(9) | M | 1 | 0 |
| d j | 0 | 9 | 2 | 1 | 0 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | 0 | 0 |
| 2 | 0 | 9 | 2 | M | 0 |
| 3 | 6 | M | 0 | 5 | 0 |
| 4 | 0 | M | M | 1 | 0 |
| d j | 0 | 9 | 0 | 0 | 9 |
| i j | 1 | 4 | 5 | d i |
| 1 | M | 4 | 0 | 0 |
| 2 | 0 | 2 | M | 0 |
| 3 | 6 | M | 5 | 5 |
| d j | 0 | 2 | 0 | 7 |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 12 | 10 | 4 | 0 |
| 2 | 0 | M | 9 | 2 | 6 |
| 3 | 6 | 12 | M | 0 | 5 |
| 4 | 0 | 6 | 0 | M | 1 |
| 5 | 0 | M | 0 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 6 | 10 | 4 | 0 |
| 2 | 0 | M | 9 | 2 | 6 |
| 3 | 6 | 6 | M | 0 | 5 |
| 4 | 0 | 0 | 0 | M | 1 |
| 5 | 0 | M | 0 | 0 | M |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 6 | 10 | 4 | 0(5) | 4 |
| 2 | 0(2) | M | 9 | 2 | 6 | 2 |
| 3 | 6 | 6 | M | 0(5) | 5 | 5 |
| 4 | 0(0) | 0(6) | 0(0) | M | 1 | 0 |
| 5 | 0(0) | M | 0(0) | 0(0) | M | 0 |
| d j | 0 | 6 | 0 | 0 | 1 | 0 |
| i j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 6 | 10 | 4 | 0 | 0 |
| 2 | 0 | M | 9 | 2 | 6 | 0 |
| 3 | 6 | 6 | M | 0 | 5 | 0 |
| 4 | 0 | M | 0 | M | 1 | 0 |
| 5 | 0 | M | 0 | 0 | M | 0 |
| d j | 0 | 6 | 0 | 0 | 0 | 6 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | 0 | 0 |
| 2 | 0 | 9 | M | 6 | 0 |
| 3 | 6 | M | 0 | 5 | 0 |
| 5 | 0 | 0 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 0 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | 0(9) | 4 |
| 2 | 0(6) | 9 | M | 6 | 6 |
| 3 | 6 | M | 0(5) | 5 | 5 |
| 5 | 0(0) | 0(9) | 0(0) | M | 0 |
| d j | 0 | 9 | 0 | 5 | 0 |
| i j | 1 | 3 | 4 | 5 | d i |
| 1 | M | 10 | 4 | M | 4 |
| 2 | 0 | 9 | M | 6 | 0 |
| 3 | 6 | M | 0 | 5 | 0 |
| 5 | 0 | 0 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 5 | 9 |
| i j | 1 | 3 | 4 | d i |
| 2 | 0 | 9 | M | 0 |
| 3 | 6 | M | 0 | 0 |
| 5 | M | 0 | 0 | 0 |
| d j | 0 | 0 | 0 | 0 |
| i j | 1 | 3 | 4 | d i |
| 2 | 0(15) | 9 | M | 9 |
| 3 | 6 | M | 0(6) | 6 |
| 5 | M | 0(9) | 0(0) | 0 |
| d j | 6 | 9 | 0 | 0 |
| i j | 1 | 3 | 4 | d i |
| 2 | M | 9 | M | 9 |
| 3 | 6 | M | 0 | 0 |
| 5 | M | 0 | 0 | 0 |
| d j | 6 | 0 | 0 | 15 |
| i j | 3 | 4 | d i |
| 3 | M | 0 | 0 |
| 5 | 0 | 0 | 0 |
| d j | 0 | 0 | 0 |
Дерево решений.
| 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (5*,2*), H=41 | (5,2) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (4*,2*), H=47 | (4,2) | (4*,3*), H=44 | (4,3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (1*,5*), H=50 | (1,5) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (2*,1*), H=56 | (2,1) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (3,4) | (3*,4*), H=41 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (5,3) | (5*,3*), H=41 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Определения
Графом
называется непустое конечное множество,
состоящее из двух подмножеств
и
.
Первое подмножество
(вершины) состоит из любого множества
элементов. Второе подмножество
(дуги) состоит из упорядоченных пар
элементов первого подмножества
.
Если вершины
и
такие, что
,
то это вершины смежные.
Маршрутом в графе
называется последовательность вершин
не обязательно попарно различных, где
для любого
смежно с
.
Маршрут называется цепью, если все его
ребра попарно различны. Если
то маршрут называется замкнутым.
Замкнутая цепь называется циклом.
Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.
В терминах теории
графов задачу можно сформулировать
следующим образом. Задано n
вершин и матрица {c
ij },
где c
ij
≥0 – длинна (или цена) дуги (i
,
j
),
.
Под маршрутом
коммивояжера
z
будем понимать цикл i
1 ,
i
2 ,…,
i
n ,
i
1
точек
1,2,…, n.
Таким образом, маршрут
является набором дуг. Если между городами
i
и j
нет перехода, то в матрице ставится
символ «бесконечность». Он обязательно
ставится по диагонали, что означает
запрет на возвращение в точку, через
которую уже проходил маршрут
коммивояжера
,
длина маршрута l
(z
)
равна сумме длин дуг, входящих в маршрут.
Пусть Z
– множество всех возможных маршрутов.
Начальная вершина i
1
– фиксирована. Требуется найти маршрут
z 0
Z
,
такой, что l
(z
0)=
min
l
(z
),
z
Z
.
Основная идея метода
ветвей и границ состоит в том, что вначале
строят нижнюю границу φ длин множества
маршрутов Z. Затем множество маршрутов
разбивается на два подмножества таким
образом, чтобы первое подмножество
состояло из маршрутов, содержащих
некоторую дугу (i, j), а другое подмножество
не содержало этой дуги. Для каждого из
подмножеств определяются нижние границы
по тому же правилу, что и для первоначального
множества маршрутов. Полученные нижние
границы подмножеств
и
оказываются не меньше нижней границы
множества всех маршрутов, т.е. φ(Z)≤ φ
(),
φ(Z) ≤ φ ().
Сравнивая нижние границы φ () и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.
Затем одно из
подмножеств
или
по аналогичному правилу разбивается
на два новых
и
.
Для них снова отыскиваются нижние
границы φ
(),
и φ
()
и т.д. Процесс ветвления продолжается
до тех пор, пока не отыщется единственный
маршрут. Его называют первым рекордом.
Затем просматривают оборванные ветви.
Если их нижние границы больше длины
первого рекорда, то задача решена. Если
же есть такие, для которых нижние границы
меньше, чем длина первого рекорда, то
подмножество с наименьшей нижней
границей подвергается дальнейшему
ветвлению, пока не убеждаются, что оно
не содержит лучшего маршрута
.
Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины маршрута. Его называют вторым рекордом. Процесс решения заканчивается, когда будут проанализированы все подмножества.
Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).
Для того чтобы найти нижнюю границу воспользуемся следующим соображением: если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любого маршрутом коммивояжера изменится на данную величину.
Вычтем из каждой строки число, равное минимальному элементу этой строки. Вычтем из каждого столбца число, равное минимальному элементу этого столбца. Полученная матрица называется приведенной по строкам и столбцам. Сумма всех вычтенных чисел называется константой приведения.
Константу приведения следует выбирать в качестве нижней границы длины маршрутов.
Разбиение множества маршрутов на подмножества
Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.
Для получения платежной матрицы маршрутов, включающей дугу (i , j ) вычеркиваем в матрице строку i и столбец j , а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку на бесконечность.
Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.
Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:
Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).
Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.
После их вычитания по строкам получим:
Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .
После их вычитания по столбцам получим приведенную матрицу:
Найдем нижнюю границу φ (Z ) = 15+1+0+16+5+5+5 = 47.
Для выделения
претендентов на включение во множество
дуг, по которым производится ветвление,
найдем степени Θ ij
нулевых элементов этой матрицы (суммы
минимумов по строке и столбцу). Θ 14
= 10 + 0,
Θ 24
= 1 + 0, Θ 36
= 5+0, Θ 41
= 0 + 1, Θ 42
= 0 + 0, Θ 56
= 2 + 0, Θ 62
= 0 + 0,
Θ 63
= 0 + 9, Θ 65
= 0 + 2.
Наибольшая степень Θ 14
= 10.
Ветвление проводим по дуге (1, 4).
Нижняя граница для
множества
остается равной 47. Для всех маршрутов
множества
из города
A
мы не перемещаемся в город D.
В матрице это обозначается выставлением
в ячейку (1, 4) знака ∞. В этом случае выход
из города A добавляет к оценке нижней
границы по крайней мере наименьший
элемент первой строки. φ
()
= 47 + 10.
В матрице, соответствующей полагаем c 14 = ∞.
После проведения процедуры приведения с r 1 =10 получим новую нижнюю границу 57 + 10 = 67.
В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c 41 = ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c 1 ij }:
Для приведения надо
вычесть минимум по первому столбцу:
h 1 =1.
При этом нижняя граница станет равной
47+1 = 48. Сравнивая нижние границы
φ
()
= 67 и φ
()
= 48
,
которое с большей вероятностью содержит
маршрут минимальной длины.
Рис. 1 Ветвление на первом шаге
Далее продолжаем
процесс ветвления. Найдем степени Θ ij
нулевых элементов этой матрицы Θ 21
=16, Θ 36
= 5, Θ 42
= 2, Θ 56
= 2, Θ 62
= 0, Θ 63
=9, Θ 65
= 2.
Наибольшая степень Θ 21 .
Затем множество
разбивается дуге (2, 1) на два новых
и
.
В матрице для вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c 42 = ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.
Для приведения надо вычесть минимум по строке 4: r 4 =2. При этом нижняя граница станет равной 48+2 = 50.
Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ () = 64 и φ () = 50 .
Рис. 2 Ветвление на втором шаге
Приведенная платежная матрица для
Для приведения надо вычесть минимум по строке 3: r 3 =5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов.
Рис. 3 Ветвление на третьем шаге
Приведенная платежная матрица для
|
0 Шпаргалка >> Бухгалтерский учет и аудит Активности, влияния, участия в решении задачи . В различных ситуациях жизни... Специальные задачи математического программирования Специальные задачи математического программирования. Задача о коммивояжере .Метод ветвей и границ . Задача о коммивояжере Пусть... |
