DP Динамическое программирование Приём
Динамика на деревьях
Также: Tree DP · DP on trees · перерасчёт с корня · rerooting · задача о корпоративе · maximum weight independent set on a tree · вершинное покрытие дерева
Ответ для поддерева собирается из ответов для поддеревьев детей, и один проход от листьев к корню считает всё дерево за O(n). Второй проход, от корня к листьям, даёт ответ для каждой вершины как для корня. На дереве адресов этого сайта два прохода находят его центр и две самые далёкие страницы — одну и ту же страницу на двух языках.
Этот сайт — дерево. У каждой страницы есть раздел: родитель адреса /utilities/math/exams/ent/equations — /utilities/math/exams/ent, у того — /utilities/math/exams, и так до главной. В карте сайта 8966 страниц, а вместе с двадцатью разделами, у которых нет своей страницы, — 8986 узлов. Какие две страницы дальше всего друг от друга, если ходить только по хлебным крошкам? Из какой ближе всего до всех остальных? Ответить на оба вопроса для всех страниц сразу можно за два прохода по дереву — от листьев к корню и обратно.
Самые далёкие страницы — в 11 кликах друг от друга, и это одна и та же страница на двух языках: разбор уравнений из тренажёра ЕНТ, русская и английская версия. Английский сайт лежит в разделе /en, поэтому английская страница на уровень глубже, и путь между ними идёт через главную. Центр сайта — сама главная: от неё до любой страницы в среднем 3,409 клика. Следом, с отставанием в две тысячных, — /en: английская половина почти так же велика, как русская.
Идея
Подвесим дерево за корень. Задача о поддереве вершины v распадается на те же задачи о поддеревьях её детей, и поддеревья детей не пересекаются и не связаны ничем, кроме самой v. Поэтому для каждой вершины храним немного чисел о её поддереве — размер, глубину, лучший ответ «с v» и «без v», — и считаем их по числам детей. Порядок — дети раньше родителя, то есть от листьев к корню; каждая вершина считается один раз, и всё дерево — за O(n).
Это динамика на деревьях. В обычной динамике порядок заполнения таблицы приходится придумывать, а здесь он дан самим деревом: это обратный порядок обхода в ширину или выход из вершины при обходе в глубину. Самая простая такая динамика — размер раздела: размер вершины — единица плюс размеры детей. Так считает du размер каталога на диске.
Глубже — диаметр, самый длинный путь в дереве. У любого пути есть самая высокая вершина, где он поворачивает вниз, и из неё он спускается по двум разным детям. Значит, для каждой вершины достаточно знать глубины двух самых глубоких веток через разных детей: длинейший путь, поворачивающий в v, — их сумма, а диаметр — наибольшая такая сумма по всем вершинам. На дереве сайта она равна 11 и достигается на главной: шесть уровней вниз по английской ветке и пять по русской.
Корпоратив без начальников
Классическая учебная задача. Компания устраивает праздник, у каждого сотрудника есть оценка «насколько он весёлый», и никто не хочет веселиться при своём прямом начальнике. Кого позвать, чтобы веселья было больше всего? На языке графов это наибольшее по весу независимое множество в дереве: никакие две выбранные вершины не соединены ребром.
Одного числа на вершину мало: родителю важно, позван ли сам ребёнок. Поэтому чисел два. take[v] — лучшее веселье отдела v, если v позвали: его подчинённых звать нельзя, и от каждого ребёнка берётся его skip. skip[v] — если не позвали: тогда каждый ребёнок свободен, и от него берётся лучшее из двух.
$$take[v] = fun[v] + \sum_{c} skip[c], \qquad skip[v] = \sum_{c} \max\bigl(take[c],\; skip[c]\bigr).$$take[v] и skip[v] — наибольшее веселье допустимого набора в поддереве v, в который v соответственно входит и не входит.
Индукция от листьев. Допустимый набор в поддереве v — это решение «звать ли v» плюс допустимые наборы в поддеревьях детей, и единственное ограничение между ними — ребро от v к ребёнку: если v позвали, ребёнок не позван. Поддеревья разных детей между собой рёбрами не связаны, поэтому их наборы выбираются независимо, и лучшее для суммы — лучшее для каждого слагаемого. Если v позвали, у ребёнка c лучший набор без c — это skip[c]; если нет — лучший из двух.
Числа под каждым человеком в сцене — эта самая таблица. Попробуйте жадное правило «самых весёлых первыми»: директор весёлый — 7, — и его зовут первым, после чего три начальника отделов по 6, 5 и 5 остаются дома, и праздник набирает 13. Таблица у директора видит оба варианта: с ним 13, без него 16. В доказательстве всё держалось на том, что поддеревья детей независимы, — на графе с циклами этого нет, и задача о наибольшем независимом множестве становится NP-трудной.
Код
Праздник: таблица, восстановление списка гостей сверху вниз, жадное правило и проверка перебором на трёхстах случайных деревьях.
Гости восстанавливаются вторым проходом, сверху вниз: директор решает, идти ли ему, сравнив take и skip, и каждый следующий знает, позвали ли его начальника. Если позвали — он остаётся дома, если нет — решает сам так же.
Дерево сайта: размеры разделов, две самые глубокие ветки, диаметр и сумма расстояний от каждой страницы до всех остальных.
Перерасчёт с корня
Проход от листьев считает ответ для корня. А если нужен ответ для каждой вершины, как будто корнем подвесили её? Например, сумма расстояний от страницы до всех остальных — чтобы найти центр сайта. Можно сделать n обходов, по одному из каждой вершины, но это n² шагов: на дереве сайта восемьдесят миллионов. Вместо этого заметим, как меняется ответ при переходе корня по одному ребру.
Пусть total[v] — сумма расстояний от v до всех вершин, и c — ребёнок v, в поддереве которого size[c] вершин. Если перейти из v в c, все вершины поддерева c станут на шаг ближе, а все остальные, n − size[c], — на шаг дальше:
$$total[c] = total[v] - size[c] + \bigl(n - size[c]\bigr).$$Отсюда два прохода. Снизу вверх считаем размеры поддеревьев и total для корня — сумму глубин. Сверху вниз переносим корень по рёбрам формулой выше. Оба прохода — O(n). Именно эти две волны показывает режим «центр» в сцене: сначала проход от листьев, потом — от корня, и вершины окрашиваются по найденной сумме.
Не каждый ответ переносится так просто. Если нужна не сумма, а расстояние до самой далёкой вершины, то при переходе из v в c самая глубокая ветка v может как раз идти через c — и тогда ею пользоваться нельзя. Поэтому у каждой вершины держат две лучшие ветки через разных детей — тот же приём, что для диаметра. Это вторая задача ниже.
Сколько это стоит
Каждая вершина обрабатывается один раз за проход, и на ребро тратится константа: O(n) времени и O(n) памяти на числа вершин. Если чисел на вершину больше — например, в «рюкзаке на дереве» на вершину приходится целая строка таблицы, — время растёт вместе с ними, но порядок обхода тот же.
Наклон обхода из каждой вершины — 2, перерасчёта — 1. На двух тысячах вершин Python тратит на обходы почти 0,4 секунды, а перерасчёт с корня проходит миллион вершин быстрее, чем обходы — две тысячи.
Рекурсия и глубокие деревья. Динамику на дереве естественно писать рекурсивным обходом в глубину, и на коротких деревьях это работает. Но дерево может быть цепочкой из сотен тысяч вершин, а Python по умолчанию разрешает около тысячи вложенных вызовов; поднятый предел упирается в размер стека, и программа падает. Листинги этой статьи рекурсии не используют: они строят порядок обхода в ширину, где родитель всегда раньше детей, и идут по нему вперёд или назад. В Go стек горутины растёт сам, но и там список вершин нагляднее и не зависит от глубины дерева.
Когда дерево — не дерево
Всё держится на одном свойстве: поддеревья детей связаны с остальным деревом только через родителя. Добавьте одно лишнее ребро — между отделом продаж и складом, — и take склада начинает зависеть от того, позвали ли начальника продаж. Таблица по поддеревьям этого не видит.
Иногда спасает небольшое расширение состояния. Если лишних рёбер мало, можно перебрать, что происходит с их концами, и для каждого варианта решить задачу на дереве. Если граф «похож на дерево» — его можно разрезать на маленькие куски-мешки, сложенные в дерево, — динамика идёт по этому дереву разбиения, а в состоянии хранится, что выбрано в текущем мешке: это уже динамика по маскам, и время растёт экспоненциально только от размера мешка. Наибольшее независимое множество на таких графах ищут именно так.
Вторая ловушка — порядок детей. Если ответ зависит от того, в каком порядке обходить детей вершины, — например, когда детей нужно выстроить в ряд с наименьшей ценой, — каждой вершине приходится решать свою маленькую задачу о порядке, и время перестаёт быть линейным. В задачах этой статьи порядок детей не важен: суммы и максимумы от него не зависят.
Где работает
Файлы и каталоги. Размер каталога — сумма размеров вложенных: du считает её проходом снизу вверх. Тот же проход отвечает, сколько файлов в разделе и насколько глубока самая длинная вложенность.
Компиляторы. Сколько регистров процессора нужно, чтобы вычислить выражение без сохранения промежуточных значений в память? Рави Сети и Джеффри Ульман в 1970 году разметили дерево выражения снизу вверх: число для узла получается из чисел двух его поддеревьев, а потом по разметке строится код, где сначала вычисляется более «тяжёлое» поддерево.
Биология. Если эволюционное дерево видов известно, а у листьев — нынешних видов — известны буквы генов, то наименьшее число мутаций, которое объясняет эти буквы, считается проходом от листьев к корню. Уолтер Фитч описал такой подсчёт в 1971 году; в основе — тот же вопрос, что в задаче о празднике: что нужно знать о поддереве, чтобы решить за родителя.
Олимпиады. Наибольшее независимое множество, вершинное покрытие, доминирующее множество, диаметр, центр, рюкзак на дереве. На графах общего вида первые три NP-трудны, а на деревьях решаются за линейное время — динамикой по поддеревьям.
Задачи
Первая — наименьшее число охранников, которые видят все проходы выставки: вершинное покрытие дерева, два числа на зал и обход без рекурсии на анфиладе из двухсот тысяч залов. Вторая — для каждой страницы сайта число кликов до самой далёкой: перерасчёт с корня, где одной лучшей ветки мало.
Охрана выставки Самая далёкая страницаДанные: Адреса страниц из карты сайта legost.in