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

[Sasha2]

Ну меня интересовало только теоретическое решение, а не машинное.
То есть я так понял теоретически такая задача не решабельна (ни синтетически, ни аналитически).

[ИСН]

Sasha2, Вы что-то своё под этим понимаете? Что значит "теоретически не решабельна"?

[gris]

Теоретически она как раз решабельна. Ибо перебор это чисто теоретическое средство при больших значениях n. Теоретически есть максимум и минимум.

А вот практически, то есть с применением методов, скажем, линейного программирования, она как раз не решается, ибо нелинейна.

[Sasha2]

Ну перебор это не то.
А теоретически - это означает следующее:
Предположим мы можем высказать, какое то утверждение о точках первого набора, ну например, что все они являются вершинами выпуклого многогранника. И то же самое относительно второго набора.
Далее берется, либо точка еще, либо прямая или еще како-то геометрический объект и нужное сочетание пар выстраивается в зависимости от соотношения этих точек с этим объектом.
Вот Вы же в самом начале высказывали идеи о том, что надо брать самые далекие или еще какие-то.
Но может нужен тритий (а может и еще какой-то обеъкт), чтобы сформировать правильное суждение.
Я приношу извинения за такое сумборное представление, но наверно старшие товарищи поправят меня, поняв суть идеи.

[smoll82]

Введём такие подстановки
$ A_m = \left( \begin{array}{cccc} 1 & 2 & \ldots & n\\ \alpha_1 & \alpha_2 & \ldots & \alpha_n\\ \end{array} \right) $ где, первая строка - идексы в обозначениях точек $a_i$, вторая строка - некоторая перестановка из индексов в обозначениях точек $b_i$, и $i=1,2,\ldots,n$,$m=1,2,\ldots,n!$
Введём соответствующую сумму
$S_m=\sum\limits_{i=1}^n |\overrightarrow{a_i}-\overrightarrow{b_{\alpha_i}}| $
$max(S_1,S_2,\ldots,S_m)=S$
А соответствующая ей подстановка $A$ и будет решением.

Если умножить справа тождественную подстановку $E$ на транспозицию $T_{k,l}$ получим новую подстановку
$ A_m=\left( \begin{array}{cccccсс} 1 & \ldots & k & \ldots & l & \ldots & n\\ \alpha_1 & \ldots & \alpha_l & \ldots & \alpha_k & \ldots & \alpha_n\\ \end{array} \right) $
Вопрос о сравнении сумм $S_E$ и $S_m$ сводится к вопросу о сравнении выражений соответственно
$|\overrightarrow{a_k}-\overrightarrow{b_{\alpha_k}}|+|\overrightarrow{a_l}-\overrightarrow{b_{\alpha_l}}|$ и $|\overrightarrow{a_k}-\overrightarrow{b_{\alpha_l}}|+|\overrightarrow{a_l}-\overrightarrow{b_{\alpha_k}}|$.
К любой подстановке можно перейти путём умножения справа тождественной подстановки на транспозиции $T_p$, где $p=(1,2,\ldots,q)$ и, в общем случае $q\leqslant n-1$.
С учётом ассоциативности умножения подстановок можно записать:
$A_m=E*\left(\prod\limits_{i=1}^q T_p\right)$.
Остаётса найти такое разложение $A_m$ по $T$ при котором $A_m=A$

Я сам не придумал ещё как его отыскать.

[Sasha2]

Ну нет - это не такое решение, которое хотелось бы видеть.
А самое главное так это, то, что в конечном счете такой метод ну максимум может срабатывать на серих от 100 до 200 точек.
И тем более, если, например, мы в одной серии заменим одну точку, он не позволит рационально прийти к новому решению, равно как не позволит дать ответы на такие вопросы, как типа, изменится ли решение, если мы чуть-чуть подвигаем эти точки.
Грубо говоря, решение в одном случае, это всего лишь решение для данного случая, МЕТОДА ОБЩЕГО, КАК Я ПОНЯЛ НЕТ.

[Профессор Снэйп]

Кстати, а если оба набора $a_1 < a_2 < \ldots < a_n$ и $b_1 < b_2 < \ldots < b_n$ на числовой прямой, то всегда ли минимум

$$ \min\left\{ \sum_{i = 1}^n | a_i - b_{\sigma(i)} | : \sigma \in S_n \right\} $$

будет достигаться на тождественной перестановке $\sigma: i \mapsto i$?

-- Ср мар 03, 2010 21:18:22 --

Для $n=2$ вроде всегда (разбор шести случаев).

[Cave]

Попытка достучаться №3, она же последняя: венгерский алгоритм.

[Sasha2]

Да Вы знаете это все не то.
Вопрос, который я задавал (вот в моем понимании) не сводится к такому переборному решению.
Если хотите он вот ближе гораздо к такому вопросу:
Существует ли такая теорема, звучащая примерно так: Для того чттобы n точек на плоскости являлись вершинами выпуклого многоугольника необходимо и достаточно ...
Имеется в виду (интутитивно кажется) более глубокое использование информации о координатах точек, а не только той, что они находятся там.

[venco]

Sasha2, вопрос, который вы задавали (в моём понимании) как раз сводится к венгерскому алгоритму.
Про выпуклые многоугольники не понял.

[ИСН]

Sasha2, я, кажется, отдалённо прозреваю за этим некий туманный смысл, но он скорее всего развеется и исчезнет при попытке придать ему математическую строгость, которой пока что и не пахнет.
А может, и нет.

[Sasha2]

Да ладно. Давайте ее закроем. Я и сам вижу, что пока знаний у меня нет даже ни на то чтобы решать такие задачи, но даже и на то, что ставить такие задачи правильно.