#алгоритм #графы #дерево
Есть дерево, в котором каждая вершина имеет свой вес, нужно разбить дерево на три
компоненты связности, в каждой из которых суммарный вес всех вершин одинаков.
Подскажите, какой алгоритм стоит использовать?
Пока вижу такое решение - перебор всех пар ребер, с последующей проверкой - но это
тяжелое решение по производительности.
Ответы
Ответ 1
Ясно, что для выполнения разбиения надо удалить ровно два ребра. Ясно также, что каждая компонента будет деревом. Также заранее ясно, чему будет равен суммарный вес вершин в каждом из трех поддеревьев. Пусть это будет Starget. Обозначим любую вершину дерева корнем и далее рассматриваем корневое дерево. Будем строить наши связные компоненты путем наращивания (и объединения) множества поддеревьев снизу-вверх, от листьев к корню. Начинаем с набора стартовых поддеревьев, каждое из которых состоит из одной листовой вершины дерева. Если на каком-то этапе построения мы обнаруживаем поддерево T с суммой Starget, то существует решение, включающее поддерево T (если у задачи вообще есть решение). Все остальные варианты разбиения могут лишь "наращивать" T дополнительными вершинами, суммарный вес которых равен нулю. Будем назвать поддерево с суммой Starget завершенным. Рассмотрим незавершенное поддерево T, корневая вершина которого являются сыном вершины P. Ясно, что P должно входить в одну и ту же связную компоненту, что и T. Из последнего утверждения сразу следует, что если у нас есть несколько незавершенных поддеревьев, корневые вершины которых являются сыновьями одного и того же предка P, то все они должны входить в одну и ту же связную компоненту, включающую также и P. Отсюда автоматически следует, что решение задачи достаточно тривиально: Начинаем с набора стартовых поддеревьев T, каждое из которых состоит из одной листовой вершины дерева. Циклически обрабатываем текущий набор поддеревьев T, пока у нас не останется ровно одно поддерево: Если суммарный вес какого-то поддерева строго равен Starget (завершенное поддерево), то считаем его частью результата и исключаем из дальнейшего рассмотрения (исключаем из T и условно исключаем из исходного дерева). Если в процессе такого исключения какая-то вершина исходного дерева становится листовой, то добавляем ее в T как отдельное поддерево. Если у нас в T присутствуют все незавершенные поддеревья, чьи корни являются сыновьями некоей вершины P, то объединяем их в одно поддерево с корнем P. По завершению работы цикла 2-5 мы получим набор связных компонент, полученных на шаге 3, а также единственное оставшееся поддерево в T. Если на шаге 3 получено ровно 2 завершенных поддерева, а вес оставшегося поддерева в T тоже равен Starget - то это наше решение. Если на шаге 3 получено ровно 3 завершенных поддерева, а вес оставшегося поддерева в T равен нулю - то объединяем оставшееся поддерево с любым из завершенных и получаем решение. В противном случае задача решения не имеет.Ответ 2
Задачка, кажущаяся на первой взгляд, переборной со сложностью (N -- число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже. Во-первых, кажущийся переборный алгоритм имеет место для произвольного графа (возможно есть оптимизации и можно решить быстрее). У нас же граф очень специфический. Он намного проще того, что есть в общем случае. Эта простота, например, выражается в отсутствии циклов. Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности. Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу скажем, что разбиение на компоненты связности -- это удаление некоторых рёбер. Приведу пример разбиения на компоненты связности следующего графа: Получим 2 компоненты связности: Получим 3 компоненты связности: Другой пример. Получим 2 компоненты связности (вершина 1 -- это заменена на вершину 15): Получим 3 компоненты связности: Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности. Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас разбиение или нет. Напишем псевдокод: # Перебираем все рёбра for i in range edge: for j in range edge: # Если разбиение делит наше дерево на равные по весу части, то заканчиваем выполнение if Splitting(i, j): break Очевидно, что сложность такого алгоритма будет полиномиальной , где g(n) -- время работы Splitting. Но что делаь с функцией Splitting(i, j)? Очевидно, что Splitting(i, j) может отработать за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды. В таком случае, ассимптотическое время работы будет , хотя, по факту, это будет 2N. Внутри DFS (обход в глубину) мы будем считать веса для каждой компоненты связности. Время работы Splitting можно улучшить следующим образом. Сделаем для этого предподсчёт. Для каждого ребра будем хранить 2 параметра: суммарный вес вершин выше ребра и суммарный вес ниже ребра. Приведём пример: Т.е. для ребра, соединяющего вершины 15 (она же 1, см. выше) и 3, мы можем посчитать суммарный вес в каждом кластере. Делать это будем следующим образом. Запустим LR-обход дерева и для каждого ребра (Замечу, что рёбра можно ассоциировать с соответствующими вершинами. Например, ребро (11, 10) ассоциируем с вершиной 11, ребро (6, 2) ассоциируем с вершиной 6 и т.д. Далее будем говорить о вершинах, а не о рёбрах). Продемонстрируем пример обхода: 0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8 При обходе будем суммировать считать вес поддерева. Под весом поддерева будем разуметь сумму всех вершин. Пусть на i-ом шаге мы уже подсчитали вес поддерева с корнем в вершине v. Тогда нам необходимо перейти на уровень выше и посчитать вес поддерева более высокого уровня. Проиллюстрируем на рисунке ниже. Пусть мы находимся в вершине 11. И для поддерева этой вершины мы уже посчитали вес (на рисунке она изображена листом, но будем считать, что у неё есть поддерево). Тогда нам необходимо перейти в вершину 10 и подсчитать вес поддерева вершины 10. В порядке LR-обхода, посетим и подсчитаем вес поддерева с корнем в вершине 12, 13. Тогда вес поддерева с корнем в вершине 10, будет суммой весов поддеревьев 11, 12, 13: Имеем формулу в общем случае: Для вершины v обозначим вес дерева выше неё: ниже неё: Теперь, нам нужно вычислить аналогично, для каждой вершины вес дерева выше неё. Для этого будем считать, что выше корневой вершины ничего нет. Тогда ещё раз запустим LR-обход (модифицированный). Модификация будет состоять в том, что мы будем осуществлять все действия ещё при спуске. Очевидно, что данный алгоритм вычисления вышеуказанных характеристик отработает за время . Таким образом, для каждой вершины имеем вес дерева ниже неё и вес дерева выше неё. Теперь нам необходимо научиться быстро узнавать: лежит ли данная вершина v в поддереве другой вершины u. Введём функцию: Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.
Комментариев нет:
Отправить комментарий