 |
|
|
 
|
|
Битоническая евклидова задача о коммивояжере 
| max07 |
|
|||
|
Бывалый  Профиль Группа: Участник Сообщений: 178 Регистрация: 21.12.2004 Репутация: нет Всего: нет |
Здрасте всем!
Может кто знает что про этот метод? Если есть ссылки на алгоритм решения поделитесь. |
|||
|
||||
Загрузка ...
| Bitter |
|
|||
 Опытный лентяй Профиль Группа: Завсегдатай Сообщений: 1209 Регистрация: 15.8.2004 Где: Харьков, Ukraine Репутация: 4 Всего: 27 |
Это метод такой "Биотонический"? Или Вы имеете в виду просто как решить задачу коммиваяжера?
|
|||
|
||||
| max07 |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 178 Регистрация: 21.12.2004 Репутация: нет Всего: нет |
Именно этот метод, не просто задача коммиваяжера
|
|||
|
||||
| MBo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 5 Всего: 18 |
В Кормене указано, что эта задача решается динамическим программированием за время O(n^2) (задача 15.1)
Насколько я понимаю, нужно отсортировать точки по X-координате, и найти пару непересекающихся кратчайших путей из 1 в N-ю точку |
|||
|
||||
| max07 |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 178 Регистрация: 21.12.2004 Репутация: нет Всего: нет |
Да это то что надо. Может есть алгоритм? псевдокодом хотябы?
|
|||
|
||||
| esperant0 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
Алгоритм обычная идея динамического програмирования. Определите целевую ф-ию. Определите переменные выбора. Напишите рекурсивное выражение связывающее задачу размероности к , с задачей меньшей размерности. -------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0432 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |