|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 26 May 2001 20:32:59
To : Alexei Frounze
Subject : Weighted mediam
--------------------------------------------------------------------------------
26 May 01 19:23, you wrote to me:
SS>> Дано N точек на плоскости с координатами Pi(Xi, Yi) и весом
SS>> Wi каждая. Hайти сабж для этих точек - такую точку P(X,Y) на
SS>> плоскости, что для нее
SS>> N
SS>> Sum [ Wi*D(Pi, P) ] i=1
SS>> будет минимальным. D - расстояние между точками, вычисляется
SS>> по формуле D(Pi, P) = abs(Xi-X) + abs(Yi-Y)
AF> кажись эта задача называется "где построить школу" :)
очень на то похоже ;)
AF> есть три деревни, в каждой соотв. кол-во детей/потенциальных
AF> учеников.
AF> не математическое простое решение:
AF> приклеиваешь карту района с этими деревнями к столу, сверлишь дырки в
AF> точках этих деревень, берёшь три нитки, связанные с одной стороны
AF> (типа жиденького пучка), просовываешь три свободных конца сквозь дырки
AF> в столе, к тому что под столом привязываешь грузики с массой
AF> пропорциональной кол-ву учеников в соответствующей деревне. вылазишь
AF> из-под стола, смотришь где находится узелок пучка на карте - там
AF> строить школу.
А математического решения у тебя нет ? Точнее алгоритмического - с O(N)
сложностью ?
AF> только вот расстояние у тебя почему-то сумма модулей, а не по
AF> Пифагору. ошибка?
Hет, не ошибка. Эта формула расстояния называется метрика Манхеттена и
эквивалентна Эвклидовой. В очень многих задачах можно заменить Эвклидову
метрику на метрику Манхеттена без влияния на результат.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
