|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sveta Ivanova 2:5004/55.115 27 May 2002 09:20:08
To : Ruslan Shevelyov
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
Пpивет, Ruslan!
Совсем случайно я увидел, что в 26 Май 02 09:31, Ruslan Shevelyov писал Serge
Ivanov:
RS> Проверка существования пути из одной вершины в другую
RS> действительно осуществляется полиномиальным алгоритмом.
RS> Hо здесь речь идёт о простом пути, проходящем через все
RS> вершины графа, т.е. о гамильтоновом пути (aka решение
RS> "задачи коммивояжёра"). Полиномиальные алгоритмы
RS> нахождения такого пути неизвестны (хотя и не доказано,
RS> что таких алгоритмов не существует).
То, что задача гамильтонова пути в произвольном графе NP-трудна,это, конечно
известно. А может ли нам помочь тот факт, что точки даны на плоскости? Известно
ли что-нибудь о трудности находжения гамильтонова пути в геометрическом графе?
Всегo наилучшегo. Sveta Ivanova.
--- GoldED+/W32 1.1.3.1
* Origin: @e:\ftn\golded\origins.tXT (2:5004/55.115)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
