0 / 0 / 1
Регистрация: 31.01.2015
Сообщений: 62
1

Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна

27.12.2015, 10:39. Показов 8546. Ответов 32
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Даны точки(неограниченно) с координатами.
Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна
Как решить подскажите?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.12.2015, 10:39
Ответы с готовыми решениями:

Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна
осталась последняя задача по Си, от неё зависит зачёт. Условия такие: найти такую точку заданного...

Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна
Всем привет! Нужна ваша помощь! Искал задачку нашел только на С++ и С# а вот на java не могу найти,...

Найти такую точку заданного множества точек на плоскости, сумма расстояний от которой до остальных минимальна
Найти такую точку заданного множества точек на плоскости, сумма расстояний от которой до остальных...

Найти точку из множества, сумма расстояний от которой до остальных его точек минимальна или максимальна
. Дано множество A из N точек. Найти такую точку из данного множества, сумма расстояний от которой...

32
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
27.12.2015, 14:25 2
Считать плотность точек на Единцу площади -даст локальный макс. На самом плотном участке перебор кандидатов?
1
763 / 664 / 194
Регистрация: 24.11.2015
Сообщений: 2,158
30.12.2015, 12:46 3
Цитата Сообщение от Excalibur921 Посмотреть сообщение
На самом плотном участке перебор кандидатов?
Искомая точка может оказаться на участке с минимальной плотностью. Представим себе правильный 128-угольник (2n), вписанный в круг радиуса 1, плюс центр круга. Для этого множества точек сумма расстояний от любой вершины многоугольника до остальных точек заведомо больше 128, а сумма расстояний от центра многоугольника до его вершин в точности равна 128. Между тем центр расположен в самой "неплотной" части множества. Так что эта идея не годится
1
373 / 343 / 42
Регистрация: 14.07.2015
Сообщений: 2,890
30.12.2015, 13:02 4
Otclik, можно начать с того, что количество точек явно не бесконечно, а значит можно посчитать все взаимные расстояния и их суммы, ну и найти минимальную.
1
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
30.12.2015, 14:19 5
Цитата Сообщение от bobah16 Посмотреть сообщение
можно посчитать все
Кажется автор намекает “не хочу брутто форс”.
Цитата Сообщение от AGK Посмотреть сообщение
Искомая точка может оказаться на участке с минимальной плотностью.
Не может, вы неправильно представили задачу. Точки от плохого псевдослучайного генератора разбросаны на плоскости. Очевидно нужно найти плотный участок и там только перебор локальный.
Цитата Сообщение от Otclik Посмотреть сообщение
сумма расстояний от которой до остальных минимальна
Значит найти участок с макс количеством точек на единицу площади.
Где-то слышал kdtree, вот тут может пригодиться.
Расстояние до пути

Добавлено через 6 минут
Цитата Сообщение от AGK Посмотреть сообщение
Представим себе правильный 128-угольник
Физик, математик и инженер стоят в поле. Каждому выдали одинаковое число досок для забора и сказали огородить максимально возможное число овец.
Инженер построил небольшой, но крепкий загончик в форме квадрата.
Физик построил загон в форме окружности, утверждая что такая форма может вместить больше овец.
Математик построил заборчик по кругу, сам сел в центре, заявляя:
— Принимаем, что я нахожусь снаружи.
2
373 / 343 / 42
Регистрация: 14.07.2015
Сообщений: 2,890
30.12.2015, 14:31 6
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Кажется автор намекает “не хочу брутто форс”.
Если плотность точек на плоскости постоянная, тогда придется все точки перебрать все равно. А как иначе?
Аналитическое решение тут получить нереально, да и будет ли оно единственным, это вопрос. Возможно есть какие-то быстрые алгоритмы поиска, но я о них не знаю. Так же можно сформулировать задачу минимизации, т.е. вариационную задачу и решить ее численно, но легче уж все точки перебрать.

Добавлено через 48 секунд
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Математик построил заборчик по кругу, сам сел в центре, заявляя:
— Принимаем, что я нахожусь снаружи.


Добавлено через 9 минут
Найти точку, у которой сумма расстояний до других точек наименьшая
1
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
30.12.2015, 15:59 7
Otclik, Вам нужно погуглить книгу Протасова "Максимумы и минимумы в геометрии"
1
Модератор
9905 / 5263 / 3318
Регистрация: 17.08.2012
Сообщений: 16,084
03.01.2016, 22:38 8
Если я всё правильно путаю, то минимальная сумма расстояний от заданных точек до искомой будет в том случае, если сумма векторов, образованных каждой заданной точкой и искомой, равна нулю. Получается, что нужно просто составить и решить СЛАУ.

Добавлено через 4 минуты
Хотя... Собстванно, зачем искать векторы, точка же нужна. Достаточно найти координаты центра тяжести заданного множества точек.
1
763 / 664 / 194
Регистрация: 24.11.2015
Сообщений: 2,158
03.01.2016, 22:57 9
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
Достаточно найти координаты центра тяжести заданного множества точек.
Увы, по условию задачи требуется
Цитата Сообщение от Otclik Посмотреть сообщение
Найти ... точку заданного на плоскости множества точек
, а не просто точку в пространстве (ну или на плоскости). В центре инерции может не существовать точки данного множества. Именно этот случай представляет интерес и затруднения

Добавлено через 3 минуты
Есть гипотеза, что искомой будет точка множества, ближайшая к центру инерции, но уже несколько дней не могу ни внятно доказать, ни построить контрпример
1
Модератор
9905 / 5263 / 3318
Регистрация: 17.08.2012
Сообщений: 16,084
03.01.2016, 23:31 10
Ох, да... Насчёт точки упустил...
1
Диссидент
Эксперт C
27707 / 17323 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
04.01.2016, 10:03 11
Цитата Сообщение от AGK Посмотреть сообщение
Есть гипотеза, что искомой будет точка множества, ближайшая к центру инерции, но уже несколько дней не могу ни внятно доказать, ни построить контрпример
Пусть все точки лежат на одной прямой. Перенумеруем их в одном направлении. 1 2 3 ..N Легко показать, что при нечетном N искомой будет точка (N+1)/2. При четном - пара равноправных точек N/2, N/2+1
Отсюда следует, что все соображения насчет плотности, центра тяжести - пустое. Вот соображения медианного характера - это может быть интересно.
3
Эксперт по математике/физике
10604 / 7043 / 3829
Регистрация: 14.01.2014
Сообщений: 16,108
04.01.2016, 13:34 12
Если просто надо найти на множестве https://www.cyberforum.ru/cgi-bin/latex.cgi?n точек одну из них, сумма расстояний от которой до остальных будет минимальной, то лучше простого переборного алгоритма быть просто не может! Затраты времени порядка https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim n^3
1
Диссидент
Эксперт C
27707 / 17323 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
04.01.2016, 13:50 13
Цитата Сообщение от mathidiot Посмотреть сообщение
лучше простого переборного алгоритма быть просто не может
Утверждение довольно смелое. Какие-то соображения можете привести в его пользу? Или только - "Мне ничего лучшего в голову не пришло"?
Я предлагаю найти "медианную" область (это будет прямоугольник или точка (не обязательно из нашего множества)), отсортировать точки по близости к этой области и начать с наиболее близких, используя метод "ветвей и границ". Для большинства точек не придется суммировать все расстояния, они будут "отваливаться" как претенденты значительно раньше.
Это, конечно, всего лишь эвристика. Но ее существование показывает, что ставить крест на задаче еще рано.
0
Эксперт по математике/физике
10604 / 7043 / 3829
Регистрация: 14.01.2014
Сообщений: 16,108
04.01.2016, 14:07 14
То, что Вы предлагаете, и есть переборный алгоритм (метод ветвей и границ), который с точки зрения программирования намного затратнее простого перебора, а порядок машинного времени останется тем же самым (https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim n^3). Ну, может быть немного получше https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim n^2ln(n)
0
Диссидент
Эксперт C
27707 / 17323 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
04.01.2016, 14:19 15
Кстати, если за расстояние взять "сумму катетов" |x1-x2| + |y1-y2| (а это тоже метрика, и довольно близкая к евклидовой), то можно применить соображения, аналогичные случаю множества точек на прямой, найти прямоугольник (для четного N) или точку (для нечетного) - "медианную область", обладающую тем свойством, что сумма расстояний от любой точки этой области до заданных точек минимальна. (в предложенной метрике). Однако, не факт, что какая-то точка множества в эту область попадет. Значит, надо взять в каком-то смысле "ближайшую".
ЗЫ. Метрика "сумма катетов" вполне имеет смысл для городов типа Санкт Петербурга или Нью-Йорка

Добавлено через 12 минут
Цитата Сообщение от mathidiot Посмотреть сообщение
с точки зрения программирования намного затратнее
Ну, о затратах на программирование вряд ли есть смысл говорить в этой теме.
Цитата Сообщение от mathidiot Посмотреть сообщение
Ну, может быть немного получше
вот уже кой-какие сдвиги по сравнению с брут-форс
0
Модератор
9905 / 5263 / 3318
Регистрация: 17.08.2012
Сообщений: 16,084
06.01.2016, 09:47 16
Попробую отсечь лишнее.

Для простоты рассуждений перенесём начало координат в центр тяжести множества точек. Пусть (xi, yi) - координаты точек в получившейся системе координат, (x0, y0) - какая-либо точка, которую есть желание принять за искомую.

Наименьшая сумма расстояний (всякая иная сумма расстояний будет больше):

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
L_{min}=\sum_{i=1}^{n}\sqrt{x_i^2+y_i^2}<br />

Если корень квадратный из функции минимален, то и сама функция минимальна. Проще говоря, почему бы и не заменить сумму расстояний суммой квадратов расстояний:

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
M_{min}=\sum_{i=1}^{n}\left( x_i^2+y_i^2\right)<br />

Теперь превознесём в наш идеал дисбаланс в виде той самой желаемой нулевой точки:

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
M=\sum_{i=1}^{n}\left( \left( x_i-x_0\right)^2+\left( y_i-y_0\right)^2\right)=M_{min}+x_0\left( \sum_{i=1}^{n}x_0-2\sum_{i=1}^{n}x_i\right)+y_0\left( \sum_{i=1}^{n}y_0-2\sum_{i=1}^{n}y_i\right)<br />

Заметим, что суммы

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\sum_{i=1}^{n}x_i<br />

и

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\sum_{i=1}^{n}y_i<br />

равны нулю, поскольку сумма векторов, образованных каждой заданной точкой и искомой, равна нулю. Окончательно получаем:

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
M=M_{min}+n\left(x_0^2+y_0^2 \right)<br />

Откуда прекрасно видно, что отличие от идеала тем меньше, чем меньше расстояние от идеала до точки дисбаланса.

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

AGK, вроде бы гипотеза доказана...

Народ, посмотрите, может, я где напутал?
1
Диссидент
Эксперт C
27707 / 17323 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.01.2016, 11:42 17
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
Народ, посмотрите, может, я где напутал?
Есть сомнения, но разбираться особо не хочется. И вот почему. В посте 11 я привел маленький (вырожденный) пример, опровергающий все соображения по поводу центра тяжести. В этом примере все точки для простоты лежат на одной прямой, что является частным случаем задачи.
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
Вывод: Сумма расстояний будет минимальной, если в качестве целевой точки избрать ближайшую к центру тяжести.
неверен, так как противоречит построенному примеру.
Возможно и наоборот, пример построен неправильно. И вообще, он построен только у меня в голове и изложен вскользь...намеком.
Хорошо. Простейший случай. Координата Y=0 для всех точек.
Координаты Х = 1,2,3,4,1000 Центр тяжести (202,0) Ближайшая точка к нему (4,0) Однако, как легко понять, самая лучшая точка (3,0)
Очень несложно показать, что на прямой именно медианная точка будет самой лучшей. Сдвиг от нее какие-то расстояния уменьшает , какие-то увеличивает на одну и ту же дельту (величину сдвига). Но увеличенных будет больше.
0
763 / 664 / 194
Регистрация: 24.11.2015
Сообщений: 2,158
06.01.2016, 11:57 18
Уважаемый Байт, Вы не опровергли гипотезу, а еще раз ее подтвердили. Если число эквидистантных точек нечетно, то точка (N+1)/2 как раз является центром инерции. Если число число эквидистантных точек четно, то точки N/2, N/2+1 как раз являются двумя ближайшими к центру инерции системы. В случаях, обладающих симметрией, а у Вас как раз такой, возможно несколько решений. Так что спасибо Вам за лишнее подтверждение
0
Диссидент
Эксперт C
27707 / 17323 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.01.2016, 12:06 19
Уважаемый AGK, посмотрите внимательно на пример из поста 17. Где центр тяжести и где лучшая точка?
Хорошо, если тот пример не впечатляет, возьмем более "эмоциональный"
1 2 3 4 5 6 1001 Центр тяжести 146. Ближайшая к нему - 6. Лучшая - 4
1
763 / 664 / 194
Регистрация: 24.11.2015
Сообщений: 2,158
06.01.2016, 12:36 20
Уважаемый Cyborg Drone, Вы попали в самую точку. Собственно, ноги гипотезы растут именно оттуда, откуда Вы показываете. Проблема в том, что, несмотря на эквивалентность метрик и порождаемых ими топологий, я пытаюсь доказать именно то, что вы считаете интуитивно очевидным, то есть
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
Проще говоря, почему бы и не заменить сумму расстояний суммой квадратов расстояний:
. Я не готов поручиться, что минимум суммы корней всегда соответствует минимуму суммы подкоренных выражений, хотя мне тоже очень этого хочется.

Добавлено через 19 минут
Цитата Сообщение от Байт Посмотреть сообщение
Ближайшая к нему - 6. Лучшая - 4
. Согласен. Впечатляет. А жаль. Пост 17 я как-то пропустил. Sorry
0
06.01.2016, 12:36
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.01.2016, 12:36
Помогаю со студенческими работами здесь

Найти такую точку множества, сумма расстояний от которой до остальных его точек максимальна
Дано линейное множество A из N точек. Найти такую точку из данного множества, сумма расстояний от...

Найти точку на плоскости, сумма расстояний от которой до остальных точек множества максимальна
Друзья, мне вновь необходима любая ваша помощь по теме) Задача такова: решить задачу, с помощью...

Найти такую точку, сумма расстояний от которой до остальных минимальна
Добрый всем день. Помогите мне решить данное задание , я плохо разбираюсь в этом языке...

Найти точку, сумма расстояний от которой до остальных точек минимальна
Имеется задачка. Дан массив точек на прямой, найти точку, сумма расстояний от которой до остальных...

Среди заданного на плоскости точек найти такую, сумма расстояний от который до остальных МАКСИМАЛЬНА
Среди заданного на плоскости точек найти такую, сумма расстояний от который до остальных...

Найти точку множества, для которой сумма расстояний к другим точкам минимальна
Дано натуральное число n множество с n точек на плоскости, что задаются парами действительных...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru