Тема: Задача о коммивояжере и ее обобщения
Методы решения задачи о Коммивояжере
Содержание
В условиях задачи указываются критерий выгодности маршрута кратчайший, самый дешёвый, совокупный критерий и тому подобное и соответствующие матрицы расстояний, стоимости и тому подобного. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости , метрическая задача коммивояжёра когда на матрице стоимостей выполняется неравенство треугольника , симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра. Оптимизационная постановка задачи относится к классу очень NP-трудных задач, впрочем, как и большинство её частных случаев. Задача коммивояжёра относится к числу трансвычислительных: Точно неизвестно, когда проблему коммивояжера исследовали впервые. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии. Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру нем. Вскоре появилось известное сейчас название задача странствующего торговца англ. Traveling Salesman Problem , которую предложил Хасслер Уитни англ. Hassler Whitney из Принстонского университета. Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации. Многие современные распространенные методы дискретной оптимизации , такие как метод отсечений , ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра. В е и е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу , Делберту Рею Фалкерсону англ. Delbert Ray Fulkerson и Селмеру Джонсону англ. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В е и е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике. Больших успехов удалось достичь в конце х и х годах, когда Мартин Грётчел нем. Manfred Padberg и Джованни Ринальди итал. Giovanni Rinaldi и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с городами. В е годы Дэвид Аплгейт англ. David Applegate , Роберт Биксби англ. Robert Bixby , Вашека Шватал англ. William Cook установили рекорды по программе Конкорд. В апреле было найдено решение для экземпляра с 85 узлами. Для возможности применения математического аппарата для решения проблемы её следует представить в виде математической модели. Проблему коммивояжёра можно представить в виде модели на графе , то есть, используя вершины и ребра между ними. Гамильтоновым циклом называется маршрут, включающий ровно по одному разу каждую вершину графа. В целях упрощения задачи и гарантии существования маршрута обычно считается, что модельный граф задачи является полностью связным , то есть, что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными городами не существует сообщения, этого можно достичь путём ввода рёбер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет к оптимальному маршруту, если он существует. В зависимости от того, какой критерий выгодности маршрута сопоставляется величине ребер, различают различные варианты задачи, важнейшими из которых являются симметричная и метрическая задачи. В общем случае, асимметричная задача коммивояжёра отличается тем, что она моделируется ориентированным графом. Таким образом, следует также учитывать, в каком направлении находятся ребра. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая. Симметричная задача моделируется неориентированным графом см. На самом деле, задача коммивояжёра в случае реальных городов может быть как симметричной, так и асимметричной в зависимости от длительности или длины маршрутов и от направления движения. Симметричную задачу коммивояжёра называют метрической , если относительно длин ребер выполняется неравенство треугольника. Такое свойство длины ребер определяет измеримое пространство на множестве ребер и меру расстояния, удовлетворяющую интуитивному пониманию расстояния. Распространенные на практике функции расстояния являются также метриками и удовлетворяют неравенству треугольника:. Две последние метрики находят применение, например, при сверлении отверстий в печатных платах, когда станок должен сделать больше отверстий за наименьшее время и может перемещать сверло в обоих направлениях для перехода от одного отверстия к следующему. Неметрическая задача коммивояжёра может возникать, например, в случае минимизации длительности пребывания при наличии выбора транспортных средств в различных направлениях. В таком случае обходной путь самолетом может быть короче прямого сообщения автомобилем. Если на практике в условиях задачи разрешается посещать города несколько раз, то симметричную задачу можно свести к метрической. Для этого задачу рассматривают на так называемом графе расстояний. Этот граф имеет такое же множество вершин, как и исходный, и является полностью связным. Таким образом, возможно несколько вариантов. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства. Каждая вершина должна сообщаться через пару ребер с остальным вершинам, то есть, через входное и выходное ребро:. Она равна 2, так как каждая вершина имеет входное и выходное ребро. Описанные ранее условия кратности выполняются не только маршрутами, но и значениями переменных, соответствующих отдельным циклам, где каждая вершина принадлежит лишь одному циклу см. Так, каждый вектор с элементами, равными 0 и 1, удовлетворяющий всем неравенствам, определяет корректный маршрут, который является решением переформулированной задачи коммивояжёра: Эту проблему можно решить применением метода отсечения плоскостью , благодаря которому неравенства добавляются, только когда эти неравенства действительно необходимы. С геометрической точки зрения, линейные неравенства можно представить как гиперплоскости в пространстве переменных. Однако, можно показать, что условия 1 и 2 определяют грани фацет политопа, то есть боковые поверхности политопа с наивысшей размерностью. Поэтому они относятся к самым сильным линейным неравенствам, которые могут описывать маршрут. Также существует много разных граней, определяемых неравенствами, известными лишь в немногих случаях. Хотя 1 и 2 вместе с ограничениями полностью моделируют проблему только для двоичных векторов, эти неравенства могут использоваться в методе ветвей и границ , чтобы отбросить решения методами линейной оптимизации с нецелыми координатами см. Таким образом, размер пространства поиска зависит экспоненциально от количества городов. Различные варианты задачи коммивояжёра метрическая, симметричная и асимметричная NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга , способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов. Однако, существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность лучшую, чем 1,5 от оптимальной. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема полиномиального времени PTAS для поиска приближённого решения. В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину. Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину. Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time-алгоритмы [ уточнить ] , то есть, постепенно улучшающие некоторое текущее приближенное решение. Существуют также постановки, в которых задача коммивояжёра становится NP-полной. Обычно такие постановки выглядят следующим образом: Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора. На практике применяются различные модификации более эффективных методов: Однако даже для небольшого количества городов решать задачу таким способом практически невозможно. То, как стремительно растет продолжительность вычислений, можно показать на следующем примере. Если бы существовало устройство, находящее решение для 30 городов за час, то для двух дополнительных городов требуется в тысячу раз больше времени; то есть, более чем 40 суток. Методы дискретной оптимизации, в частности ветвей и границ, позволяют находить оптимальные или приблизительные решения для достаточно больших задач. Гиперплоскости, описываемые этими неравенствами, отсекают такие ребра единичного куба, которые не соответствуют ни одному маршруту. На рисунке рядом показано применение метода для задачи с тремя узлами. В этом случае существует лишь один возможный маршрут, а именно тот, что проходит через три вершины. Кроме этого маршрута, что соответствует вектору 1,1,1 , неравенству удовлетворяют также все точки в отмеченной красным части этого неравенства. Плоскости, проходящие через красные линии, отсекают все углы, отвечающие несуществующим маршрутам с максимум одним ребром, а именно, ноль-вектор 0, 0, 0 , единичные векторы 1, 0, 0 , 0, 1, 0 и 0, 0, 1. В этом отдельном случае тот же эффект можно получить тремя неравенствами типа 1. Для определения допустимого ребра с наименьшей длиной следует решить наборы задач линейной оптимизации, отсекающие секущими плоскостями ненужные части единичного куба и попытаться разделить единичный куб на меньшие политопы методом ветвей и границ. Однако этого метода для быстрого поиска маршрутов обычно недостаточно. Основное преимущество точных методов заключается в том, что имея достаточно времени, они вычисляют кратчайший маршрут. Имея нижнюю границу для оптимальных решений, можно оценить то, насколько отличается найденный маршрут от оптимального. Например, имея нижнюю границу на уровне , и после нахождения маршрута длиной , оптимальный маршрут может находиться в пределах от до Когда длина вычисленного маршрута равна длине предыдущего, считается, что найденное решение является оптимальным. Для поиска маршрутов приемлемой длины точные методы могут комбинироваться с эвристическими. Метод ветвей и границ для решения задачи коммивояжёра был предложен в году группой авторов Дж. В году его использовали Дурбин Durbin и Уиллшоу Willshaw , указавшие аналогию с механизмами установления упорядоченных нейронных связей [2]. Каждый из маршрутов коммивояжёра рассматривался как отображение окружности на плоскость в каждый город на плоскости отображается некоторая точка этой окружности. Соседние точки на окружности должны отображаться в точки, по возможности ближайшие и на плоскости. Начинается с установки на плоскость небольшой окружности. Она неравномерно расширяется, становясь кольцом, проходящим практически около всех городов и устанавливая таким образом искомый маршрут. На каждую движущуюся точку кольца оказывает действие две составляющие: Город в итоге связывается с определенным участком кольца по мере расширения. По мере расширения такой эластичной сети каждый город оказывается ассоциирован с определенным участком кольца. Вначале все города оказывают приблизительно одинаковое влияние на каждую точку маршрута. В последующем, большие расстояния становятся менее влиятельными и каждый город становится более специфичным для ближайших к нему точек кольца. Такое постепенное увеличение специфичности, которое напоминает метод обучения сети Кохонена, контролируется значением некоторого эффективного радиуса. Дурбин и Уиллшоу показали, что для задачи с 30 городами, рассмотренной Хопфилдом и Танком, метод эластичной сети генерирует наикратчайший маршрут примерно за итераций. Материал из Википедии — свободной энциклопедии. Метод ветвей и границ. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Проставив сноски , внести более точные указания на источники. Упаковка в контейнеры двумерная упаковка линейная упаковка упаковка по весу упаковка по стоимости Задача о ранце рюкзаке. Задача о вершинном покрытии Задача о клике Задача о независимом множестве наборе Задача о покрытии множества Задача Штейнера Задача коммивояжёра Обобщённая задача коммивояжёра. Задача выполнимости булевых формул в конъюнктивной нормальной форме. Обобщённые пятнашки игра в N 2 -1 задача поиска кратчайшего решения Задачи, решения которых применяются в Тетрис Задача обобщённого судоку Задача о заполнении латинского квадрата Задача какуро. Классы сложности Исследование операций Оптимизация Комбинаторная оптимизация Прикладная математика Теория алгоритмов Динамическое программирование 21 NP-полная задача Карпа. NP-полные задачи Теория графов Комбинаторика Гамильтоновы пути и циклы Исследование операций. Страницы, использующие волшебные ссылки ISBN Статьи, требующие уточнения источников Википедия: Статьи к переработке Википедия: Стилистически некорректные статьи Википедия: Навигация Персональные инструменты Вы не представились системе Обсуждение Вклад Создать учётную запись Войти. Пространства имён Статья Обсуждение. Просмотры Читать Править Править вики-текст История. В других проектах Викисклад. Эта страница последний раз была отредактирована 1 июня в Текст доступен по лицензии Creative Commons Attribution-ShareAlike ; в отдельных случаях могут действовать дополнительные условия. Свяжитесь с нами Политика конфиденциальности Описание Википедии Отказ от ответственности Разработчики Соглашение о cookie Мобильная версия. Мы называем проблемой посыльного поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно. Эта статья или раздел нуждается в переработке.
Добавить в избранное О проекте. Задача о коммивояжере и ее обобщения Вид работы:. Все дипломные по математике. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно. Задача о коммивояжере относится к классу NP-трудных задач. Методы решения задачи о коммивояжере различны. В данной курсовой кратко рассказывается только о некоторых наиболее известных. Эти методы имеют большую погрешность. Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи, но они довольно громоздки. Метод перебора прост, но только лишь при небольшом количестве итераций. И наиболее удобным мне кажется метод ветвей и границ. Его можно применять и при большом количестве городов. В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут - порядок посещения городов так, чтобы путь, который ему придется пройти, был как можно короче. Основное условие этой задачи состоит в том, что коммивояжер не имеет права возвращаться снова в этот город, в котором он однажды уже побывал. Мы считаем, что расстояние между двумя городами - функция f x i , x j - определено. Разумеется, функция f x i , x j может означать не только расстояние, но, например, время или издержки в пути и т. Длина l пути S определяется формулой 1. Рассмотрим снова плоскость t, x, где t - дискретный аргумент, принимающий значения 0,1, 2, …, N , соответствующие этапам путешествия торговца. Аргумент x теперь также принимает дискретные значения 1,2, …, N Рисунок 1. Соединим точку 0, 1 с точками 1,1 , 1, 2 , … 1, N и длинам отрезков, соединяющих эти точки, припишем значения f x 1 ,x j. Далее точки 1, s - узлы, лежащие на первой вертикали, мы соединим со всеми уздами второй вертикали, длинам отрезков мы припишем значения f x s , x k и т. В результате мы построили некоторый граф, каждая ломанная которого, соединяющая точку 0,1 сточкой N,1 , описывает путь коммивояжера. Нашу задачу мы можем теперь сформулировать следующим образом. Таким образом, задача о коммивояжере формулируется более привычным для нас языком. Рассмотрим узел P , лежащий на третьей вертикали Рисунок 1. В данном случае ситуация иная, и если два коммивояжера находятся в точке P , но один из них пришел в это состояние, двигаясь вдоль траектории, проходящей через точку Q , а второй через точку R , то их состояния существенно отличаются друг от друга. Коммивояжер, который двигался по второй траектории , уже побывал в городах номер 2 и номер 5 и в будущем он уже не имеет права снова заезжать в эти города. Что касается коммивояжера, который двигался вдоль первой траектории, то он побывал в городах номер 3 и номер 6; он не имеет права возвращаться в эти города, но зато он еще обязан посетить города номер 2 и номер 5 и т. Поскольку функция f x i , x j определена на конечном множестве точек, то и функция l х 1 ,…,x N также определена на конечном множестве точек. Следовательно, задача определения минимума функции l сводится к перебору некоторого конечного множества значений этой функции, и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны. Легко подсчитать, что число возможных вариантов число значений функции l равно N - 1! Таким образом, непосредственно перебрать и сравнить между собой все возможные пути, по которым может следовать бродячий торговец, для достаточно большого количества городов практически невозможно. Но немного расскажем о них. Итак, имеется n городов, которые нужно обойти. Для этого достаточно проложить n -1 путей между городами. Как соединить города так, чтобы суммарная стоимость путешествия была минимальна? В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G V , E , в котором V - множество вершин городов , а E - множество их возможных попарных соединений дороги. Пусть для каждого ребра u , v однозначно определено некоторое вещественное число w u , v - его вес длина или стоимость пути. W u , v называется весовой функцией. Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом. Так как рассматриваются только деревья, можно считать все ребра положительными достаточно добавить к весу всех ребер некоторую относительно большую положительную константу. В противном случае, если стоимость соединения между двумя вершинами равна отрицательному числу, можно несколько раз параллельно соединить их для уменьшения суммарного веса остовного подграфа. Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным с суммарным весом v-1 , где v - количество вершин в графе. Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G , который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом n деревьев из одной вершины. На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Такое ребро называется безопасным. По определению A , он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом любое ребро остова, не входящее в A. Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности изначально все вершины в отдельных компонентах, в конце A - одна компонента. Таким образом анализ графа выполняется n-1 раз. Далее приводится общее правило отыскания безопасных ребер. Для этого есть теорема, которая поможет находить безопасные ребра. Пусть G V;E - связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А - некоторый подграф G , являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E K ребер графа G , только один конец которых лежит в К. Тогда ребро минимального веса из E K будет безопасным. В связи с приведенной теоремой введем следующее: В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается лидер или корень - вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшем случае с помощью обхода A в глубину: После того, как лидеры выбраны, для каждой компоненты связности находится безопасное для нее ребро, по существу методом грубой силы. Как только все такие ребра отобраны, они добавляются к A. Процесс продолжается до тех пор, пока в A присутствует больше одной компоненты связности. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее показанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным. Остается понять, как реализовать выбор безопасного ребра на каждом шаге. Для этого в алгоритме Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются. Удобно использовать для хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу один из самых быстрых известных методов. Элементами множеств являются вершины графа, каждое множество содержит вершины одной связной компоненты. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: По теореме такое ребро является безопасным. При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами кучей. Алгоритм получает на вход граф G и его корень r - вершина, на которой будет наращиваться минимальный остов. Приоритет вершины v определяется значением key[ v ], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[ v ] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на остов дерева, в которою ведет ребро с весом key[ v ] одно из таких ребер, если их несколько. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты по одной копейке. Нам не только удалось быстро определить перечень монет нуясного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства. Задача коммивояжера Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений — задача коммивояжера , имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем. Скачать Скачать документ Читать online Читать online. Основной объект теории графов-граф и его обобщения. Некоторые модели сводятся к задаче о нескольких коммивояжерах , но мы здесь их рассматривать не будем. Блочно-симметричные модели и методы проектирования систем обработки данных Показатели эффективности ДС и ее компонент определяется как показатели эффективности отдельных СМО и сети в целом. Одним из типичных примеров комбинаторной модели является задача о коммивояжере. Разработка медицинского автоматизированного манипулятора Охарактеризуем свойство обратимости, на примере следующих доменов планирования: Решения задачи планирования производства симплекс методом Метод используется для решения некоторых NP-трудных задач , такие как: Психология между теорией и практикой Наконец, принцип неопрагматизма оправдывает использование любых этически Нужна качественная работа без плагиата? Другие дипломные по математике. Не нашел материала для курсовой или диплома? Наш проект для тех, кому интересно, для тех, кто учится, и для тех, кто действительно нуждается!
Основания и фундаменты зданий при реконструкции
Время обладает характеристикой
Трэш фильм про
Лютеосил инструкция по применению в ветеринарии
Проверка статуса заявления в детский сад сургут