Решение задач коммивояжёра, способов её решения - Реферат. Решение задачи коммивояжера
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.
Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ .
Общий план решения задачи коммивояжера
Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):
- Построение матрицы с исходными данными.
- Нахождение минимума по строкам.
- Редукция строк.
- Нахождение минимума по столбцам.
- Редукция столбцов.
- Вычисление оценок нулевых клеток.
- Редукция матрицы.
- Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
- Вычисление итоговой длины пути и построение маршрута.
Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.
Подробная методика решения задачи коммивояжера
В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».
Итак, методика решения задачи коммивояжера:
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-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.
Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.
Исправленный алгоритм, для нахождения действительно минимального маршрута
Алгоритм состоит из двух этапов:
Первый этап
Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.
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). А также следует выбирать для разбиения множество с минимальной границей из всех возможных путей, а не из двух полученных в результате последнего разбиения детей.
Доказательство
Вернемся к картинке в начале поста:
А вот решение с исправленным алгоритмом.
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу - в задаче минимизации, сверху - в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
Таблица 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 ! - количеству способов упорядочения пунктов). К примеру, для 100 пунктов количество вариантов будет представляться 158-значным числом - не выдержит ни один калькулятор! Мощная ЭВМ, способная перебирать миллион вариантов в секунду, будет биться с задачей на протяжении примерно 3 ⋅ 10 144 лет. Увеличение производительности ЭВМ в 1000 раз даст хоть и меньшее в 1000 раз, но по-прежнему чудовищное время перебора вариантов. Не спасает ситуацию даже то, что для каждого варианта маршрута имеется 2 n равноценных, отличающихся выбором начального пункта (n вариантов) и направлением обхода (2 варианта). Перебор с учётом этого наблюдения сокращается незначительно - до n ! 2 n = n − 1 ! 2 вариантов.
Может быть, алгоритм, основанный на полном переборе вариантов, не является самым эффективным (в смысле быстродействия) для решения задачи коммивояжёра? Увы, доказано, что не существует алгоритма решения, имеющего степенную сложность (то есть требующего порядка n a операций для некоторого a) - любой алгоритм будет хуже. Всё это делает задачу коммивояжёра безнадёжной для ЭВМ с последовательным выполнением операций, если n хоть сколько-нибудь велико.
В таком случае следует отказаться от попыток отыскать точное решение задачи коммивояжёра и сосредоточиться на поиске приближённого - пускай не оптимального, но хотя бы близкого к нему. В виду большой практической важности задачи полезными будут и приближённые решения.
Заметим, что интеллект человека, не вооружённый вычислительной техникой, способен отыскивать такие приближённые решения задач, требующих огромного перебора вариантов в поисках оптимального. Вспомним хотя бы шахматы. Человек может весьма успешно соперничать в этой игре с вычислительной машиной либо вовсе не прибегая к перебору, либо сводя его к минимуму. Человек руководствуется при этом интуицией и набором эвристик (находок) - правил, которые обычно помогают в решении задач, хотя эффективность таких правил и не имеет достаточного обоснования. В качестве подобной универсальной эвристики можно упомянуть категорический императив Канта : «поступай с другими так, как тебе хотелось бы, чтобы поступали с тобой». Другой, более приземлённый пример даёт золотое правило валютного спекулянта: «когда все продают доллары, ты покупай, а когда все покупают - продавай».
Многие природные процессы решают задачи выбора оптимального варианта из огромного (даже, возможно, бесконечного) множества вариантов. Например, тяжёлая гибкая однородная цепочка, подвешенная за концы на двух гвоздиках, из всевозможных доступных форм принимает именно ту, которая соответствует минимуму потенциальной энергии силы тяжести (которая пропорциональна высоте центра тяжести цепочки). Причём цепочке для поиска нужной формы (она называется катеноидой , или цепной линией ) требуется времени гораздо меньше, чем человеку, составляющему и решающему дифференциальное уравнение Эйлера - Лагранжа для нахождения этой самой катеноиды. Мыльная плёнка, натянутая на проволочный контур, принимает форму, соответствующую минимуму внутренней энергии плёнки (состоящей, в основном, из потенциальной энергии сил поверхностного натяжения, пропорциональной площади плёнки). Световой луч в прозрачной (возможно, неоднородной) среде, преломляясь, отыскивает кратчайший путь (требующий наименьшего времени прохождения любого своего участка) с учётом скорости света в каждой точке среды, через которую он проходит. Вещество, кристаллизуясь из расплава, постепенно принимает ту кристаллическую форму, которая минимизирует опять же внутреннюю энергию, складывающуюся из энергий попарного взаимодействия молекул. В последнем примере молекулы вещества, совершающие хаотическое тепловое движение, которое замедляется по мере остывания, постепенно «нащупывают» нужную, минимальную в энергетическом смысле конфигурацию среди огромного количества вариантов расположения молекул. Биологическая эволюция совершенствует виды, снижая вероятность выживания (и, соответственно, передачи потомству генетической информации) менее приспособленных особей.
Все эти соображения ведут нас к эвристике: «хочешь приближённо решить задачу - смоделируй (например, с помощью ЭВМ) природный процесс, решающий подобную задачу». Вот несколько конкретных приложений этой эвристики: «нужен эллипс - посвети фонариком на пол, слегка наклонив его (фонарик или пол)». Или «налей в цилиндрический или конический стакан воды и чуть наклони». Или «возьми батон колбасы и разрежь наискосок». «Нужна синусоида - заверни колбасу в бумагу и разрежь вместе с бумагой, а затем разверни бумажный лист». Или «присоедини колебательный контур к осциллографу» - колебательный контур мгновенно решает дифференциальное уравнение колебаний, а решения этого уравнения - синусы и косинусы. «Хочешь вычислить определённый интеграл - вырежи криволинейную трапецию из бумаги, взвесь её и подели на массу единичного бумажного квадратика».
Описанные выше наблюдения позволяют считать природные процессы вычислительными машинами (такие машины называют аналоговыми ), вполне пригодными для решения многих важных задач. Аналоговые вычислительные машины можно использовать непосредственно, а можно принципы их работы положить в основу весьма эффективных алгоритмов для традиционных, цифровых ЭВМ. Единственное, что может пострадать при таком моделировании - точность решения задачи.
Переборные задачи, нацеленные на поиск оптимального варианта, называют задачами комбинаторной оптимизации
Дадим формальную постановку задачи оптимизации. Дано конечное (обычно очень большое) множество X и числовая функция U x на этом множестве. Эту функцию называют целевой . Требуется найти такой x * ∈ X , что U x * будет наименьшим, то есть U x * ⩽ U x для всех x ∈ X . Вариант постановки задачи, когда требуется найти точки максимума целевой функции, легко сводится к поиску точек минимума функции − U .
Задача коммивояжёра может быть поставлена как задача оптимизации. В качестве множества X достаточно взять S n (множество перестановок n -элементного множества), а в качестве целевой функции U x - длину замкнутой ломаной, проходящей через n заданных точек в порядке, заданной перестановкой x ∈ X .
Для решения задачи поиска точки минимума функции придумано множество методов. Например, для дифференцируемых функций U , определённых на числовом множестве X , как известно, точки минимума (если они есть) следует искать среди критических точек U , то есть таких x , что U ′ x = 0 . Однако о дифференцируемости функции, определённой на конечном множестве, к тому же не обязательно числовом, говорить не приходится, поэтому метод, основанный на критических точках, не годится. Полный перебор всех x мы тоже отвергаем по причинам, которые обсуждались выше.
Для множеств X , для которых определено отношение близости , годятся и другие методы. Среди них - метод градиентного спуска
Отношение близости - это способ определить для двух элементов множества, являются ли они близкими (в каком-нибудь смысле). Для числовых множеств, для множеств точек на плоскости или в пространстве близкими можно считать два числа (две точки), расстояние между которыми не превосходит некоторого маленького числа ε . Для множества S n близкими удобно считать две перестановки, отличающиеся на одну транспозицию , то есть получающиеся друг из друга «рокировкой» двух элементов множества. Например, перестановки 2 4 1 3 и 2 3 1 4 являются близкими в этом смысле, так как отличаются перестановкой элементов с номерами 2 и 4 . Можно определить и более строгое отношение близости, при котором близкие перестановки отличаются на соседнюю транспозицию , когда рокировка затрагивает элементы множества с соседними номерами. Тогда указанные выше перестановки близкими уже не будут, но близкими окажутся 2 4 1 3 и 2 4 3 1 .
Суть метода градиентного спуска отражена в его названии и заключается в следующем. Строится последовательность x 0 x 1 x 2 x 3 … ⊂ X , в которой начальный элемент x 0 выбирается произвольно (возможно, случайным образом), а каждый последующий является одним из соседей предыдущего, причём именно тем из соседей, для которого значение функции U будет наименьшим. Построение последовательности завершается тогда, когда последовательность значений целевой функции U x 0 U x 1 U x 2 U x 3 … перестанет быть монотонно убывающей.
Последний элемент построенной последовательности называют точкой локального минимума . Это такая точка, в которых значение U строго меньше, чем во всех соседних с ней. В слове «локальный» заключён главный недостаток описанного метода. Локальных минимумов у функции U может быть много, и каждому из них отвечает, как правило, своё локально минимальное значение целевой функции. Нас же интересует абсолютный минимум функции и тот элемент множества X , в котором он достигается. Если бы было легко найти все точки локального минимума, перебором среди них мы нашли бы точку абсолютного минимума. Но метод градиентного спуска не даёт рецепта поиска всех точек локального минимума, он позволяет найти лишь какую-нибудь .
Имеется вероятностная версия метода градиентного спуска. На каждом шаге для элемента множества X выбирается случайный сосед. Если значение целевой функции в случайной соседней точке уменьшилось, она добавляется в последовательность и мы переходим к следующему шагу. Если же нет, то снова выбирается случайный сосед. Алгоритм останавливается, если достаточно долго не пополняется последовательность (не происходит переход к следующему шагу): вероятно, алгоритм в этом случае привёл в точку локального минимума.
Один из приближённых методов решения таких задач оптимизации - метод имитации отжига . Отжиг - уже упоминавшийся процесс постепенного остывания вещества, при котором молекулы на фоне всё замедляющегося теплового движения собираются в наиболее энергетически выгодные конфигурации. Термин «отжиг» пришёл из металлургии. Дело в том, что металл в более энергетически выгодном состоянии одновременно твёрже и прочней: требуется большее внешнее воздействие, большая механическая работа над куском металла, чтобы нарушить выгодную конфигурацию молекул, «приподнять» эту конфигурацию над самым дном энергетической ямы.
Метод имитации отжига является модификацией вероятностного метода градиентного спуска. Отличие заключается в поведении алгоритма, когда U x ⩽ U x ~ , где x - очередной элемент последовательности, а x ~ - его сосед, выбранный наугад. Вероятностный метод градиентного спуска отвергал такого соседа безусловно, а метод имитации отжига допускает добавление такого «плохого» соседа в последовательность, правда, с некоторой вероятностью p , зависящей от того, насколько плохой сосед ухудшил целевую функцию. Возьмём разность ∆ U = U x ~ − U x (она неотрицательна, если сосед «плохой») и положим p = e − ∆ U Θ . Здесь e - некоторое число, большее единицы (какое именно, не принципиально, но обычно берут e ≈ 2,718281828459045… - основание натуральных логарифмов), а Θ - некоторое положительное число, называемое температурой
На рисунке 45.1. «Вероятность мутации для метода имитации отжига» показаны зависимости вероятности мутации от величины ∆ U при различных значениях температуры Θ . Высоким температурам соответствуют графики, чей цвет ближе к красному, низким - к синему. Как и положено, значение вероятности заключено в отрезке 0 1 . При отрицательных ∆ U вероятность равна 1 , что соответствует случаю «хорошей» мутации.
Продолжение следует…
В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений.
Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .
Математическая модель задачи коммивояжера
Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).
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
Методы решения задачи коммивояжера
- метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
- венгерский метод. Пример решения венгерским методом .
Алгоритм Литтла или исключения подциклов
- Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
- Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
- Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
- Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
- Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
- Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
- Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
- Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
- Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
- Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.
Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей
| 1 | 2 | 3 | 4 | |
| 1 | - | 5 | 8 | 7 |
| 2 | 5 | - | 6 | 15 |
| 3 | 8 | 6 | - | 10 |
| 4 | 7 | 15 | 10 | - |
Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij
| 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 |
d j = min(i) d ij
| 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 |
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления
| 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 |
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
| 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 |
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.
| 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 |
Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| 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 |
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
| 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 |
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.
После операции приведения сокращенная матрица будет иметь вид:
| 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 |
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .
| 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) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| 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 |
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.
| 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 |
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
| 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 |
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| 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 |
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.
| 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 |
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
| 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 |
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| 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 |
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
| 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 |
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
| i j | 3 | 4 | d i |
| 3 | M | 0 | 0 |
| 5 | 0 | 0 | 0 |
| d j | 0 | 0 | 0 |
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41
Дерево решений.
| 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||