2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 19:34 
Аватара пользователя
В принципе решаема. Тупым перебором. А может быть даже есть какие-то методы.

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 19:39 
А может, это из серии: "От перемены мест слагаемых..."?

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 19:45 
Аватара пользователя
Даже на прямой от перемены мест ещё как, а в многомерном пространстве?

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 19:51 
Я, как понимаю, отрезки - это, в некотором роде, разности координат.
А какая разница, как считать суммарную разность одного набора относительно другого?

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

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

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 19:56 
Ну перебор не интересует.
То что минимум и максимум должен быть, очевидно, как у любого конечного множества.
Но, хотелось бы поосмысленней

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

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 20:03 
Аватара пользователя
А на прямой? $\{2;7\}$ и $\{3;12\}$
А, понял. Но там же длины.

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 20:04 
Координаты могут быть везде: и на прямой, и на плоскости, и в пространстве.

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

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 21:13 
Аватара пользователя
Соединение самых отдалённых (взяли максимум по всем а и по всем бэ - провели один отрезок - повторить...) не гарантирует максимальной суммы, а так-то всё хорошо.

 
 
 
 Re: Решаема задача или нет
Сообщение02.03.2010, 21:53 
Батороев в сообщении #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$

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

 
 
 
 Re: Решаема задача или нет
Сообщение03.03.2010, 08:52 
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}$.

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

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

 
 
 
 Re: Решаема задача или нет
Сообщение03.03.2010, 09:32 
Батороев
Вы правы. У меня ошибка.
$a_2(1,4,3),b_1(-1,4,3)$
Вместе с тем, мой вариант - это всего лишь опровержение.

 
 
 
 Re: Решаема задача или нет
Сообщение03.03.2010, 11:24 
gris
Прочитайте по ссылке, которую я привёл выше, там всё написано. Никакая она не NP-трудная.

 
 
 [ Сообщений: 27 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group