|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sveta Ivanova 2:5004/55.115 02 Jun 2002 01:36:38
To : Ruslan Shevelyov
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
Пpивет, Ruslan!
Совсем случайно я увидел, что в 28 Май 02 22:30, Ruslan Shevelyov писал Sveta
Ivanova:
SI>> То, что задача гамильтонова пути в произвольном графе
SI>> NP-трудна,это, конечно известно. А может ли нам помочь тот факт,
SI>> что точки даны на плоскости?
RS> Hавряд ли; в тех алгоритмах поиска гамильтонова пути,
RS> описания которых я видел, под графом понимается набор
RS> из двух множеств: множества вершин v1...vn и множества
RS> дуг -- пар вида (vi,vj). Как видите, ни плоскости, ни
RS> длины рёбер в этом определении не наблюдаются.
Они присутствуют в определении геометрического графа (хотя, может быть, я
использовала неправильный термин). Под геометрическим графом я подразумевала
граф, вершины которого можно представить точками на плоскости так, что пара
вершин соединяется ребром <=> расстояние между соответствующими точками не
превосходит некоторой величины d.
Hо вроде уже поступила информация, что для геометрических графов задача тоже
NP-трудна. Так что вопрос можно считать закрытым.
To All: Спасибо всем ответившим!
Всегo наилучшегo. Sveta Ivanova.
--- GoldED+/W32 1.1.3.1
* Origin: @e:\ftn\golded\origins.tXT (2:5004/55.115)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
