соединить n точек на плоскости

[A'Y]

Заданы $n$ точек на плоскости. (то есть известны расстояния между каждыми двумя точками) Задача состоит в том, чтобы построить самую короткую сеть на этих с точками в вершинах.

Часто указывают такой способ (его называют "экономичным деревом"), опишу его как понял (подскажите, если где ошибся). Сначала соединяем две точки с минимальным между ними расстоянием. Потом одну из этих точек соединяем с другой, до какой расстояние минимальное. Если равнозначные возможности, то выбираем любую. И так столько шагов, сколько понадобиться чтобы соединить все $n$ точек.

Действительно ли этот метод работает? Мне он кажется очень простым и легким для алгоритмизации. Чем же он отличается от задачи коммивояжера и прочих трудных?

[longstreet]

По-моему, по этому пути работает алгоритм Крускала.

-- 27.05.2012, 16:51 --

Но это, насколько я знаю, жадный алгоритм. Так что я не знаю, всегда ли этот алгоритм даёт самое короткое соединение.

[Tanechka]

Алгоритм Прима-Краскала всегда даёт наименьшее остовное дерево...

-- 27.05.2012, 18:00 --

Краскал найдёт дерево, т. е. будут всяческие "перекрёстки", не факт, что началом пути будет этот город, да и путь обратно он не найдёт...

[A'Y]

Tanechka в сообщении #577226 писал(а):

не факт, что началом пути будет этот город

А алгоритм Дейкстры позволит находить наикратчайший путь, начиная с заданного города (вершины)?

[Tanechka]

Это и есть задача этого алгоритма - находить кратчайший путь от данного города до всех.

-- 27.05.2012, 22:05 --

Но не факт, что этот путь будет проложен через все вершины.

[dikiy]

что такое "сеть" в твоем понимании?

[A'Y]

Ну, соединительный путь. А в теории графов, я не знаю, термин "сеть" как-то зарезервирован?

[Toucan]

dikiy в сообщении #577401 писал(а):

что такое "сеть" в твоем понимании?

dikiy, строгое предупреждение за фамильярность.
Таким образом, за это нарушение у Вас уже есть замечание, предупреждение и строгое предупреждение. Надеюсь, у Вас хватит проницательности, чтобы догадаться, какие меры воздействия последуют в случае очередного рецидива.

[dikiy]

A'Y в сообщении #577427 писал(а):

Ну, соединительный путь. А в теории графов, я не знаю, термин "сеть" как-то зарезервирован?

тогда это является минимальным деревом. Оно строится за логарифмическое время от количества узлов (или ребер) (что удобнее) графа. Если не применять оптимизаций, то будет линейное время. Алгоритм Крускала или Прима.

[longstreet]

То есть, минимальное оставное дерево всегда можно найти за полиномиальное время.

[dikiy]

если обобщая то да, за полиномиальное. А точнее, то за линейное.

[longstreet]

Существуют ли алгоритм (пусть даже дающий приближённое к минимальному решение) вычисляющий для заданных координат $n$ точек координаты нужных для кратчайшего соединения точек Штейнера?

[Tanechka]

longstreet в сообщении #577451 писал(а):

То есть, минимальное оставное дерево всегда можно найти за полиномиальное время.

Да... или за квадрат, или (если

longstreet в сообщении #577454 писал(а):

Существуют ли алгоритм (пусть даже дающий приближённое к минимальному решение) вычисляющий для заданных координат точек координаты нужных для кратчайшего соединения точек Штейнера?

Алгоритм Мелзака... но он экспонециальный...
Если хотите быстро, но никакой гарантии того, что он кратчайший вам не надо - пишите обычный перебор, типа метода ветвей и границ.

[A'Y]

А метод ветвей и границ насколько хорош? Можно ли процентно оценить его отличие от идеального?

[Tanechka]

A'Y, всё смешалось в кучу.
Если вы про минимальное остовное дерево, то его можно найти за квадрат, а при использовании куч - за v*log(v).
Если вы про точки Штейнера - то тут я не помощник, сама бы я писала перебор с отсевом (читай метод ветвей и границ)... я никогда не занималась этим вопросом, поэтому знаю его поверхностно.