Задачка про города

[Cave]

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

[venco]

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

[geomath]

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

[ИС]

venco

venco в сообщении #264287 писал(а):

Мне кажется, простейшее решение - это найти единственный минимум тернарным поиском

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

[venco]

ИС в сообщении #264335 писал(а):

А можно ссылку на этот тернарный поиск.

Первая ссылка на Гугле: Троичный поиск

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

geomath в сообщении #264320 писал(а):

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

Условие такое в первом посте темы.

[geomath]

venco в сообщении #264418 писал(а):

geomath в сообщении #264320 писал(а):

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

Условие такое в первом посте темы.

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

[Circiter]

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

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

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

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

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

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

[venco]

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

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

[Cave]

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

[venco]

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

[Cave]

Почему?

[Circiter]

2Cave

Цитата:

venco в сообщении #265155 писал(а):

Да, она монотонно убывает до минимума, а потом монотонно возрастает.

Почему?

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

2venco

Цитата:

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

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

[venco]

Circiter в сообщении #265630 писал(а):

2venco

Цитата:

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

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

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

[Cave]

Circiter в сообщении #265630 писал(а):

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

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

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

[Circiter]

2Cave

Цитата:

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

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