Это своего рода вопрос о расстоянии редактирования, и он очень прост. У меня просто мозги на эту тему, и до сих пор не могу понять.
Учитывая ряд чисел, например
[3, 1, 1, 1]
Как наиболее эффективно превратить все числа в одно и то же число с минимальным количеством «ходов»? Под «перемещением» подразумевается добавление или удаление одного из числа.
В приведенном выше примере наиболее эффективными являются следующие шаги:
[1, 1, 1, 1]
Это потребует 2 хода, уменьшая первый номер в два раза.
Я не могу найти лучший способ выяснить это, учитывая гораздо большие массивы из сотен чисел.
Первоначально я пытался вычислить округленное среднее число (сумма всех, деленных на длину), а затем уменьшить их до вычисленного среднего, но в приведенном выше примере это сломалось, потребовав 4 хода вместо 2.
Я полагаю, я мог понять:
- Среднее,
- Режим,
- Медиана
и получите расстояние редактирования каждого из них, выбрав минимальное расстояние. Однако я не уверен, что это будет правильно в каждом отдельном случае. Как я могу знать?
источник
Ответы:
Ответ - взять медиану. Одним из свойств медианы является то, что она минимизирует расстояние L1 до каждого элемента. (Чтобы понять смысл статьи в Википедии, возьмите распределение вероятностей за равномерное распределение по вашей исходной серии чисел).
Это алгоритм, который решает проблему (изначально написанный dc2 ):
источник
Как упоминает TCSGrad, учитывая список целых чисел , вы ищете целое число минимизирующее Полезно вычислить : Когда переходит от к , количество переходит от к . Более того, он переключает значения только в точкахx1,…,xn m
Предположим далее, что все различны и что нечетно. Пусть будет медианой . Тогда то время как , и поэтому является единственным оптимумом. Если четно, то аналогичный расчет показывает, что мы можем выбрать любую точку в интервале, соединяющую медианы. Подобные, но более сложные рассуждения показывают, что любая медиана является оптимальной, даже если не различимы. Так что на самом деле нет необходимости вычислять для всех .xi n m xi δ(m+1)−δ(m)=1 δ(m)−δ(m−1)=−1 m n xi δ xi
источник
Проблема может быть сформулирована как проблема LP:
Учитывая набор из чисел , решите следующий LP:n [a1,a2...an]
(Удалены ограничения на , которые не были необходимы, как указал Рафаэль)x
Как только LP будет решен, вы получите значение соответствующее решению. Если является целым числом, все готово, иначе округлите его до ближайшего целого числа.x x
РЕДАКТИРОВАТЬ : Как указано в комментариях, целевая функция должна быть сумма по абсолютной разности. Чтобы преобразовать его обратно в стандартный LP, мы можем переписать LP следующим образом:
при условии:
При оптимальном решении , и мы можем получить значение из решения.a′i=|ai−x| ∀i x
источник