 |
Формулировка в виде задачи дискретной оптимизации
|
|
|
|
Содержание
Введение
Задача о коммивояжере. Определение. История.
Метод полного перебора
Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения»
Метод полного перебора
Заключение
Список литературы
Введение
Задача коммивояжера, известная также как задача о сверлильном станке или алгоритм коммивояжера была поставлена в 1934 году. Эта задача является одной из знаменитых задач теории комбинаторики и широко применяется при разработке программного обеспечения.
Целью данной курсовой работы является постановка задачи коммивояжера и ее решение методом полного перебора с использованием надстройки MS Excel «Поиск решения».
Объектом исследования в курсовой работе выступает программа, реализующая один из методов решения задачи коммивояжера - надстройка MS Excel «Поиск решения».
Предмет курсовой работы – сущность задачи коммивояжера, порядок и методы ее решения.
Для достижения поставленной цели необходимо решить следующие задачи:
ü изучить понятие и особенности задачи коммивояжера;
ü ознакомиться с практическим применением задачи коммивояжера;
ü рассмотреть методы решения задачи коммивояжера;
ü получить представление о назначении надстройки MS Excel «Поиск решения»;
ü сформулировать задачу коммивояжера и решить ее при помощи надстройки MS Excel «Поиск решения».
ЗАДАЧА О КОММИВАЯЖОРЕ.ОПРЕДЕЛЕНИЕ. ИСТОРИЯ
Определение
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
|
|
|
Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет
История
Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для ее решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.
|
|
|
Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру (нем. Karl Menger), который сформулировал ее на математическом коллоквиуме в 1930 году так: Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, ее решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.
Вскоре появилось известное сейчас название задача странствующего продавца (англ. Traveling Salesman Problem), которую предложил Гаслер Уитни (англ. Hassler Whitney) из Принстонского университета.
Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжера отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины 20-го века, исследование задачи коммивояжера имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.
Многие современные распространенные методы дискретной оптимизации, такие как метод деления плоскостью, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера.
В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corportation сформулировали задачу в виде задачи дискретной оптимизации и разработали метод деления плоскостью для ее решения. Используя новый метод, они вычислили путь для отдельного набора узлов с 49 городами и доказали, что не существует короткого пути. В 1960-е и 1970-е годы многочисленные группы исследователей изучали задачу с точки зрения математики и ее применения, например, в информатике, экономике, химии и биологии.
Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-полнота задачи коммивояжера. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.
|
|
|
Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Гиованни Ринальди (нем. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.
В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашека Шватал (англ. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1 % больше оптимальной.
Формулировка в виде задачи дискретной оптимизации
Одним из подходом к решению задачи является формулировка ее в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер V. Каждому ребру {i,j} сопоставляется двоичная переменная, равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства.
|
|
|
Условие кратности: каждая вершина должна иметь одно входное и одно выходное ребро маршрута.
В сумме каждое слагаемое xij равно или 1 (принадлежит маршруту) или 0 (не принадлежит). То есть, полученная сумма равна количеству ребер в маршруте, имеющих вершину i на одном из концов. Она равна 2, так как каждая вершина имеет входное и выходное ребро. В приведенном рядом рисунке вершина i показана с входным и выходными ребрами, а ребра маршрута обозначены толстыми линиями. Рядом с ребрами указаны длины xij, прилагаемые к указанной выше сумме.
Алгоритмическая сложность
Поскольку коммивояжер в каждом из городов встает перед выбором следующего города из тех, что он еще не посетил, существует (n − 1)! маршрутов для асимметричной и (n − 1)! / 2 маршрутов для симметричной задачи коммивояжера. Таким образом, размер пространства поиска зависит экспоненциально от количества городов.
Различные варианты задачи коммивояжера (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга, способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.
Также известно, что при условии не существует алгоритма, который для некоторого полинома p вычислял бы такие решения задачи коммивояжера, которые отличались бы от оптимального максимум на коэффициент 2p(n).
Однако, существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность, лучшую чем 1,5 от оптимальной. По предположению, существует (неизвестная) константа c > 0, такая, что ни один алгоритм с полиномиальным временем не может гарантировать точность 1 + c. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема поиска приблизительных решений задачи (PTAS).
Замкнутый и незамкнутый варианты задачи
В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину. Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.
Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.
|
|
|
Чтобы свести замкнутый вариант к незамкнутому, нужно определить число K, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве K можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину vn (предполагаем, что вершины исходного графа пронумерованы числами от 0 до n − 1, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину vn, определяются следующим образом:
cn,i = 3K
c0,n = 3K
ci,n = ci,0 + 2K при i от 1 до n − 1
Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на 2K больше.
|
|
|
