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

[Лев]

Кто как ее решает?
У Wiki мнение, что нужно решать "методом ветвей и границ или методом генетических алгоритмов, а также алгоритмом муравьиной колонии".

Я сомневаюсь, что подобные вещи были знакомы первым коммивояжерам. Поэтому предлагаю "геометрическое" решение, которое не требует особых манипуляций с данными. Простое и понятное:


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

[Lider]

Я курсовую писал на эту тему)))) Решил 2мя способами, но уже не помню их(

[Лев]

Мой первый некропостинг 

Но неужели никого не заинетересовал этот алгоритм?

Или это ТАКАЯ глупость на которую даже время не стоит тратить? 

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

[zhekas]

я думаю, не помешает записать условие

[Лев]

Посыльный выезжает из города 1, ему необходимо посетить все города от 1 до N по одному разу. Найти самый кратчайший маршрут. В общем виде задача звучит как "найти алгоритм поиска маршрута для конечного натурального N".


Решена она уже не раз (и не два), но я о чем говорю...

Представим, что у героя задачи нет никаких современных вычислительных средств. Максимум - линейка (мерная нитка) и более-менее масштабная карта. Как ему тогда быть?

[Вилли ☂]

У всех уже ЖПС и ГЛОНАС    

[Вилли ☂]

Совершенно не очевидна минимальность такого решения.
Т.е. метод этот можно назвать "на глазок" 

[Лев]

Допускаю

Предложи лучше

[☭-Изделие 20Д]

Я курсовую писал на эту тему)))) Решил 2мя способами, но уже не помню их(

Когда я был маленьким, ещё учился ув институте был такой предмет ОПУП. Организация планирования и управления производством.
Так там эта хрень кажется обзывалась как - "метод встречных грузоперевозок"

[Лев]

Совершенно не очевидна минимальность такого решения.

Помоги доказать.

[Чаинка]

а может, попробовать создать два "направления", движущихся навстречу друг дружке?
Ну допустим, ближайшая к нам точка А, самая дальняя точка Я.
Найдем от точки А две ближайших Б и В, найдем ближайшие от точки Я: Э и Ю...
Потом, не оставляя "за спиной" точек, находим ближайшую к Б и ближайшую к В и т.д.
Так у нас получится замкнутый контур, когда два этих "направления" встретятся..

[Лев]

Дело в том, что "Б" может быть близко и к "В" и к "Э" - тогда не понятно, куда именно идти.

[buka]

А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут?

[☭-Изделие 20Д]

А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут?

Интереснее было бы обосновать логично подобное требование. Я кроме желания "насолить" руководству за отправку в нежелательную командировку не вижу.

[VVV]

   Если каждая вершина является вершиной или точкой стороны выпуклой оболочки, тогда обход этих вершин без пропусков вдоль границы выпуклой оболочки в одном направлении, действительно, решит задачу коммивояжера. Докажите это утверждение строго. Но в обычном случае гораздо больше вершин будет гораздо больше, чем на границе. В этом случае этот алгоритм бессилен. Алгоритм нахождения  выпуклой оболочки --- полиномиальный. Приведите пример такого алгоритма. А задача коммивояжера принадлежит классу NP-полных задач. Если найдется полиномиальный алгоритм, который решает задачу коммивояжера, то это доказывало бы, что NP=P.  Проблема NP=P? является одной из самых привлекательных в современной математике. Кстати, если NP=P, то все алгоритмы шифрования с открытым ключом можно выбросить на свалку.

А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут?

   Очевидно, что такой же сложности. Меняем расстояние на такое же с обратным знаком, тем самым сводим одну задачу к другой.