Что является хорошей целевой функцией для нахождения местоположения, "наиболее близкого" к двум другим местам?
Я пытался найти ответ, прибегая к помощи Google, но я не смог добиться реального прогресса (возможно, потому что я не знал, что именно Google).
Проблема, которую я хочу решить, выглядит примерно так: предположим, что я остаюсь в месте A, а мой друг - в месте B. Мы хотим найти ресторан, который не был бы "слишком далеко" для нас обоих. Какой была бы хорошая целевая функция, которая учитывает только расстояния ресторана от A и B и отражает некоторое понятие "справедливости", чтобы при минимизации функции над множеством возможных ресторанов мы получили место, которое не несправедливо далеко (или закрыть) только для одного человека.
Я рассмотрел сумму расстояний, но это дает один и тот же результат для всех точек на линии, соединяющей А и В. Интуитивно кажется, что "справедливая" функция должна давать более низкое значение для точек вблизи средней точки. Затем я рассмотрел сумму квадратов расстояний, но я не уверен, что это очень хорошая идея.
Другой возможностью было рассмотреть расстояние до ресторана от средней точки, но это имеет некоторые практические проблемы. Из-за различных других причин (таких как дороги с односторонним движением, закрытые дороги вокруг средней точки и т. Д.) Мы можем получить плохое решение, если мы просто рассмотрим расстояния от средней точки. По этой причине я хочу, чтобы целевая функция принимала только расстояния от A и B в качестве входных данных (а не от любой другой точки).
2 ответа
Как и во многих вещах в жизни, беспокойство о "справедливости" приводит к неоптимальным решениям.
Я полагаю, что лучшим решением является минимизация MAX( dist(A), dist(B))
Это будет "несправедливо", если ближайший к B ресторан гораздо ближе к A, но вы действительно хотите выбрать ресторан, который находится дальше от обеих сторон, просто чтобы убедиться, что A выплачивает свою "справедливую" долю обострения?
Если есть несколько ресторанов с одинаковым счетом, я предлагаю минимизировать MIN( dist(A), dist(B)), чтобы разорвать связи, потому что это предпочитает меньшее общее ухудшение по сравнению с большим. Это означает, что если B должен идти дальше, но есть два кандидата на одинаковом расстоянии от B, то B должен выбрать тот, который ближе всего к A. В конце концов, А и Б должны быть друзьями, верно? Вы были бы очень раздражены, если бы ваш друг хотел, чтобы вы страдали только потому, что их страдания были неизбежны. (Я уверен, что у всех нас есть такой бывший друг:-)
Обратите внимание, что минимизация суммы квадратов и минимизация максимума - это оба случая "p-норм" с разными показателями степени: https://en.wikipedia.org/wiki/Norm_(mathematics)
Сумма квадратов - это норма L_2, которая предпочитает решения, которые лучше в среднем с худшими отдельными компонентами, а минимизация максимума - это норма L_infinity, в которой полностью доминирует худший отдельный компонент.
Я думаю, что все p-нормы являются разумными ответами на ваш вопрос.
Как насчет чего-то вроде:
objective function = A + B + lambda * abs( A - B )
настраивая лямбду, вы можете контролировать вес, заданный для справедливости.