Задача коммивояжёра

[квит]

Приобрел таки книжку Ершова, красиво сделано, но сложно написано - чем дальше тем он короче объясняет по коду, сам код не дает, иногда приходится сильно думать)))

Реализовал из его примеров задачу коммивояжера - методом муравьиной колонии

tsp1.JPG

[квит]

Свой вариант - методом случайной парной перестановки

tsp2.JPG

[Ирис]

А чем "задача коммивояжера" отличается от классической "транспортной задачи"??

[квит]

Транспортная задача, упрощенно - есть N складов и M магазинов, надо товары из складов развести по магазинам за минимальную стоимость


Задача коммивояжера - надо обойти все города по минимальному маршруту

https://ru.wikipedia.org/wiki/%D0%A2...B0%D1%87%D0%B0

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида.[1][2] Её можно рассматривать как задачу об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году[4]. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[5]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

https://ru.wikipedia.org/wiki/%D0%97...80%D0%BE%D0%B4.

Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так:

Мы называем задачей посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.

Вскоре появилось известное сейчас название задача странствующего торговца (англ. traveling salesman problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.

Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.

Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 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 % больше оптимальной.

[BOBA]

Квит, а ты где то программистские задачки решал?

[BOBA]

а что кстати за книжка и из какой системы скрины?

[квит]

Сообщение от BOBA

а что кстати за книжка и из какой системы скрины?

А Фавн давал наводку
http://project.megarulez.ru/forums/s...2&postcount=10

система нетлого

[квит]

Сообщение от BOBA

Квит, а ты где то программистские задачки решал?

в смысле, тут, на форуме, или вообще в принципе???)))

какие то где то решал, да

я даже как то школьников немного пообучал в плане подготовки к егэ и к олимпиадам

[квит]

в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))

[BOBA]

А. Понятно. Почти вдохновился тоже что то порешать.... Как пойдет.