Вычислить значение на максимальном расстоянии от множества значений

Question

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

Эффективно, учитывая набор значений S в пределах диапазона Min-Max, мне нужно вычислить новое значение V в пределах того же диапазона, чтобы сумма расстояний между V и всеми значениями в S была максимизирована.

Answer 1

Я не думаю, что в вашей проблеме есть решение с серебряной пулей, но я бы так же решил ее решить. Во-первых, вам необходимо определить функцию sumDistance(), которая принимает новое значение V вместе со всеми значениями в текущем наборе и выводит сумму расстояний между V и каждым значением в наборе.

Далее, вы можете перемещаться по области d из sumDistance(), где Min <= d <= Max и следить сумм для каждого значения V в домене. Когда вы встретите новую большую сумму, запишите ее. Значение V, которое дало вам наибольшую сумму, - это значение, которое вы сохраняете и добавляете в свой набор.

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

Answer 2

Легко показать, что возможные кандидаты для V являются либо уже имеющимся значением S, либо минимумом/максимумом. Доказательство. Пусть S_1, S_2, ..., S_n - отсортированная последовательность S, включая min и max. Если вы выберете S_i < V < S_ {i + 1}, то сумма сумм расстояний может быть достигнута либо V = S_i, либо V = S_ {i + 1}, в зависимости от количества точек слева и справа ,

Это наблюдение дает алгоритм O (n^2), который проверяет каждый потенциальный кандидат в S. Его можно улучшить до O (n) путем вычисления префиксных сумм заранее, чтобы вычислить сумму расстояний в O (1) per элемент.

В целом, поскольку каждый элемент вносит две линейные функции стоимости в область возможных значений, эта задача может быть решена в O (log n) для каждого запроса. Вам просто нужна структура данных, которая может поддерживать список сегментов линейных функций и возвращает точку с максимальной суммой. Это может решить сбалансированное двоичное дерево поиска с некоторым умным дополнением и ленивыми обновлениями. Нужно ли это или нет, конечно, зависит от количества элементов и количества запросов, которые вы ожидаете выполнить.

Answer 3

Предполагая расстояние d(a,b) = |a-b|, тогда один из min и max всегда даст максимум.

Доказательство:

Предположим, у вас есть V, что не в конечной точке. Затем у вас есть значения n1, которые ниже, и значения n2, которые выше. Общее расстояние в минимуме будет не менее (n1 - n2) * (max - V) больше, а общее расстояние в максимуме будет не менее (n2 - n1) * (V - min) больше.

Поскольку по крайней мере один из n1 - n2 и n2 - n1 должен быть неотрицательным, максимум можно найти всегда в одной из конечных точек.