Re: Гамильтонов цикл

From

Mike Girkin (2:5055/177.22)

To

Artur Mogozov ()

Date

2003-03-20T22:03:10Z

Area

RU.ALGORITHMS

    Да пребудет с тобой тьма, Artur !

20 Мар 03 19:01, Artur Mogozov закинул письмецо для All:
 AM>  Есть ли не полнопереборный алгоритм поиска сабжа в графе, который
 AM> работал бы за разумное время, хотя бы на 1000 вершинах?
Если тебе просто гамильтонов цикл найти, то есть. Есть специальная теорема,
наподобии теоремы об Эйлеровом цикле, и тогда ты сможешь определить есть ли он
вообще, а найти в этом случае довольно просто. Если тебе еще и минимальный
найти, то это NP-полная задача, и тут только перебор (ну или почти перебор, что
позволяет сократить число операций в несколько раз, но это будет при 10000 ыерши
несущественно)

                                       Тьма за нас. Mike .

... Если я сказал: "Не брал!", значит не отдам.
--- GoldED+/W32 1.1.5-030118
 * Origin:  (2:5055/177.22)