Kubinator
Новенький
Offline
Сообщений: 40
СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 12
|
|
� Ответ #15 : Апрель 10, 2011, 20:59:36 � |
|
Основная проблема в том, что для построения выпуклой оболочки нужно, чтобы вершины укладывались в метрическое пространство. То есть Расстояние(А,Б) + Расстояние(Б,В) >= Расстояние(А,В) В задаче коммивояжера это условие в общем случае может не выполняться. Пускай у вас есть симметричная матрица N*N. Что является ее выпуклой оболочкой?
|
|
|
Записан
|
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #16 : Апрель 11, 2011, 12:43:07 � |
|
Основная проблема в том, что для построения выпуклой оболочки нужно, чтобы вершины укладывались в метрическое пространство. То есть Расстояние(А,Б) + Расстояние(Б,В) >= Расстояние(А,В)
Расстояние (А,Б,В), я бы сказал
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #17 : Май 09, 2011, 02:47:58 � |
|
задачу нужно решать пчелой //текст доступен после регистрации//
|
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
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #18 : Май 10, 2011, 20:32:29 � |
|
В принципе, неплохо. Расположить цветки и улей в соответствии с городами на карте и повторить подвиг пчел Для средневекового торговца - самое оно
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #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 программа работает несколько минут. Более быстрые алгоритмы для большого количества точек давали гораздо худший результат. В данном случае визуально результат кажется оптимальным. //текст доступен после регистрации//
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #20 : Май 16, 2011, 14:27:39 � |
|
Мы рассматриваем данную задачу в парадигме темного средневековья
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #21 : Май 16, 2011, 14:34:15 � |
|
Спасибо за рисунок!
Заметьте, моим "на глазок" алгоритмом мы приходим к такому же решению практически без вычислений.
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #22 : Май 16, 2011, 15:08:57 � |
|
Задача состоит в том чтобы найти именно наилучшее решение. Приблизительно лучшее всегда почти очевидно в случае если мы имеем дело с точками на плоскости где всегда AB=BA и AB+BC>AC.
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #23 : Июнь 27, 2011, 00:29:26 � |
|
А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут? Очевидно, что такой же сложности. Меняем расстояние на такое же с обратным знаком, тем самым сводим одну задачу к другой. Не уверен... Думаю, что обратная задача гораздо сложнее...
|
|
|
Записан
|
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #24 : Июнь 28, 2011, 13:40:03 � |
|
Кроме того, пчелами ее не решить
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #25 : Август 25, 2011, 00:33:18 � |
|
А вот интересно, насколько сложнее обратная задача - выбрать наиболее длинный маршрут? Очевидно, что такой же сложности. Меняем расстояние на такое же с обратным знаком, тем самым сводим одну задачу к другой. Не уверен... Думаю, что обратная задача гораздо сложнее... Обратная задача совершенно такой же сложности. В программе вместо "<" ставим ">". //текст доступен после регистрации//
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #26 : Август 25, 2011, 11:31:51 � |
|
Кто еще не понял, что мы решаем ее здесь средневековыми методами?
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #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
|
|
|
|