Что такое хорошая целевая функция для нахождения местоположения, "ближайшего" к двум другим местам? - PullRequest
0 голосов
/ 03 июня 2018

Я пытался найти ответ, прибегая к помощи Google, но я не мог добиться реального прогресса (возможно, потому что я не знал, что именно Google).

Проблема, которую я хочу решить,что-то вроде этого: предположим, я остаюсь в месте A, а мой друг - в месте B. Мы хотим найти ресторан, который не был бы «слишком далеко» для нас обоих.Что было бы хорошей целевой функцией, которая учитывает только расстояния ресторана от A и B и отражает некоторое понятие «справедливости», чтобы при минимизации функции над множеством возможных ресторанов мы получили место, которое не несправедливо далеко (илиclose) только для одного человека.

Я рассмотрел сумму расстояний, но это дает одинаковый результат для всех точек на линии, соединяющей А и В. Интуитивно кажется, что «справедливая» функция должна даватьболее низкое значение для точек вблизи средней точки.Затем я рассмотрел сумму квадратов расстояний, но я не уверен, что это очень хорошая идея.

Другой возможностью было рассмотреть расстояние до ресторана от средней точки, но у этого есть некоторые практические проблемы.Из-за различных других причин (таких как дороги с односторонним движением, закрытые дороги вокруг средней точки и т. Д.), Мы можем получить плохое решение, если мы просто учтем расстояния от средней точки.Вот почему я хочу, чтобы целевая функция принимала только расстояния от A и B в качестве входных данных (а не от любой другой точки).

Ответы [ 2 ]

0 голосов
/ 03 июня 2018

Как и во многих вещах в жизни, беспокойство о "справедливости" приводит к неоптимальным решениям.

Я полагаю, что лучшее решение - минимизировать MAX (dist (A), dist (B))

Это будет "несправедливо", если ближайший ресторан к B намного ближе к A , но вы действительно хотите выбрать тот, которыйподальше от обеих сторон, просто чтобы убедиться, что A выплачивает свою "справедливую" долю обострения?

Если есть несколько ресторанов с одинаковым счетом, я предлагаю минимизировать MIN(dist (A), dist (B)) , чтобы разорвать связи, потому что это предпочитает меньшее общее ухудшение по сравнению с большим.Это означает, что если B нужно идти дальше, но есть два кандидата на одинаковом расстоянии от B , то B должен выбрать тот, который ближайший к A .В конце концов, A и B должны быть друзьями, верно?Вы были бы очень раздражены, если бы ваш друг хотел, чтобы вы страдали только потому, что их страдания были неизбежны.(Я уверен, что у всех нас есть бывший друг, подобный этому: -)

Обратите внимание, что сведение к минимуму суммы квадратов и сведение к минимуму оба являются примерами "p-норм"с различными показателями: https://en.wikipedia.org/wiki/Norm_(mathematics)#p-norm

Сумма квадратов - это норма L_2, которая предпочитает решения, которые лучше в среднем с худшими отдельными компонентами, а минимизация максимума - это норма L_infinity, в которой преобладает наихудшееотдельный компонент.

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

0 голосов
/ 03 июня 2018

Как насчет чего-то вроде:

 objective function = A + B + lambda * abs( A - B )

, настраивая лямбду, вы можете контролировать вес, заданный для справедливости.

...