DP Динамическое программирование Приём
Оптимизации Кнута и «разделяй и властвуй»
Также: Knuth optimization · divide and conquer optimization · неравенство четырёхугольника · quadrangle inequality · монотонность лучшего разреза · естественные интервалы Дженкса · Jenks natural breaks · условие Монжа
Когда в динамике лучший разрез не убывает при сдвиге границы вправо, его не нужно искать заново: «разделяй и властвуй» считает слой разбиения на k частей за O(n log n) вместо O(n²), а окно Кнута сводит динамику на отрезках к O(n²). Обе держатся на неравенстве четырёхугольника для стоимости куска.
На картограмме каждый город — точка, а цвет — класс населения. Где провести границы классов? Если поделить размах поровну, почти все 45 тысяч городов окажутся в одном классе: у большинства десятки тысяч жителей, а у крупнейших — десятки миллионов. Джордж Дженкс в 1977 году предложил «естественные интервалы»: границы, при которых сумма квадратов отклонений внутри классов наименьшая. Это динамика: для пяти классов перебор границ стоит пять миллиардов вычислений. Но лучшая граница монотонна, и та же динамика укладывается в три с половиной миллиона — браузер считает её за десятки миллисекунд.
Пять классов Дженкса объясняют 92 % разброса населения: 44 095 городов до 527 тысяч жителей, 944 — до 2,2 миллиона, 132 — до 6 миллионов, 44 — до 13 миллионов и 12 крупнейших. Квантили делят города поровну по числу, и миллионники тонут среди стотысячников; равные интервалы отдают почти всё одному классу.
Идея
Отсортируем значения x1 ≤ … ≤ xn. Класс — это отрезок подряд идущих значений, и его цена w(j, i) — сумма квадратов отклонений от среднего на значениях j + 1 … i; по префиксным суммам x и x² она считается за O(1). Лучшее разбиение первых i значений на g классов:
bestg[i] = minj < i ( bestg−1[j] + w(j, i) ).
Перебор j для всех i — n²/2 на слой. Но обозначим через opt(i) лучший последний разрез. Если граница i сдвигается вправо, последний класс не должен начинаться левее: opt(i) ≤ opt(i + 1).
Если лучший разрез монотонен, посчитаем его сначала для середины i = n/2 перебором всех j. Тогда для левой половины разрезы не правее opt(n/2), а для правой — не левее. В каждой половине снова берём середину, и окна сужаются. На каждом уровне рекурсии окна вместе покрывают все j один-два раза, уровней log n — слой стоит O(n log n).
Когда разрез монотонен
Монотонность — не общий закон. Её даёт неравенство четырёхугольника: w(a, c) + w(b, d) ≤ w(a, d) + w(b, c) при a ≤ b ≤ c ≤ d.
Пусть w удовлетворяет неравенству четырёхугольника, и opt(i) — наибольший из лучших разрезов для i. Тогда opt(i) ≤ opt(i + 1).
Пусть j′ = opt(i), j = opt(i + 1), и допустим j < j′. Неравенство при a = j, b = j′, c = i, d = i + 1 даёт w(j, i) + w(j′, i + 1) ≤ w(j, i + 1) + w(j′, i). Раз j′ лучший для i, f(j′) + w(j′, i) ≤ f(j) + w(j, i), где f = bestg−1. Сложим: f(j′) + w(j′, i + 1) ≤ f(j) + w(j, i + 1). Значит, j′ не хуже j и для i + 1, а он больше — противоречие с выбором наибольшего лучшего разреза.
Для отсортированных значений цена «сумма квадратов отклонений от среднего на отрезке» удовлетворяет неравенству четырёхугольника.
Сумма квадратов отклонений набора — это min по c суммы (x − c)², и минимум достигается в среднем. Пусть μ — среднее отрезка [a, d), ν — среднего [b, c) (если он пуст, неравенство очевидно: разрезать отрезок не дороже, чем не резать). Разобьём [a, d) на три куска: A = [a, b), B = [b, c), C = [c, d). Справа в неравенстве стоят слагаемые (x − μ)² по A, B, C и (x − ν)² по B. Если μ ≤ ν, дадим отрезку [a, c) центр μ, а [b, d) — центр ν: слева получатся те же слагаемые по A и B, а по C — (x − ν)² вместо (x − μ)². Точки C не меньше всех точек B, значит не меньше ν ≥ μ, и до ν им не дальше, чем до μ. Если ν < μ, отдадим [a, c) центр ν, а [b, d) — μ; теперь меняются слагаемые по A, а точки A не больше ν < μ. В обоих случаях левая часть с такими центрами не больше правой, а с лучшими центрами — тем более.
Окно Кнута
В динамике на отрезках разрез ищется для каждого отрезка [i, j]: так строится оптимальное дерево поиска или порядок слияния соседних кусков. Дональд Кнут в 1971 году заметил для дерева поиска, а Фрэнсис Яо в 1980-м доказала в общем виде: если цена w удовлетворяет неравенству четырёхугольника и не убывает при расширении отрезка, то лучший разрез отрезка лежит между лучшими разрезами двух отрезков на единицу короче: opt(i, j − 1) ≤ opt(i, j) ≤ opt(i + 1, j). Доказательство Яо длиннее — сначала то же неравенство переносится на саму таблицу ответов, — и мы его здесь не повторяем.
Если для каждого отрезка перебирать разрез только между opt(i, j − 1) и opt(i + 1, j), вся таблица считается за O(n²).
Для отрезков одной длины L окна стоят opt(i + 1, i + L) − opt(i, i + L − 1) + 1. При суммировании по i правый конец каждого слагаемого сокращается с левым концом следующего, и остаётся не больше n + (число отрезков длины L) ≤ 2n. Длин n, всего O(n²).
Код
Слой — функция layer: стек отрезков [lo, hi] с окнами [olo, ohi], без рекурсии. Для пяти классов на всех 45 227 городах Python считает несколько секунд. Сцена выше делает то же в браузере для любого числа классов.
Сколько это стоит
| Задача | Перебор | С монотонностью |
|---|---|---|
| Разбиение на k частей | O(kn²) | O(kn log n), «разделяй и властвуй» |
| Динамика на отрезках | O(n³) | O(n²), окно Кнута |
| Цена — минимум прямых | O(n²) | O(n), огибающая прямых |
На тысяче городов перебор на Python в двенадцать раз медленнее, на Go при четырёх тысячах — больше чем в двести раз; на всех 45 тысячах городов «разделяй и властвуй» на Go укладывается в 66 мс.
Где легко ошибиться
- Монотонность без проверки. Если цена не удовлетворяет неравенству четырёхугольника, «разделяй и властвуй» молча даёт не лучший ответ. Сумма модулей отклонений от среднего, например, его нарушает — уже на девяти числах от 0 до 19, — а сумма модулей отклонений от медианы ему подчиняется. Проверяйте на маленьких данных против перебора.
- Несортированные значения. Неравенство для суммы квадратов доказано для отсортированных значений; для произвольного порядка классы не будут отрезками.
- Окно без j < i. Разрез должен быть левее i: правую границу окна надо урезать до i − 1.
- Потеря точности. Сумма квадратов населения доходит до 10¹⁶, и разность двух близких больших чисел теряет младшие цифры. Для сравнения разрезов этого обычно хватает, но равные с точностью до округления варианты могут выбираться по-разному в разных языках.
- Рекурсия в «разделяй и властвуй» глубиной log n безопасна, а вот в окне Кнута её нет вовсе — это два вложенных цикла.
Где работает
Картограммы: естественные интервалы — классификация по умолчанию, например, в ArcGIS. Одномерная кластеризация — та же задача k-средних, но на прямой её можно решить точно. Деление последовательности на k частей поровну, когда неравномерность штрафуется квадратом. Динамика на отрезках — оптимальные деревья поиска, слияние соседних кусков, разрезание палки — с окном Кнута.
История
Дональд Кнут в 1971 году ускорил построение оптимального дерева поиска с n³ до n², заметив монотонность корней. Фрэнсис Яо в 1980 году вывела её из неравенства четырёхугольника — условия, которое носит имя Гаспара Монжа: в 1781 году он заметил его в задаче о перевозке земли. Приём «разделяй и властвуй» для разбиения на части и более сильный алгоритм SMAWK (Аггарвал, Клаве, Моран, Шор, Уилбер, 1987) используют ту же монотонность. Джордж Дженкс описал естественные интервалы для картограмм в 1977 году.
Задачи
Прочитать «Онегина» вслух за k вечеров как можно ровнее — «разделяй и властвуй». И слить соседние куски в один с наименьшей ценой — окно Кнута.
Вечера чтения Слить соседниеДанные: Населённые пункты: GeoNames, CC BY 4.0