Соединить точки на плоскости набором отрезков миним. длины

[Sasha2]

Вот хотелось бы узнать, задача вот такого плана решаема или нет
На плоскости или в пространстве даны два набора точек по $n$ в каждом: $a_1, a_2,..., a_n$ и $b_1, b_2,..., b_n$. Требуется соединить точки первого набора с точками второго набора отрезками так, чтобы общая длина полученных таким образом $n$ отрезков была максимальной или минимальной.
Одна точка каждого набора может быть соединена только с одной точкой другого. Это требование относится к точкам обеих наборов.
Координаты всех точек известны.

[gris]

В принципе решаема. Тупым перебором. А может быть даже есть какие-то методы.

[Батороев]

А может, это из серии: "От перемены мест слагаемых..."?

[gris]

Даже на прямой от перемены мест ещё как, а в многомерном пространстве?

[Батороев]

Я, как понимаю, отрезки - это, в некотором роде, разности координат.
А какая разница, как считать суммарную разность одного набора относительно другого?

-- Вт мар 02, 2010 22:53:15 --

Только я имею в виду с учетом того, что знаки учитываются.
Если не учитываются, то это - не из упомянутой серии.

[Sasha2]

Ну перебор не интересует.
То что минимум и максимум должен быть, очевидно, как у любого конечного множества.
Но, хотелось бы поосмысленней

P.S. А причем тут разность координат, они же не на прямой, а на плоскости или в пространстве. Если хотите, то можно написать и так $a_i=a_i(x_i,y_i,z_i)$

[gris]

А на прямой? $\{2;7\}$ и $\{3;12\}$
А, понял. Но там же длины.

[Батороев]

Координаты могут быть везде: и на прямой, и на плоскости, и в пространстве.

Я сначала не въехал в условие. Теперь дошло.
Тогда, по-видимому, алгоритм таков, что соединяем сначала самые отдаленные. При этом мы "захватываем" промежутки, которые не вошли бы в отрезки при других соединениях. Из оставшихся опять выбираем самые отдаленные и т.д.

[ИСН]

Соединение самых отдалённых (взяли максимум по всем а и по всем бэ - провели один отрезок - повторить...) не гарантирует максимальной суммы, а так-то всё хорошо.

[smoll82]

Батороев в сообщении #294004 писал(а):

Тогда, по-видимому, алгоритм таков, что соединяем сначала самые отдаленные. При этом мы "захватываем" промежутки, которые не вошли бы в отрезки при других соединениях. Из оставшихся опять выбираем самые отдаленные и т.д.

$a_1(0,0,0),a_2(0,4,-1),b_1(0,4,1),b_2(0,8,0)$,
$|\overrightarrow{a_1 b_1}|=\sqrt{26}, |\overrightarrow{a_1 b_2}|=8,|\overrightarrow{a_2 b_1}|=2,|\overrightarrow{a_2 b_2}|=\sqrt{26}$
$\max({|\overrightarrow{a_1 b_1}|,|\overrightarrow{a_1 b_2}|,|\overrightarrow{a_2 b_1}|,|\overrightarrow{a_2 b_2}|})=8$ и
$|\overrightarrow{a_1 b_2}|+|\overrightarrow{a_2 b_1}|=10$, но
$|\overrightarrow{a_1 b_1}|+|\overrightarrow{a_1 b_2}|=2\sqrt{26}>10$

[Cave]

Это задача о назначениях, в английской Вики тут: http://en.wikipedia.org/wiki/Assignment_problem
Решается за $O(n^4)$, а если чуть больше усилий приложить, то и за $O(n^3)$ можно.

[Батороев]

smoll82 в сообщении #294038 писал(а):

Батороев в сообщении #294004 писал(а):

Тогда, по-видимому, алгоритм таков, что соединяем сначала самые отдаленные. При этом мы "захватываем" промежутки, которые не вошли бы в отрезки при других соединениях. Из оставшихся опять выбираем самые отдаленные и т.д.

$a_1(0,0,0),a_2(0,4,-1),b_1(0,4,1),b_2(0,8,0)$,
$|\overrightarrow{a_1 b_1}|=\sqrt{26}, |\overrightarrow{a_1 b_2}|=8,|\overrightarrow{a_2 b_1}|=2,|\overrightarrow{a_2 b_2}|=\sqrt{26}$
$\max({|\overrightarrow{a_1 b_1}|,|\overrightarrow{a_1 b_2}|,|\overrightarrow{a_2 b_1}|,|\overrightarrow{a_2 b_2}|})=8$ и
$|\overrightarrow{a_1 b_2}|+|\overrightarrow{a_2 b_1}|=10$, но
$|\overrightarrow{a_1 b_1}|+|\overrightarrow{a_1 b_2}|=2\sqrt{26}>10$

Ваш контр-пример мне не понятен.
Во-первых, если все точки лежат в одной плоскости, зачем давать объемные координаты?
Во-вторых, по заданным Вами координатам у меня получается длина отрезков:
$a_1b_2=8$; $a_2b_1=2$
$a_1b_1=a_2b_2= \sqrt {17}$
$ 8+2>2\sqrt {17}$.

Вместе с тем, мой вариант - это всего лишь предположение. Я на нем не настаиваю.

[gris]

Она может быть и о назначениях, только далеко не линейная и относится к разряду NP-hard, уж если на то пошло. Может быть если известно что о наборах, можно что-то придумать. Например, оба набора содержатся в не пересекающихся шарах, а не перемешаны.

[smoll82]

Батороев
Вы правы. У меня ошибка.
$a_2(1,4,3),b_1(-1,4,3)$
Вместе с тем, мой вариант - это всего лишь опровержение.

[Cave]

gris
Прочитайте по ссылке, которую я привёл выше, там всё написано. Никакая она не NP-трудная.