Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Каримов Р.А. 1

---

1 Сибирский федеральный университет

Задача коммивояжера, проблема оптимизации в теории графов, в которой узлы (города) графа соединены направленными ребрами (маршрутами), где вес края указывает расстояние между двумя городами. Проблема состоит в том, чтобы найти путь, который посещает каждый город один раз, возвращается в начальный город и минимизирует пройденное расстояние. Единственный известный алгоритм общего решения, гарантирующий кратчайший путь, требует времени решения, которое растет экспоненциально с размером задачи (т. Е. Количеством городов). Это пример NP-полной проблемы (из неполиномиальной), для которой не существует известного эффективного алгоритма (то есть полиномиального времени). Изучение этой проблемы привлекло многих исследователей из разных областей, например, математики, исследования операций, физики, биологии или искусственного интеллекта. Это связано с тем, что TSP демонстрирует все аспекты комбинаторной оптимизации и служит и продолжает служить в качестве ориентира для новых алгоритмических идей, таких как моделируемый отжиг, поиск с запретами, нейронные сети и эволюционные методы. Теоретические исследования, связанные с вопросами сложности задач дискретной оптимизации, а также с построением и анализом эффективных приближенных алгоритмов решения этих задач, находятся в русле современных, интенсивно развивающихся областей математики. Терминология, возникающая в ходе этих исследований, широко распространена в современной научной литературе и требует определенного с ней знакомства.

Статья в формате PDF

138 KB

задача коммивояжера

методы оптимизации

комбинаторная оптимизация

поиск выгодного маршрута

np-трудные задачи

теория графов

венгерский метод

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

1. Евдокимов И.В. Сумма гармонических сигналов с постоянной составляющей как тестирующее воздействие в одном методе активной идентификации//Труды Братского государственного университета. Серия: Естественные и инженерные науки. 2005. Т. 1. С. 39-41.

2. Буштрук Т.Н., Буштрук А.Д., Евдокимов И.В. Метод идентификации моделей фильтр Заде//Современные информационные технологии. 2004. № S1. C. 122-125.

3. Дэвид Эплгейт, Роберт Е. Биксби, Васэк Чватал, Уилльям Дж. Кук.//The Travelling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics) 2nd Printing Edition. С. 152-160.

4. Андрэс Бьёрклунд. // Determinant Sums for Undirected Hamiltonicity. Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS ’10), pp. 173–182.

5. M. Хэлд, R. M. Карп. // A Dynamic Programming Approach to Sequencing Problems Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210.

6. Палуч, K., Эльбассиони, K., Зайлен, A. вaн. // Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. STACS’ 12 С. 120-124.

7. А. В. Кононов, П. А. Кононова. // Приближенные Алгоритмы для NP-трудных задач. 2014. С 31-37.

8. Сердюков А. И. Асимптотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Методы целочисленной оптимизации (Управляемые системы). — 1987. — № 27. — С. 79-87.

Оптимизация занимает достаточно большую часть в жизни людей. Порой мы даже не задумываемся о том, что мы что-то оптимизируем. Так, к примеру, мы отправляемся в путешествие и нам необходимо собрать много вещей, а чемодан средних размеров. (Мы тоже имеем физические ограничения) Если мы пойдем на пляж, то взять шорты, очки и крем от загара будет значительно лучшим решением, если бы возьмем с собой зимнюю куртку, то есть опираясь на приоритет вещей мы делаем свой выбор, чтобы суммарная ценность груза была максимальной.

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

Более строгим будет определение, что оптимизация – это инструмент, который находит оптимальное решение.

Математически «оптимизация» - представляет собой, нахождение MAX и MIN функции [1].

Наконец разобравшись с тем, что такое оптимизация и, что она делает.

Попробуем разобраться – «How does it work?!» (Как это работает?)

Представим на секунду, что наш чемодан превратился в корабль, а в котором множество отсеков, задача которого переправить товар в точку доставки (наша задача осталась неизменна – привести суммарную ценность к ее максимуму), целевой функцией будет сумма стоимости продукции. Теперь, нам понадобиться значительно больше времени для нахождения оптимального решения.

Взяв случайное решение, мы не сможем быть уверенны, что оно хоть сколько-нибудь будет приближенно к искомому экстремуму. Существует большое количество методов, которые помогут решить данную задачу [2]. Их такое количество, что их разделяют на классы.

Одним из них является метод имитации отжига (или просто метод отжига.), он входит в класс стохастических.(то-есть который может угадывать) Зачем же здесь вероятность? Ответим на это дальше. Но для начала приведем примеры прикладного применения глобальной оптимизации.

Где используем?

Существует множество применений методов глобальной оптимизации [3]. Используется для реконструкции изображений, глобальной маршрутизации, назначение задач и планирование, и многое другое.

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

Начнем с метода «ветвей и границ»:

Шаг 1: Построение исходной матрицы

Представим длины дорог соединяющих города:

Шаг 2: Нахождение min по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец [4].

Шаг 3: Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Шаг 4: Нахождение min по столбцам

Теперь, находим минимальные значения в каждом столбце (dj)

Шаг 5: Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

Шаг 6: Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка [5]. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

Шаг 7: Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Шаг 8: Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

Шаг 9: Вычисление итоговой длины пути и построение маршрута

Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.) [6]. Длины дорог соединяющих города берем из самой первой таблицы с исходными данными. Общая длина пути: L = 30.

А теперь «венгерский метод», исходная матрица принимает вид:

Шаг 1: Проводим редукцию матрицы по строкам. В новой матрице в каждой строке будет ка минимум 1 ноль.

Теперь, по столбцам:

После вычитания минимальных элементов получим полностью редуцированную матрицу [7].

Шаг 2: Методом проб и ошибок осуществим поиск допустимого решения, для которого все значения имеют нулевую стоимость.

Получим эквивалентную матрицу Сэ:

Шаг 3: Методом проб и ошибок определяем матрицу назначения Х, которая позволит по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения [8].

Заключение

Ответ на вопрос, «Какой же из алгоритмов лучше?» достаточно прост и очевиден. Так как метод ветвей и границ является вариацией полного перебора, и для большого объема входных данных он слабо или абсолютно не подходит - вычисления будут не красивые и громоздкие. Для решения крупных задач больше подойдет венгерский метод в силу того, что он значительно сокращает вычисления и считается более точным.

Библиографическая ссылка