(5х5) (Засчитывается за 4 условные задачи) время на исполнение 2 пары) (Презентация КОММИВОЯЖЁР) Самая сложная задача исследования операций
Методом ветвей и границ требуется найти Кратчайший маршрут объезда 5 городов с возвратом в исходный, при КОТОРОМ КАЖДЫЙ ГОРОД ПОСЕЩАЕТСЯ в ТОЧНОСТИ 1 раз (в матрице даны цены проезда из «левого» города в «верхний»).
Решение Методом ветвей и границ
Шаг №0 Оцениваем цикл 1-2-3-4-5-1 – это первое приближение верхней оценки. Далее, если на любой ветви дерева ветвления нижняя оценка подмножества решений окажется выше верхней эта ветвь «отмирает» , т.к. все её решения хуже уже имеющегося.
Шаг №1а) Выписываем константы редуцирования по строкам. Это минимальные числа в строках. Их надо вычесть из элементов своих строк (при этом появится не менее одного нуля в каждой строке).
Шаг №1б) В только что полученной на шаге 1а) матрице (с нулями в строках) ровно ту же операцию проводи и по столбцам - ищем столбцы, где минимум е равен 0 и вычитаем его. В формате самопроверки убедитесь, что теперь в каждом столбце и каждой строке матрицы стоимостей проезда имеется хотя бы один ноль.
Шаг №1в) Вычисляем сумму констант
редуцирования полученных на шагах а)
и б). Очевидно, никакой маршрут не может
стоить дешевле – поэтому это оценка
снизу. Далее мы будем увеличивать эту
оценку на величину
и
(эти величины опишем ниже), где
- пара индексов ребра, по которому
выбрано производить ветвление.
Опишем, как будет происходить ветвление: выбираем ребро i,j(удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).
Теоретически можно производить ветвление по любому ребру, но наша задача в том, чтобы на одном множестве нижняя оценка цены маршрута не изменилась, а на другом максимально выросла – это может способствовать тому, что в большинстве случаев комбинаторный перебор, вообще говоря, экспоненциального алгоритма решения NPполной задачи окажется не слишком большой.
Для этого: Шаг №2. Вычисляем стоимости
обхода для каждого нулевого элемента
(если он превратился в бесконечность
∞)
- величина на которую увеличиваются
константы редуцирования соответствующей
строки и столбца.
Разбиваем текущее множество решений на два:
Процесс отчасти заканчивается после выбора 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 (правая ветвь).
В нашем случае полученный вариант оказался лучше всех нижних оценок по другим ветвям.
Ответ:
.
Проверка
Презентация КОММИВОЯЖЁР.
Задача проверяется преподавателем по оформлению дерева ветвления. Чтобы на нём была представлена максимально полная необходимая для проверки информация в вершинах дерева отобразить нижние оценки целевых функций, на рёбрах дерева обязательно должны быть отображены все θ (рост суммы констант редуцирования на правом повороте), все ΔZ(рост суммы констант редуцирования при левом повороте). При левом повороте выбирается одно обязательное ребро (отмечается на дереве ветвления) и добавляется одно запрещённое ребро. Для объяснения его выбора рядом с деревом ветвления на соответствующем уровне должна быть изображена цепочка в которой запрещаемое ребро вкупе с ранее выбранными (включая сейчас выбранное) порождает цикл не проходящий через все рёбра (так называемое «короткое замыкание» цикла).
В ответе дается цепочка Рёбер вида (1,k)(k,l)(l,m)..(r,1)(по размеру задачи), стоимость маршрута состоит из начальной нижней оценки и её приращений ΔZ(если были только ВЫЧЁРКИВАНИЯ – левые ПОВОРОТЫ) и – что бывает очень редко - ΔZи θ, если КРОМЕ левых ПОВОРОТОВ присутствовали один или несколько правых поворотов. Провести проверку стоимости ПОЛУЧЕНОГО решения по исходной матрице, объяснить причины несовпадения – если имелись (не совпадений быть не должно).
Здравствуй! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию, предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:
Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.
Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.
Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.
Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.
Исправленный алгоритм, для нахождения действительно минимального маршрута
1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)
1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.
а) Ищем все нулевые элементы в приведенной матрице
б) Для каждого из них считаем его штраф за неиспользование.
в) Выбираем элементы, которым соответствует максимальный штраф
2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w i) и не содержащие эти ребра(S w i /o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множеств S w i /o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h i ,k i), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h i ,k i)
б) При вычислении затрат для множества S w i примем во внимание, что раз ребро (h i i,k i) входит в маршрут, то значит ребро (k i ,h i) в маршрут входить не может, поэтому в матрице затрат пишем c(k i ,h i)=infinity, а так как из пункта h i мы «уже ушли», а в пункт k i мы «уже пришли», то ни одно ребро, выходящее из h i , и ни одно ребро, приходящее в k i , уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h i и столбец k i . После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h i ,k i), где r(h i ,k i) - сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.
Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.
Небольшая оптимизация - подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h i ,k i) или нет, и вешаем двух и более детей - Sw(h i ,k i) и Sw/o(h i ,k i). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
Причина у этих ошибок одна - игнорирование возможности появления нескольких нулевых элементов с максимальным штрафом. В таком случае надо делить не на два подмножества, а на большее количество (2n). А также следует выбирать для разбиения множество с минимальной границей из всех возможных путей, а не из двух полученных в результате последнего разбиения детей.
Вернемся к картинке в начале поста:
А вот решение с исправленным алгоритмом.
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «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 .
Применение задачи коммивояжера на практике довольно обширно. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу - в задаче минимизации, сверху - в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
Таблица 2
Таблица 3
Таблица 4
Изложим алгоритм Литтла на примере 1 предыдущего раздела. Повторно запишем матрицу:
Нам будет удобнее трактовать С ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.
Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.
Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. табл. 3), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам, см. табл. 4).
Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.
Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.
Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.
Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).
Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса - включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.
Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.
Таблица 5
Таблица 7
Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т.к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис. 6.
Кружки представляют классы: верхний кружок - класс всех туров; нижний левый - класс всех туров, включающих ребро (1,2); нижний правый - класс всех туров, не включающих ребро (1,2). Числа над кружками - оценки снизу.
Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C еще строку 3 и столбец 1, получив матрицу C[(1,2), (3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. , и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.
Таблица 9
Таблица 11
Оцениваем теперь нули в приведенной матрице C[(1,2), (3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис. 8).
Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.
В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.
Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С , т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.
Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.
Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.
ЭММиМвЛ, ИСО, МПУР
ЗАДАЧА КОММИВОЯЖЕРА
Определения
Графом
называется непустое конечное множество,
состоящее из двух подмножеств
и
.
Первое подмножество
(вершины) состоит из любого множества
элементов. Второе подмножество
(дуги) состоит из упорядоченных пар
элементов первого подмножества
.
Если вершины
и
такие, что
,
то это вершины смежные.
Маршрутом в графе
называется последовательность вершин
не обязательно попарно различных, где
для любого
смежно с
.
Маршрут называется цепью, если все его
ребра попарно различны. Если
то маршрут называется замкнутым.
Замкнутая цепь называется циклом.
Постановка задачи
Коммивояжер должен объездить 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
),
а другое подмножество
не содержало этой дуги. Для каждого из
подмножеств определяются нижние границы
по тому же правилу, что и для первоначального
множества маршрутов. Полученные нижние
границы подмножеств
и
оказываются не меньше нижней границы
множества всех маршрутов, т.е.
.
Сравнивая нижние границы
φ
(
)
иφ
(
),
можно выделить то, подмножество маршрутов,
которое с большей вероятностью содержит
маршрут минимальной длины.
Затем одно из подмножеств
или
по аналогичному правилу разбивается
на два новых
и
.
Для них снова отыскиваются нижние
границыφ
(
),
и φ
(
)
и т.д. Процесс ветвления продолжается
до тех пор, пока не отыщется единственный
маршрут. Его называютпервым
рекордом
. Затем
просматривают оборванные ветви. Если
их нижние границы больше длины первого
рекорда, то задача решена. Если же есть
такие, для которых нижние границы меньше,
чем длина первого рекорда, то подмножество
с наименьшей нижней границей подвергается
дальнейшему ветвлению, пока не убеждаются,
что оно не содержит лучшего маршрута
.
Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины маршрута. Его называют вторым рекордом . Процесс решения заканчивается, когда будут проанализированы все подмножества.
Основная идея метода ветвей и границ состоит в том, что ветвятся не все вершины. Сначала вершины просматриваются, и каждая вершина оценивается. Ветвится та вершина, которая получает лучшую оценку.
Каждой вершине соответствует
множество вариантов решений. Каждому
варианту решения
соответствует определенное значение
критерия эффективности
.
Лучшее из этих значений (минимальное
или максимальное) удобно взять в качестве
оценки вершины. Однако подсчитать точное
значение
критерия, не перебрав всех вариантов,
невозможно. Поэтому используется не
точное значение
критерия, а его оценка снизу (в случае
минимизации) или сверху (в случае
максимизации). Оценка снизу – это оценка
нижней границы множества вариантов,
оценка сверху – это оценка верхней
границы множества вариантов.
Оценка вершины должна удовлетворять следующим свойствам.
Алгоритм метода ветвей и границ
Шаг 1 . Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка нижней (верхней) границы. Ветвится вершина, которой соответствует лучшая (минимальная или максимальная) оценка.
Шаг 2
.
Для всех вершин
-го
уровня (
)
подсчитывается оценка. Ветвится та из
висячих вершин уровня
,
которой соответствует лучшая (минимальная
или максимальная) оценка.
Шаг 3
.
Действия шага 2 повторяются до тех пор,
пока не будет получено точное решение
на последнем уровне. Для него подсчитывается
точное значение
.
Если это значение не хуже оценок
оставшихся висячих вершин, то найдено
оптимальное решение. Если это значение
строго лучше, то оптимальное решение
единственно. Если значение функции
для вершин последнего уровня не лучше
значения оценок оставшихся висячих
вершин, то переходят на шаг 2.
Метод ветвей и границ не гарантирует того, что в ходе решения задачи не будет произведен полный перебор.
Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).
Для того чтобы найти нижнюю границу воспользуемся следующим соображением: если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любого маршрута коммивояжера изменится на данную величину.
Вычтем из каждой строки число, равное минимальному элементу этой строки. Вычтем из каждого столбца число, равное минимальному элементу этого столбца. Полученная матрица называется приведенной по строкам и столбцам. Сумма всех вычтенных чисел называется константой приведения .
Константу приведения следует выбирать в качестве нижней границы длины маршрутов.
Разбиение множества маршрутов на подмножества
Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.
Для получения платежной матрицы маршрутов, включающей дугу (i , j ) вычеркиваем в матрице строку i и столбец j , а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку на бесконечность.
Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.
Пример (Г.И. Просветов, 2009, стр. 44)
Решим задачу коммивояжера для пяти пунктов.
Расстояния между населенными пунктами заданы с помощью матрицы
,
где
- длина пути от пунктаi
до пункта j
.
На каждом шаге ребро
либо включается в ответ (обозначение
),
либо не включается в ответ (обозначение
).
Шаг 1. Нахождение константы приведения .
Находим минимальный элемент в каждой строке и вычитаем его из всех элементов этой строки. В полученной матрице находим минимальный элемент в каждом столбце и вычитаем его из каждого элемента соответствующего столбца.
Найденные минимумы в строке и столбце называются константами приведения строки или столбца соответственно. Сумма всех найденных минимумов равна 18 – константа приведения матрицы. Она дает оценку снизу на данном шаге длины маршрута.
Шаг 2 . Определение дуги, исключение которой максимально увеличивает оценку, полученную на предыдущем шаге.
С этой целью заменяем
поочередно каждый из нулей на
.
Элемент
имеет наибольшую сумму. Поэтому все
множество маршрутов распадается на два
класса:
(не содержат дугу
)
и
(содержат дугу
).
Шаг 3 . Определение множества дуг для дальнейшего ветвления.
Рассмотрим множество
.
Исключение дуги
на
:
.
В полученной матрице нужно определить сумму констант приведения:
Нижняя граница множества
,
где 18 – оценка предыдущего шага, 3 –
оценка текущего шага.
Рассмотрим множество
.
Включение дуги
проводится с помощью исключения 1-й
строки (в множестве
из пункта 1 мы идем только в пункт 3) и
3-го столбца (в множестве
в пункт 3 мы можем попасть только из
пункта 1). Элемент (3,1) заменяем на
(исключаем возможность возвращения,
зацикливания, образования негамильтонова
цикла):
.
Нижняя граница множества , где 18 – оценка предыдущего шага, 1 – оценка текущего шага. Числа над матрицей суть номера столбцов, числа перед матрицей – номера строк.
Так как
,
то дальше ветвим множество
.
Для матрицы
определим дугу, исключение которой
максимально увеличило бы полученную
оценку
.
Для этого заменяем поочередно каждый
из нулей на
и вычисляем сумму наименьших элементов
в строке и столбце, содержащих этот
новый элемент
:
Для элемента
эта сумма наибольшая. Поэтому все
множество маршрутов распадается на два
класса:
(не содержит дугу
)
и
(содержит дугу
).
Рассмотрим множество
.
Исключение дуги
проводится с помощью замены элемента
на
:
.
Определим в полученной матрице ее константу приведения:
.
