Алгоритм сопоставления чисел с минимальным количеством ходов

11

Это своего рода вопрос о расстоянии редактирования, и он очень прост. У меня просто мозги на эту тему, и до сих пор не могу понять.


Учитывая ряд чисел, например

[3, 1, 1, 1]

Как наиболее эффективно превратить все числа в одно и то же число с минимальным количеством «ходов»? Под «перемещением» подразумевается добавление или удаление одного из числа.

В приведенном выше примере наиболее эффективными являются следующие шаги:

[1, 1, 1, 1]

Это потребует 2 хода, уменьшая первый номер в два раза.

Я не могу найти лучший способ выяснить это, учитывая гораздо большие массивы из сотен чисел.

Первоначально я пытался вычислить округленное среднее число (сумма всех, деленных на длину), а затем уменьшить их до вычисленного среднего, но в приведенном выше примере это сломалось, потребовав 4 хода вместо 2.

Я полагаю, я мог понять:

  1. Среднее,
  2. Режим,
  3. Медиана

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

dthree
источник
Если домен ограничен, вы можете попробовать все возможности от мин до макс. В противном случае вы можете попытаться использовать режим или медиану.
Бартош Прзыбыльски
Спасибо @Bartek. Похоже , пробуя все возможности были бы чрезвычайно неэффективны , если дело с сотнями или тысячами номеров. Я проверю режим / медиану. Но являются ли они уверены , для получения результатов в каждом конкретном случае? Это мой главный вопрос. Я ищу определенный, эффективный алгоритм.
dthree
Есть ли число быть в наборе чисел, или оно может быть любым целым числом?
TCSGrad
@TCSGrad Это может быть любое целое число, но, очевидно, вы захотите выбрать одно, которое находится между минимальным и максимальным числом. В этом случае либо 1, 2, либо 3.
3

Ответы:

10

Ответ - взять медиану. Одним из свойств медианы является то, что она минимизирует расстояние L1 до каждого элемента. (Чтобы понять смысл статьи в Википедии, возьмите распределение вероятностей за равномерное распределение по вашей исходной серии чисел).

Это алгоритм, который решает проблему (изначально написанный dc2 ):

function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2
mhum
источник
Да, это было сделано. Забавно, как это работает. Не похоже, что медиана сделает это, но эй. Большое спасибо.
dthree
1
Смотрите мой ответ для доказательства.
Юваль Фильмус
@ dc2: вы не можете «убедиться», «попробовав».
Рафаэль
1
Просто чтобы отметить: вы можете рассчитать среднее время O (n)
Бартош Przybylski
1
@ Рафаэль Можно ли включать код OP в какой-то другой ответ, без ссылки на OP?
thefourtheye
10

Как упоминает TCSGrad, учитывая список целых чисел , вы ищете целое число минимизирующее Полезно вычислить : Когда переходит от к , количество переходит от к . Более того, он переключает значения только в точкахx1,,xnm

δ(m)=i=1n|mxi|.
δ(m+1)δ(m)
δ(m+1)δ(m)=i=1n{+1mxi1m<xi=#{i:mxi}#{i:m<xi}.
m+δ(m+1)δ(m)nnx1,,xn, Нетрудно проверить, что оптимальным значением является минимальная точка, в которой . Эта минимальная точка является одной из , поэтому расстояние редактирования равно .mδ(m+1)δ(m)0ximin(δ(x1),,δ(xn))

Предположим далее, что все различны и что нечетно. Пусть будет медианой . Тогда то время как , и поэтому является единственным оптимумом. Если четно, то аналогичный расчет показывает, что мы можем выбрать любую точку в интервале, соединяющую медианы. Подобные, но более сложные рассуждения показывают, что любая медиана является оптимальной, даже если не различимы. Так что на самом деле нет необходимости вычислять для всех .xinmxiδ(m+1)δ(m)=1δ(m)δ(m1)=1mnxiδxi

Юваль Фильмус
источник
Возможно, вы пропустили это, но этот ответ (почти) доказывает, что медиана является оптимальным выбором.
Юваль Фильмус
1
Ваш ответ был превосходным, и я проголосовал за него. К сожалению для меня, это слишком хорошо, потому что я не очень хорошо разбираюсь в научной нотации, оставляя большую часть этого материала в искаженном виде. Это моя проблема, а не ваша.
dthree
5

Проблема может быть сформулирована как проблема LP:

Учитывая набор из чисел , решите следующий LP:n[a1,a2...an]

min|aix|

(Удалены ограничения на , которые не были необходимы, как указал Рафаэль)x

Как только LP будет решен, вы получите значение соответствующее решению. Если является целым числом, все готово, иначе округлите его до ближайшего целого числа.xx

РЕДАКТИРОВАТЬ : Как указано в комментариях, целевая функция должна быть сумма по абсолютной разности. Чтобы преобразовать его обратно в стандартный LP, мы можем переписать LP следующим образом:

minai

при условии:

aiaix i
aiaix i
ai,x0 i

При оптимальном решении , и мы можем получить значение из решения.ai=|aix| ix

TCSGrad
источник
Так что, если я правильно понимаю, в моем примере x будет 1 - 3, и поэтому я найду расстояние редактирования 1, 2 и 3, а затем сделаю мин на этом?
3
@ dc2: это минимизирует сумму расстояний между каждым числом и , где - сходящееся число. Ограничения гарантируют, что LP быстро завершается и не выполняет поиск по всем целым числам! хxx
TCSGrad
Почему ограничения необходимы?
Рафаэль