Страниц: 1 [2]
  Печать  
Автор Тема: Задача коммивояжера  (Прочитано 13393 раз)
0 Пользователей и 1 Гость смотрят эту тему.

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

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


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

Сообщений: 40

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 12


Просмотр профиля Email
Ответ #15 : Апрель 10, 2011, 20:59:36 �

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

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #16 : Апрель 11, 2011, 12:43:07 �

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

Расстояние (А,Б,В), я бы сказал  Undecided
Записан

В действительности все не так, как на самом деле
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #17 : Май 09, 2011, 02:47:58 �

задачу нужно решать пчелой
//текст доступен после регистрации//

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #18 : Май 10, 2011, 20:32:29 �

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

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

Для средневекового торговца - самое оно  Гуд
Записан

В действительности все не так, как на самом деле
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #19 : Май 16, 2011, 14:25:00 �

Для решения данной задачи можно использовать следующий алгоритм. Пусть всего у нас 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 программа работает несколько минут.
Более быстрые алгоритмы для большого количества точек давали гораздо худший результат. В данном случае визуально результат кажется оптимальным.
//текст доступен после регистрации//

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #20 : Май 16, 2011, 14:27:39 �

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

В действительности все не так, как на самом деле
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #21 : Май 16, 2011, 14:34:15 �

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

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

В действительности все не так, как на самом деле
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #22 : Май 16, 2011, 15:08:57 �

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

Зачем откладывать на завтра то, что можно отложить на послезавтра?
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #23 : Июнь 27, 2011, 00:29:26 �

    
А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут? Wink
   Очевидно, что такой же сложности. Меняем расстояние на такое же с обратным знаком, тем самым сводим одну задачу к другой.
Не уверен... Думаю, что обратная задача гораздо сложнее...
Записан
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #24 : Июнь 28, 2011, 13:40:03 �

Кроме того, пчелами ее не решить Smiley
Записан

В действительности все не так, как на самом деле
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #25 : Август 25, 2011, 00:33:18 �

   
А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут? Wink
   Очевидно, что такой же сложности. Меняем расстояние на такое же с обратным знаком, тем самым сводим одну задачу к другой.
Не уверен... Думаю, что обратная задача гораздо сложнее...
Обратная задача совершенно такой же сложности. В программе вместо "<" ставим ">".
//текст доступен после регистрации//
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #26 : Август 25, 2011, 11:31:51 �

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

В действительности все не так, как на самом деле
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #27 : Август 25, 2011, 11:56:59 �

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Страниц: 1 [2]
  Печать  
 
Перейти в: