2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Задачка про города
Сообщение21.11.2009, 22:57 
То есть научиться решать задачу не хотите? Хорошо, ваше дело.

 
 
 
 Re: Задачка про города
Сообщение22.11.2009, 00:48 
Похоже, никто не заметил, что станция обязательно должна быть на железной дороге, с $y=0$.
Мне кажется, простейшее решение - это найти единственный минимум тернарным поиском.
Сложность - $n \log(\Delta x)$

 
 
 
 Re: Задачка про города
Сообщение22.11.2009, 10:08 
Аватара пользователя
Скажите, а какой смысл в железной дороге? Почему это множество выделено? Расстояние между его точками (станциями) можно считать нулевым, ведь они не считаются городами? А у городов нет никаких весов помимо расстояний?

 
 
 
 Re: Задачка про города
Сообщение22.11.2009, 11:22 
Аватара пользователя
venco
venco в сообщении #264287 писал(а):
Мне кажется, простейшее решение - это найти единственный минимум тернарным поиском


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

 
 
 
 Re: Задачка про города
Сообщение22.11.2009, 17:07 
ИС в сообщении #264335 писал(а):
А можно ссылку на этот тернарный поиск.
Первая ссылка на Гугле: Троичный поиск

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

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

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

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

 
 
 
 Re: Задачка про города
Сообщение24.11.2009, 18:25 
А ведь Cave прав насчет необходимости более тщательной проработки задачки...

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

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

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

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

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

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

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

 
 
 
 Re: Задачка про города
Сообщение25.11.2009, 01:17 
Это очевидно, что функционал сначала убывает, а потом возрастает?

 
 
 
 Re: Задачка про города
Сообщение25.11.2009, 06:23 
Наверно, вы имели в виду функцию.
Да, она монотонно убывает до минимума, а потом монотонно возрастает.

 
 
 
 Re: Задачка про города
Сообщение25.11.2009, 10:21 
Почему?

 
 
 
 Re: Задачка про города
Сообщение27.11.2009, 00:33 
2Cave
Цитата:
venco в сообщении #265155 писал(а):
Да, она монотонно убывает до минимума, а потом монотонно возрастает.

Почему?

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

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

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

 
 
 
 Re: Задачка про города
Сообщение27.11.2009, 06:02 
Circiter в сообщении #265630 писал(а):
2venco
Цитата:
А чем вам поиск минимума делением не понравился?

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

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


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

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

 
 
 
 Re: Задачка про города
Сообщение28.11.2009, 00:54 
2Cave
Цитата:
Это не доказательство.

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

 
 
 [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group