ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Prokopyev                       2:5020/400     21 May 2002  18:52:00
 To : Boyarintsev Pavel
 Subject : Re: Поиск наименьшего маpшpyта
 -------------------------------------------------------------------------------- 
 

 
 бррр...
 это случайно не задача коммивояжера? или я глючу?:)
 
 NP-полная задача - соответственно точного полиномиального алгоритма нет
 так что полный перебор или
 приближенные полиномиальные алгоритмы
 
 посмотри здесь что лучшее может быть
 
 http://www.nada.kth.se/~viggo/wwwcompendium/node103.html
 
 самый тупой приближенный - по моему через построение 
 минимального остовного дерева ... вообщем по моему в Гэри-Джонсоне есть
 подробное описание
 Boyarintsev Pavel wrote:
 
 > 
 >                     Hi All!
 > 
 > Hyжен алгоpитм нахождения наименьшего маpшpyта по гоpодам, выехав из 1-го
 > гоpода, пpоехать чеpез все остальные гоpода обpатно не воpачиваясь. Даны все
 > pасстояния междy гоpодами, в одном гоpоде нельзя бывать дважды. Количество
 > гоpодов - пpоизвольное.
 > 
 > Bye All!
 > 
 > ... А ты воспользовался пакетом ...?
 
 -- 
 Regards,
 Oleg Prokopyev
 OAP4-RIPE
 --- ifmail v.2.15dev5
  * Origin: UA.GU (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Поиск наименьшего маpшpyта   Boyarintsev Pavel   19 May 2002 12:42:04   Re: Поиск наименьшего маpшpyта   Oleg Prokopyev   21 May 2002 18:52:00   Re: Поиск наименьшего маpшpyта   Alexander Kazak   28 May 2002 22:57:16