Задача: Где поставит свич ?
Недавно на университетской олимпиаде встретил на первый взгляд тривиальную задачу.
700 точек на плоскости - условно компы.
Нужно поставить свич от которого кабеля идут по прямых к компам.
Надо вибрать положение свича так чтоб минимизировать длинну кабелей.
Все (даже судьи) были уверены что правильный ответ ето центр мас. Ну типа
x = (x1 + x2 + x3 .... + xn) / n
y = (y1 + y2 + y3 .... + yn) / n
Ето конечно полный бред. Помойму так минимизируется сума квадратов расстояний а не сума самих расстояний.
Может у ково будут соображения, а то мне в голову ничево кроме итерационного метода с использованием симплекса (ето такой равносторонний треугольник) не лезет.
700 точек на плоскости - условно компы.
Нужно поставить свич от которого кабеля идут по прямых к компам.
Надо вибрать положение свича так чтоб минимизировать длинну кабелей.
Все (даже судьи) были уверены что правильный ответ ето центр мас. Ну типа
x = (x1 + x2 + x3 .... + xn) / n
y = (y1 + y2 + y3 .... + yn) / n
Ето конечно полный бред. Помойму так минимизируется сума квадратов расстояний а не сума самих расстояний.
Может у ково будут соображения, а то мне в голову ничево кроме итерационного метода с использованием симплекса (ето такой равносторонний треугольник) не лезет.
что-то в голову не приходит пример почему это не так
Цитата: nilbog
что-то в голову не приходит пример почему это не так
Простейшый пример.
две точки с координатами (0,0) и одна точка (9,0).
Центр мас получится в точке (3,0).
Сума расстояний 3 + 3 + 6 = 12
Правильный ответ (0,0)
Сума расстояний 0 + 0 + 9 = 9
Цитата:
Центр мас получится в точке (3,0).
Сума расстояний 3 + 3 + 6 = 12
Сума расстояний 3 + 3 + 6 = 12
разве?
Центр масс
центр масс в точке (4.5 , 0).
и Сума расстояний 4.5+ 4.5 = 9
=)
там 2 точки в примере в (0,0), всего их три.
Ну давай решим задачу для прямой. Есть массив точек (x1,x2..,xN). Надо найти такое x=x0, где сумма L(min) = |x1-x|+|x2-x|+...+|xN-x| меньше любой другой суммы расстояний при другом x.
Мы же можем рассортировать x1,..,xN в порядке возрастания, а также расположить начало оси в x1==0? Замечательно. Тогда мы можем утверждать следующее:
1. (x <= xN) & (x >= x1)
2. L(min) = (x-x1) + (x-x2) + ... (x-xK) + (x(K+1)-x) + (x(K+2)-x) + ... + (xN-x).
Это я сразу раскрыл модули. В п.2 x, естественно, расположен между xK и x(K+1). Раскрываем формулу, сводим, получаем формулу L(x), берем первую ее производную, находим экстремумы. Дальше все просто.
Мы же можем рассортировать x1,..,xN в порядке возрастания, а также расположить начало оси в x1==0? Замечательно. Тогда мы можем утверждать следующее:
1. (x <= xN) & (x >= x1)
2. L(min) = (x-x1) + (x-x2) + ... (x-xK) + (x(K+1)-x) + (x(K+2)-x) + ... + (xN-x).
Это я сразу раскрыл модули. В п.2 x, естественно, расположен между xK и x(K+1). Раскрываем формулу, сводим, получаем формулу L(x), берем первую ее производную, находим экстремумы. Дальше все просто.
не кажеться что модули поторопились раскрыть?
из каких соображений k добудете
к тому же что вам даст производная линейной функции
= k -(N-k) = 2k - N => k=N/2 ?
но кажется тут сложнее
дело в том что k не являеться константой в этой функции
k - зависит от x
вернемся к функции
L(min) = |x1-x|+|x2-x|+...+|xN-x|
L(min) = |x-x1|+|x-x2|+...+|x-xN|
рассмотрим ее во всех точках кроме x1, ... ,xN
она дифференцируема и очевидно что произв = 0 когда x находиться на среднем отрезке (произв у нас просто сумма +-1 )
значит можно сказать что inf функции будет наименьшее из чисел L(x1) , .... , L(n), и значение ф-и от числа из этой самой середины
из каких соображений k добудете
к тому же что вам даст производная линейной функции
= k -(N-k) = 2k - N => k=N/2 ?
но кажется тут сложнее
дело в том что k не являеться константой в этой функции
k - зависит от x
вернемся к функции
L(min) = |x1-x|+|x2-x|+...+|xN-x|
L(min) = |x-x1|+|x-x2|+...+|x-xN|
рассмотрим ее во всех точках кроме x1, ... ,xN
она дифференцируема и очевидно что произв = 0 когда x находиться на среднем отрезке (произв у нас просто сумма +-1 )
значит можно сказать что inf функции будет наименьшее из чисел L(x1) , .... , L(n), и значение ф-и от числа из этой самой середины
хе... действительно проморгал.
То есть точки могут быть одинаковыми.
Ну хорошо представим такую модель.
Берем первую плоскость точек - без повторений. И получаем их центр масс (кол-во точек без повторений).
Потом как бы навешиваем груз - повторяющиеся точки + центр масс первой плоскости. Получаем еще один центр масс.
Потом для тех точек которые встречаются 3 раза (одинаковые координаты) + центр масс второй плоскости и т.д.
Не непойдет, опять поторопился.
То есть точки могут быть одинаковыми.
Ну хорошо представим такую модель.
Берем первую плоскость точек - без повторений. И получаем их центр масс (кол-во точек без повторений).
Потом как бы навешиваем груз - повторяющиеся точки + центр масс первой плоскости. Получаем еще один центр масс.
Потом для тех точек которые встречаются 3 раза (одинаковые координаты) + центр масс второй плоскости и т.д.
Не непойдет, опять поторопился.
Конечно, не поторопился. Откуда такие сомнения?
Хотя, могу понять. Вам нужна формула для определения этого N. А тут все очень просто. Должна быть наименьшей разница между (xK-x1)+(xK-x2)+...+(xK-x(K-1)) и (x(K+1)-xK)+(x(K+2)-xK)+...+(xN-xK). Только в таком случае искомая точка находится между этими двумя точками (xK и x(K+1)).
Хотя, могу понять. Вам нужна формула для определения этого N. А тут все очень просто. Должна быть наименьшей разница между (xK-x1)+(xK-x2)+...+(xK-x(K-1)) и (x(K+1)-xK)+(x(K+2)-xK)+...+(xN-xK). Только в таком случае искомая точка находится между этими двумя точками (xK и x(K+1)).
Цитата: Dolonet
Конечно, не поторопился. Откуда такие сомнения?
Хотя, могу понять. Вам нужна формула для определения этого N. А тут все очень просто. Должна быть наименьшей разница между (xK-x1)+(xK-x2)+...+(xK-x(K-1)) и (x(K+1)-xK)+(x(K+2)-xK)+...+(xN-xK).
Хотя, могу понять. Вам нужна формула для определения этого N. А тут все очень просто. Должна быть наименьшей разница между (xK-x1)+(xK-x2)+...+(xK-x(K-1)) и (x(K+1)-xK)+(x(K+2)-xK)+...+(xN-xK).
Вот ето действительно круто.
Ето натолкнуло меня на такое вот решение для случая на прямой.
L(K+1) = L(K) + K * (x(k+1) - xk)
K от 1 и больше
Такую же динамику запускаем с другого конца
L(T-1) = L(T) + (N-T+1) * (xt - x(t-1))
Т от N и меньше
На каждом шаге или К++ или Т-- но так чтоб L(K)+L(T) было минимально.
Когда (К = Т-1)
Если K < T то ответ в точке К
K > T ответ в точке Т.
K = T где угодно между ними.
Только ето наверно для плоскости не пройдет :(
Цитата: Dolonet
искомая точка находится между этими двумя точками (xK и x(K+1)).
ето очень редкий случай когда все точки с етого промежутка подходят как ответ
По поводу последней Вашей фразы - я не имел в виду, что ВСЕ точки должны подойти с этого промежутка - но точка там, среди множества возможных значений. Да и целью было на данном этапе определить между какой и какой точкой находится искомая.
Сейчас мы немного запутаемся. Давайте подумаем логически и с самого начала. То есть для прямой. Точка имеет наименьшую сумму расстояний до всех прямых, которые справа от нее, а также слева от нее. Рассмотрим два случая:
1. Количество точек слева = количеству точек справа. Значит, сумма расстояний не изменится от постановки точки в пределах отрезка от xK до x(K+1).
2. Количество точек слева < количества точек справа. Значит, сумма расстояний до точек будет тем меньше, чем расстояние в сторону наибольшего количества точек вплоть до точки x(K+1).
Несложно посчитать (в уме) что точка балланса будет в таком случае находиться либо в любом месте между двумя центральными точками (по количеству, а не расположению), если их четное количество, и в точке центральной точки, если их нечетное количетство. Для прямой задача решена.
Сейчас мы немного запутаемся. Давайте подумаем логически и с самого начала. То есть для прямой. Точка имеет наименьшую сумму расстояний до всех прямых, которые справа от нее, а также слева от нее. Рассмотрим два случая:
1. Количество точек слева = количеству точек справа. Значит, сумма расстояний не изменится от постановки точки в пределах отрезка от xK до x(K+1).
2. Количество точек слева < количества точек справа. Значит, сумма расстояний до точек будет тем меньше, чем расстояние в сторону наибольшего количества точек вплоть до точки x(K+1).
Несложно посчитать (в уме) что точка балланса будет в таком случае находиться либо в любом месте между двумя центральными точками (по количеству, а не расположению), если их четное количество, и в точке центральной точки, если их нечетное количетство. Для прямой задача решена.
Цитата: Dolonet
точка балланса будет в таком случае находиться либо в любом месте между двумя центральными точками (по количеству, а не расположению), если их четное количество, и в точке центральной точки, если их нечетное количетство.
Точно. Ето я в прошлом посте серйозно лапухнулся. В трех последних строках алгоритма нужно писать вместо L(K) L(T) просто K и T. Щас исправим :)
Заметили, как просто получается? То есть для 10 точек балланс будет между 5 и 6, для 11 - в 6-й. :)
Это для прямой.
Это для прямой.
для плоскости нужно уже искать минимум по двум переменным