Не совсем пятничная задачка, но очень интересно как решать

← →
DillerXX © (2007-04-14 22:36) [0]

Даны точки на плоскости. Поставить такую новую точку (x;y), что сумма расстояний от всех существующих до неё было бы минимально.
У меня была идея - выбирать горизонтальную прямую, с помощью дифференцирования ф-ции суммы растояний узнать X с минимальной суммой расстояний. А затем шуровать тернарным поиском по оси Y.. но видимо это я фигню придумал. Может кто знает как решить?

← →
Чапаев © (2007-04-14 22:51) [1]

А не центр ли тяжести это будет?

← →
Zod (2007-04-14 22:53) [2]

DillerXX © (14.04.07 22:36)

Производная от функции двух переменных/дифференцирование по-частям?
Только как аналитически выразить такую функцию, интересно?

← →
DillerXX © (2007-04-14 23:06) [3]

> А не центр ли тяжести это будет?

Возможно, если бы у нас был выпуклый многоугольник. А здесь - точно нет.

← →
Vendict © (2007-04-14 23:19) [4]

если рассуждать логически:

минимальное расстояние = мин по х. + мин по у.
т. е. ищем расстояние на прямой.
так это наверняка должно быть просто среднее арифмитическое.
хотя этот жадный алгоритм может и не пройти..

← →
Mystic © (2007-04-15 02:19) [5]

Хм... Ничего не понимаю... Это обычная оптимизационная задача, для которой существует куча методов... Как я понял, целевая функция у тебя

L = \sum_i \sqrt{(x-x_i)^2 + (y-y_i)^2} \to \min

Соответственно надо найти минимум. Тут подойдут любые методы, тем более, что известно и более-менее хорошее начальное приближение---центр масс. Можно попытаться и решить аналитически:

{\partial L \over \partial x} =
\sum_i { x - x_i \over \sqrt {(x-x_i)^2 + (y-y_i)^2}} = 0

аналогично

{\partial L \over \partial x} =
\sum_i { y - y_i \over \sqrt {(x-x_i)^2 + (y-y_i)^2}} = 0

И можно решать эту систему, например итерационным методом. Действительно, для первого уравнения если разбить сумму на две, вынести из первой x за cкобки, то получим x = f_1(x, y), а из второго y = f_2(x,y). Начальное приближение---центр масс. И вперед! Только надо учесть, что в случае, когда x совпадает с некоторым x_j, то надо для соответствующего слагаемого брать предел. Как нетрудно видеть, он равен единице.

← →
Думкин © (2007-04-15 04:57) [6]

> если рассуждать логически:
>
> минимальное расстояние = мин по х. + мин по у.

Это не логически ниразу.

← →
Думкин © (2007-04-15 05:26) [7]

> Думкин © (15.04.07 04:57) [6]

Беру слова обратно. Для функций данного вида логически. :)

← →
Думкин © (2007-04-15 05:30) [8]

Хотя нет.
Все-таки не мин суммы расст по x,y а мин суммы квадратов расст по х,y.

← →
vain © (2007-04-15 13:30) [9]

Это центр тяжести.

← →
Mystic © (2007-04-15 14:35) [10]

> Это центр тяжести.

Нет. Центр тяжести получим в том случае, когда мы будем минимизировать сумму квадратов расстояний (МНК).

← →
Pavia © (2007-04-15 16:19) [11]

Это цент масс. Или мат ожедание каму как угодно.

Нам нужен min(сумма(sqrt((xi-x)^2+(yi-y)^2)))
Ясно что сумма будет минимальной. Если будет минимальной
min(сумма(((xi-x)^2+(yi-y)^2))) отсюда можем разделить на две состовляющих
min(сумма((xi-x)^2))=min(сумм(xi^2)-2*сумм(xi)*x+n*x^2)
min(сумма((yi-y)^2))=min(сумм(yi^2)-2*сумм(yi)*x+n*y^2)
переобозначем
min(a1*x^2+b1*x+c1)
min(a2*y^2+b2*y+c2)
минимум будет в центре парабалы. Берем производную. Выражаем x,y и делаем обратную подстановку.
2*a1*x+b1=0 => x=-b1/(2*a1) => x=сумм(xi)/n
2*a2*y+b2=0 => y=-b2/(2*a2)=> y=сумм(yi)/n
Что и требовалось доказать минимум и будет в центре масс.

← →
Mystic © (2007-04-15 19:01) [12]

> Ясно что сумма будет минимальной. Если будет минимальной min(сумма(((xi-x)^2+(yi-y)^2)))

А доказать?

>А доказать?

А не получится :-)

Предлагаю рассмотреть пример попроще.
Все сразу станет ясно... или не ясно ))

Итак, наш пример: 3 точки с координатами (1,0) (-1,0) (0,y), y>0
Т.е. две точки фиксированы на оси X, а третья может плавать вверх по оси Y.
Центр тяжести нашей конфигурации, если не ошибаюсь, всегда будет в точке (0,y/3).

А где искомая точка с минимумом расстояний? Вы не поверите - всегда в точке
(0,y) если y<0.577
(0,0.577) если y>=0.577
По крайней мере такой результат выдает моя программа )
Это просто мистика какая-то. Буду благодарен тому, кто найдет в ней ошибку
procedure TForm1.Button1Click(Sender: TObject); var y3, y, r, e, y0, r0, ymin, rmin: extended; begin y3:=StrToFloatDef(Edit1.Text,3); y0:=y3 / 3; r0:=(y3-y0)+ 2 * sqrt(1+y0*y0); ymin:=y0; rmin:=r0; e:=1 / 1000; y:=y3; while y>=0 do begin; r:=(y3-y)+ 2 * sqrt(1+y*y); if rmin>r then begin; rmin:=r; ymin:=y; end; y:=y-e; end; Memo1.Lines.Add(Format("центр тяжести %g %g",[y0,r0])); Memo1.Lines.Add(Format("мин расстояний %g %g",[ymin,rmin])); end;

Понемногу доходить стало, магическое число - это sqrt(3)/3 ))

> Sha © (16.04.07 01:50) [14]

А что тут мистического? Ты интуитивно приписываешь искомой точке свойства, которыми обладает центр тяжести, и интуитивно помещаешь эту точку в центр, но это не так. Например, если оставить только две точки A(-1, 0) и B(1, 0), то любая точка внутри этого отрезка имеет сумму расстояний 2.

Соответственно, если поместить третью точку C в точку B, то минимальной сумма расстояний будет для точки O = C = B, а центр масс делит отрезок AB в отношении 1:3, что показывает ошибку в рассуждениях Pavia [11].

Кстати, этот пример служит хорошей иллюстрацией того, почему в большинстве приложений минимизируется именно сумма квадратов (дисперсия), а не сумма расстояний :)

← →
485АТА (2007-04-16 15:13) [18]

Не сочтите за флуд, но скажите имеите ли Вы отношение к КЭМТ им. Н.Островского.

Не совсем пятничная задачка, но очень интересно как решать Найти похожие ветки