Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.02.2010, 16:31
bazingo

 
Сообщений: n/a

Минимальный вес гамильтонова цикла в полном графе
Дан полный взвешенный граф размерности n <= 21. Требуется найти минимальный вес гамильтонова цикла за время, не превышающее 20 с, и затратах памяти не более 256 мб.
  #2  
Старый 21.02.2010, 20:38
гость

 
Сообщений: n/a

Давайте называть вещи своими имена, это называется TSP (traveling salesman problem)! И ссылку на первоисточник задачи - в студию!

Динамическое программирование решит эту задачу за O(n^2 2^n) времени и O(n 2^n) памяти. Если вес ребра - 64-битное число (double или целое), 256 Mb не хватит, и вам придется совмещать частичный перебор с динамическим программированием.
  #3  
Старый 21.02.2010, 20:42
гость

 
Сообщений: n/a

Сообщение от bazingo Посмотреть сообщение
за время, не превышающее 20 с
это где? на каком-нибудь 80386? ARM'е в сотовом телефоне? Core i7? кластере с тыщями машин???
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Минимальный разрез гость Графы 7 01.06.2010 19:24
поиск цикла максимальной длинны в графе гость Графы 2 21.12.2008 04:00
Матроиды и минимальный разрез гость Графы 0 25.10.2008 23:48
Поиск эйлерова цикла в графе,ошибка гость Реализация, исходники, языки 0 21.11.2007 22:40
нахождение цикла в графе reinkarn Графы 1 09.03.2007 05:50