Форум умных людей

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

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


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

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

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

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

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

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

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

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


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

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

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

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

Допускаю :)

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

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

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

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

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

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

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

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

Основная проблема в том, что для построения выпуклой оболочки нужно, чтобы вершины укладывались в метрическое пространство.
То есть Расстояние(А,Б) + Расстояние(Б,В) >= Расстояние(А,В)
В задаче коммивояжера это условие в общем случае может не выполняться. Пускай у вас есть симметричная матрица N*N. Что является ее выпуклой оболочкой?

Расстояние (А,Б,В), я бы сказал  :-\

задачу нужно решать пчелой
http://www.popmech.ru/article/8071-pchelyi-i-kommivoyazheryi/ (http://www.popmech.ru/article/8071-pchelyi-i-kommivoyazheryi/)

В принципе, неплохо.

Расположить цветки и улей в соответствии с городами на карте и повторить подвиг пчел :)

Для средневекового торговца - самое оно  :good3:

Для решения данной задачи можно использовать следующий алгоритм. Пусть всего у нас N точек и они соединены последовательно. Выберем 3 числа K,L,M. Возьмем точку с номером K. Вырежем цепочку точек начиная с K-й и всего L(L было ограничено значением N/3). Точку с номером K-1 cоединим с точкой с номером K+L, а вырезанную цепочку(возможно в обратном порядке) вставим в разрыв между точками с номерами K+L+M и K+L+M+1 (все числа берутся по модулю N). Посмотрим улучшился ли результат. Находим тройку (K,L,M) при которой происходит максимальное сокращение общей длины и производим перестановку. Повторяем эту прцедуру до тех пор пока такую тройку чисел еще можно найти. Результат получается вполне удовлетворительный. Для 20 точек ответ получается мгновенно, для 50 программа работает несколько минут.
Более быстрые алгоритмы для большого количества точек давали гораздо худший результат. В данном случае визуально результат кажется оптимальным.
(http://s51.radikal.ru/i134/1105/db/550890617fba.jpg) (http://www.radikal.ru)

Мы рассматриваем данную задачу в парадигме темного средневековья :)

Спасибо за рисунок!

Заметьте, моим "на глазок" алгоритмом мы приходим к такому же решению практически без вычислений.

Задача состоит в том чтобы найти именно наилучшее решение. Приблизительно лучшее всегда почти очевидно в случае если мы имеем дело с точками на плоскости где всегда AB=BA и AB+BC>AC.

Не уверен... Думаю, что обратная задача гораздо сложнее...

Кроме того, пчелами ее не решить :)

Обратная задача совершенно такой же сложности. В программе вместо "<" ставим ">".
Скачать CommiVoyageur.exe с WebFile.RU (http://webfile.ru/5508523)

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

он!