Соединить n точек в 3D

[A'Y]

Задано расположение $n$ точек в трёхмерном пространстве. Через них нужно провести линию кратчайшей длины. Как это сделать?

-- 05.05.2012, 19:20 --

Задачу предполагается решить в общем виде, так что перебрать всевозможные линии не получится. Понятно, что эта линия $-$ ломаная (то есть будет состоять из отрезков). Но в каком порядке соединять? Не знаю, имеет ли задача решение.

[Yu_K]

http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0 почитайте про подобные плоские задачи.

[A'Y]

Есть ли сравнение методов решения, которые там указаны?
И как быть, если в задаче коммивояжера требуется учесть кривизну местности?

-- 05.05.2012, 19:55 --

Напомню, что задача поставлена в 3D.

[A'Y]

Интересно, это может быть каким-то образом связано с теорией узлов

-- 06.05.2012, 02:09 --

Буду рад любым идеям.

[A'Y]

Или посоветуйте ещё чего-нибудь почитать, пожалуйста.

[Xaositect]

Задача коммивояжера ставится для произвольных весов ребер, не обязательно даже удовлетворяющих аксиомам метрики. Для метрической задачи существуют полиномиальные приближенные алгоритмы, а для общей - нет.
Про практическую эффективность алгоритмов не знаю.

[A'Y]

Задача метрическая. В смысле, неравенство треугольника выполняется.

-- 06.05.2012, 11:40 --

А что значит "произвольный вес ребра"?