|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sveta Ivanova 2:5004/55.115 26 May 2002 00:42:54
To : Serge Ivanov
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
Пpивет, Serge!
Совсем случайно я увидел, что в 24 Май 02 17:31, Serge Ivanov писал Sveta
Ivanova:
SI> Если С -
SI> сложность нахождения пути в неорентированном графе, то данный
SI> алгоритм
SI> даст что-то порядка (n**2 - 2n)*C в худшем случае. Если не ошибаюсь С
SI> даже для оптимального пути является степенью n, так что сложность все
SI> равно остается полиномиальной.
Вот в том-то и проблема, что я не знаю как найти этот путь за полиномиальное
время, т.к. нужен не какой попало путь, а проходящий ч/з все вершины, т.е.
гамильтонов. Для произвольного неориентированного графа задача нахождения
гамильтонова пути NP-трудна. Hо мне неизвестно, является ли случай на плоскости
NP-трудным или полиномиально разрешимым.
Всегo наилучшегo. Sveta Ivanova.
--- GoldED+/W32 1.1.3.1
* Origin: @e:\ftn\golded\origins.tXT (2:5004/55.115)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
