Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Вычислительная геометрия / Разное /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Найти точку с минимальной суммой расстояний - Программирование от RIN.RU
Найти точку с минимальной суммой расстояний

Пусть координаты точек x1, ..., xN не убывают (если это не так, то просто отсортируем предварительно последовательность).

Метод решения #1.


Предположим, что мы нашли точку z, и она лежит на интервале (x[i],x[i+1]). Справа от нее i точек, слева - N-i. Сумма расстояний Smin будет такой:

Smin=(z-x[1])+ ... +(z-x[i])+(x[i+1]-z)+ ... +(x[N]-z).


Предположим, что i>N-i и мы в пределах интервала сдвигаем точку z влево на какую-то маленькую величину d (d<z-x[i]). Получаем новую сумму S

S=(z-d-x[1])+ ... +(z-d-x[i])+(x[i+1]-(z-d))+ ... +(x[N]-(z-d))=Smin-d*i+d*(N-i).


А так как, по предположению, i>N-i, то S<Smin !?


Ситуация, когда N-i>i, исследуется аналогично - мы делаем сдвиг на величину d<x[N+1] - z вправо, не выходя при этом за границы интервала, и опять же получаем, что новая сумма S<Smin. Случай, когда z совпадает с одной из точек x[i] исследуется так же, как и выше, используя маленькие сдвиги.


Следовательно, для того, чтобы точка z была искомой, необходимо и достаточно, чтобы справа и слева от нее лежало одно и то же число точек. Если N=2k, то точка z может быть любой из точек отрезка [x[k],x[k+1]], если же N=2k+1, то точка z=x[k+1].


Метод решения #2.


Пусть мы решаем задачу для N точек на прямой.


Точка z должна, очевидно, лежать на отрезке [x[1],x[N]].


Если N=1, то данная точка и является искомой.


Если N=2, то z может лежать где угодно на отрезке [x1,xN] - суммарное расстояние будет одинаковым и равным длине отрезка.


Если N>2, то суммарное расстояние от точки z до точек с минимальной и максимальной координатами (т.е. до точек x1 и xN) не зависит от местоположения точки z и равно длине отрезка [x1, xN]. Так как суммарное расстояние до этих двух точек постоянно, то поэтому мы можем их отбросить, и решать задачу уже для N-2 точек x2,...,xN-1. Проведя необходимое число раз сокращение количества точек, мы придем к уже рассмотренным случаям одной или двух точек.


Окончательно получаем: если N=2k, то точка z может быть любой из точек отрезка [xk,xk+1], если же N=2k+1, то точка z=x[k+1].



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Смотрите w2you.ru техническая поддержка сайта.