2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Задачка про города
Сообщение21.11.2009, 22:57 


02/07/08
322
То есть научиться решать задачу не хотите? Хорошо, ваше дело.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение22.11.2009, 00:48 
Заслуженный участник


04/05/09
4586
Похоже, никто не заметил, что станция обязательно должна быть на железной дороге, с $y=0$.
Мне кажется, простейшее решение - это найти единственный минимум тернарным поиском.
Сложность - $n \log(\Delta x)$

 Профиль  
                  
 
 Re: Задачка про города
Сообщение22.11.2009, 10:08 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Скажите, а какой смысл в железной дороге? Почему это множество выделено? Расстояние между его точками (станциями) можно считать нулевым, ведь они не считаются городами? А у городов нет никаких весов помимо расстояний?

 Профиль  
                  
 
 Re: Задачка про города
Сообщение22.11.2009, 11:22 
Аватара пользователя


21/04/09
195
venco
venco в сообщении #264287 писал(а):
Мне кажется, простейшее решение - это найти единственный минимум тернарным поиском


А можно ссылку на этот тернарный поиск. Я первый раз слышу это словосочетание :lol:

 Профиль  
                  
 
 Re: Задачка про города
Сообщение22.11.2009, 17:07 
Заслуженный участник


04/05/09
4586
ИС в сообщении #264335 писал(а):
А можно ссылку на этот тернарный поиск.
Первая ссылка на Гугле: Троичный поиск

-- Вс ноя 22, 2009 09:08:51 --

geomath в сообщении #264320 писал(а):
Скажите, а какой смысл в железной дороге? Почему это множество выделено? Расстояние между его точками (станциями) можно считать нулевым, ведь они не считаются городами? А у городов нет никаких весов помимо расстояний?
Условие такое в первом посте темы.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение22.11.2009, 18:00 
Аватара пользователя


15/11/06
2689
Москва Первомайская
venco в сообщении #264418 писал(а):
geomath в сообщении #264320 писал(а):
Скажите, а какой смысл в железной дороге? Почему это множество выделено? Расстояние между его точками (станциями) можно считать нулевым, ведь они не считаются городами? А у городов нет никаких весов помимо расстояний?
Условие такое в первом посте темы.

Замечательный ответ. :D

 Профиль  
                  
 
 Re: Задачка про города
Сообщение24.11.2009, 18:25 
Заслуженный участник


26/07/09
1559
Алматы
А ведь Cave прав насчет необходимости более тщательной проработки задачки...

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

Предлагаю такую модельку. Разместим на железной дороге тележку и свяжем её пружинками одинаковой жесткости со всеми поселками, после чего минимизируем энергию системы. Идея в том, что абсцисса оптимально размещенной тележки после округления до ближайшего целого даст искомую координату железнодорожной станции (т.е., после оптимизации, энергию самой длинной пружины уже уменьшать будет некуда). :)

Просто нужно найти более аналитическое решение этой проблемы (чтобы не моделировать физику, а посчитать все в "один ход" по готовой формуле). Например, можно минимизировать энергию пружин с учетом привязки тележки к железной дороге смесью МНК и лагранжевых множителей. Но этот подход эквивалентен первоначальной идеи ИС'а о проецировании на ось абсцисс центра тяжести облака поселков. Это неправильное решение, так как при этом теряются ординаты поселков, а они должны учитываться, например, как некоторые веса в выражении для энергии пружин.

То есть, если поселки расположены почти на прямой, параллельной железной дороге, то достаточно найти центр тяжести и спроецировать его на железную дорогу с последующим округлением. А вот если один из поселков сильно удален от железной дороги, то искомая станция будет находится не около проекции центра тяжести всех поселков, а около проекции этого самого удаленного поселка.

Какие идеи? Что можно использовать вместо центра тяжести? Ведь по-сути решается задача минимизации отклонения длины пружины от её среднего значения (мат. ожиданя), i.e. что-то вроде минимизации "дисперсии" расстояний от искомой станции до всех поселков.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение24.11.2009, 19:08 
Заслуженный участник


04/05/09
4586
Нет, так нельзя.
Если к уже имеющемуся минимальному решению добавить сколько угодно городов внутри минимального круга, хоть все по одну сторону от станции, это ни на йоту не изменит решения. Оптимизация по любой функции учитывающей все города будет неправильной - у нас реально ограничивающими решение почти всегда будут только два дальних города - один справа и один слева. Исключение - если один из городов гораздо дальше других от ЖД, тогда станцию нужно строить напротив него.
Я конечно, утрировал про любую функцию. Можно взять что-то типа $\root k \of {\sum{(y_i^2+(x_i-x)^2)^k}}$ и устремить $k$ к бесконечности, но это не настоящая функция, да и большие степени не способствуют простоте решения.

А чем вам поиск минимума делением не понравился?

 Профиль  
                  
 
 Re: Задачка про города
Сообщение25.11.2009, 01:17 


02/07/08
322
Это очевидно, что функционал сначала убывает, а потом возрастает?

 Профиль  
                  
 
 Re: Задачка про города
Сообщение25.11.2009, 06:23 
Заслуженный участник


04/05/09
4586
Наверно, вы имели в виду функцию.
Да, она монотонно убывает до минимума, а потом монотонно возрастает.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение25.11.2009, 10:21 


02/07/08
322
Почему?

 Профиль  
                  
 
 Re: Задачка про города
Сообщение27.11.2009, 00:33 
Заслуженный участник


26/07/09
1559
Алматы
2Cave
Цитата:
venco в сообщении #265155 писал(а):
Да, она монотонно убывает до минимума, а потом монотонно возрастает.

Почему?

Тележка едет из $-\infty$ по железной дороге в одном направлении и длины (энергия) пружин при этом уменьшаются (по мере приближения тележки к поселкам), но после прохождения тележкой некоторой точки (лежащей около искомой станции) пружины вновь начинают удлиняться. Примерно так. :)

2venco
Цитата:
А чем вам поиск минимума делением не понравился?

Я, честно говоря, не совсем понял вашу идею. :)

 Профиль  
                  
 
 Re: Задачка про города
Сообщение27.11.2009, 06:02 
Заслуженный участник


04/05/09
4586
Circiter в сообщении #265630 писал(а):
2venco
Цитата:
А чем вам поиск минимума делением не понравился?

Я, честно говоря, не совсем понял вашу идею. :)
Поскольку минимум один, его можно найти троичным поиском (ссылка выше). Сходимость, как и у бинарного поиска нуля - логарифмическая. Для каждого положения станции по тупому перебираем все города и ищем максимально удалённый (сложность - $n$). Соответственно сложность всего поиска - $n \log (\Delta x)$.
Вероятно, можно найти более сложный алгоритм с лучшей скоростью, но, скорее всего, скорость уже достаточна.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение27.11.2009, 10:32 


02/07/08
322
Circiter в сообщении #265630 писал(а):
Тележка едет из $-\infty$ по железной дороге в одном направлении и длины (энергия) пружин при этом уменьшаются (по мере приближения тележки к поселкам), но после прохождения тележкой некоторой точки (лежащей около искомой станции) пружины вновь начинают удлиняться.


Это не доказательство.

А троичный поиск всегда можно свести к двоичному: рассмотреть дискретную производную от функции, найти бинарным поиском её нуль и затем сравнить два значения около этого нуля.

 Профиль  
                  
 
 Re: Задачка про города
Сообщение28.11.2009, 00:54 
Заслуженный участник


26/07/09
1559
Алматы
2Cave
Цитата:
Это не доказательство.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group