ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Mike Girkin                          2:5055/177.22  20 Mar 2003  23:03:10
 To : Artur Mogozov
 Subject : Re: Гамильтонов цикл
 -------------------------------------------------------------------------------- 
 

     Да пребудет с тобой тьма, Artur !
 
 20 Мар 03 19:01, Artur Mogozov закинул письмецо для All:
 
  AM>  Есть ли не полнопереборный алгоритм поиска сабжа в графе, который
  AM> работал бы за разумное время, хотя бы на 1000 вершинах?
 
 Если тебе просто гамильтонов цикл найти, то есть. Есть специальная теорема,
 наподобии теоремы об Эйлеровом цикле, и тогда ты сможешь определить есть ли он
 вообще, а найти в этом случае довольно просто. Если тебе еще и минимальный
 найти, то это NP-полная задача, и тут только перебор (ну или почти перебор, что
 позволяет сократить число операций в несколько раз, но это будет при 10000 ыерши
 несущественно)
 
                                        Тьма за нас. Mike .
 
 ... Если я сказал: "Hе брал!", значит не отдам.
 --- GoldED+/W32 1.1.5-030118
  * Origin:  (2:5055/177.22)
 
 

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

Тема:    Автор:    Дата:    Гамильтонов цикл   Artur Mogozov   20 Mar 2003 20:01:17   Гамильтонов цикл   Stanislav Shwartsman   20 Mar 2003 17:43:16   Re: Гамильтонов цикл   Mike Girkin   20 Mar 2003 23:03:10