6.4 Минимизация сумм

Рассмотрим задачу: дано \(n\) чисел \(a_1, a_2, \dots, a_n\), и нужно выбрать такое значение \(x\), чтобы минимизировать сумму

\[|a_1 - x|^c + |a_2 - x|^c + \dots + |a_n - x|^c.\]

Мы разберём два наиболее важных случая: \(c = 1\) и \(c = 2\).

Случай \(c = 1\)

В этом случае нужно минимизировать сумму

\[|a_1 - x| + |a_2 - x| + \dots + |a_n - x|.\]

Пример

Пусть числа равны \([2, 4, 10, 4, 7]\).

Если выбрать \(x = 4\), получим:

\[|2 - 4| + |4 - 4| + |10 - 4| + |4 - 4| + |7 - 4| = 2 + 0 + 6 + 0 + 3 = 11.\]

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

В нашем примере после сортировки получаем:

\[[2,\ 4,\ 4,\ 7,\ 10].\]

Значит, медиана равна \(4\), и именно она даёт минимальную сумму.

Почему именно медиана?

Интуитивно:

• если \(x\) меньше медианы, то слишком много чисел лежат справа, и сдвиг \(x\) вправо уменьшает суммарное расстояние;
• если \(x\) больше медианы, то слишком много чисел лежат слева, и сдвиг \(x\) влево тоже улучшает ответ.

Поэтому минимум достигается в точке медианы.

Важное замечание

Если \(n\) чётно, то после сортировки есть две «середины». В таком случае оптимальными будут:

• обе медианы;
• и вообще любое значение между ними.

---

Случай \(c = 2\)

Теперь нужно минимизировать сумму

\[(a_1 - x)^2 + (a_2 - x)^2 + \dots + (a_n - x)^2.\]

Примеры

Возьмём числа \([2, 4, 10, 4, 8]\).

Среднее арифметическое равно

\[\frac{2 + 4 + 10 + 4 + 8}{5} = \frac{28}{5} = 5.6.\]

Именно значение \(x = 5.6\) минимизирует сумму квадратов расстояний.

Если считать по формуле, получаем:

\[(2 - 5.6)^2 + (4 - 5.6)^2 + (10 - 5.6)^2 + (4 - 5.6)^2 + (8 - 5.6)^2\]

\[= 12.96 + 2.56 + 19.36 + 2.56 + 5.76 = 43.2.\]

Почему здесь работает среднее?

Раскроем скобки:

\[(a_1 - x)^2 + (a_2 - x)^2 + \dots + (a_n - x)^2\]

\[= nx^2 - 2x(a_1 + a_2 + \dots + a_n) + (a_1^2 + a_2^2 + \dots + a_n^2).\]

Последняя часть не зависит от \(x\), значит, её можно считать константой. Тогда остаётся квадратичная функция вида:

\[nx^2 - 2sx,\]

где

\[s = a_1 + a_2 + \dots + a_n.\]

Это парабола с ветвями вверх, а её минимум достигается в вершине:

\[x = \frac{s}{n}.\]

Но \(\frac{s}{n}\) — это и есть среднее арифметическое всех чисел.

---

Итого

Для задачи минимизации суммы расстояний оптимальный выбор зависит от степени:

• при \(c = 1\) нужно брать медиану;
• при \(c = 2\) нужно брать среднее арифметическое.

Это важный приём, который часто встречается в жадных алгоритмах, математической оптимизации и задачах анализа данных.