4

Есть дерево, в котором каждая вершина имеет свой вес, нужно разбить дерево на три компоненты связности, в каждой из которых суммарный вес всех вершин одинаков.

Подскажите, какой алгоритм стоит использовать?

Пока вижу такое решение - перебор всех пар ребер, с последующей проверкой - но это тяжелое решение по производительности.

9
  • Эта задача у Вас возникла всё по той же теме: оценка размера PNG (ru.stackoverflow.com/questions/649761/…) ? 11 апр 2017 в 9:09
  • Что делать, если решения не существует? Правильно ли я понимаю, что нужно удалить какие-то 2 ребра? В таком случае в дереве окажется 3 компоненты связности. Каков размер дерева? 11 апр 2017 в 9:09
  • @hedgehogues, нет, задачи не связаны друг с другом, в случае отсутствия решения просто сообщить об этом (ведь на самом деле его может и не быть) набор данных ограничен только тем, что граф это любое дерево (для простоты полагается что как минимум два ребра есть) 11 апр 2017 в 12:05
  • В таких задачах правильное решение и выбор алгоритма критически зависит от того, могут ли веса вершин быть отрицательными. В том числе и в этой задаче. Могут или нет? 12 апр 2017 в 16:59
  • 1
    Просто если все веса строго положительны, то разбиение (если оно существует) будет однозначным. А если есть нулевые веса, то могут появляться компоненты нулевого веса, которые можно будет гонять туда-сюда. Т.е. появляется неоднозначность в решении. Однозначная задача более "осязаема". 12 апр 2017 в 20:16

2 ответа 2

4

Задачка, кажущаяся на первой взгляд, переборной со сложностью сложность лобового алгоритма (N -- число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже.

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

Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности.

Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу скажем, что разбиение на компоненты связности -- это удаление некоторых рёбер. Приведу пример разбиения на компоненты связности следующего графа:

Исходный граф

Получим 2 компоненты связности:

2 компоненты связности -- 1

Получим 3 компоненты связности:

3 компоненты связности -- 1

Другой пример. Получим 2 компоненты связности (вершина 1 -- это заменена на вершину 15):

2 компоненты связности -- 2

Получим 3 компоненты связности:

3 компоненты связности -- 2

Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности.

Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас разбиение или нет. Напишем псевдокод:

# Перебираем все рёбра
for i in range edge:
    for j in range edge:
       # Если разбиение делит наше дерево на равные по весу части, то заканчиваем выполнение
       if Splitting(i, j):
           break

Очевидно, что сложность такого алгоритма будет полиномиальной

O(N^2 * g(N)),

где g(n) -- время работы Splitting.

Но что делаь с функцией Splitting(i, j)? Очевидно, что Splitting(i, j) может отработать за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды. В таком случае, ассимптотическое время работы будет сложность O(N), хотя, по факту, это будет 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. Введём функцию:

Функция

Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.

9
  • ваше решение как раз то о чем я написал обычный метод грубой силы (правда немного не возьму в толк откуда у вас 2^N сложность выскочила, на первый взгляд не могу представить такой сложный алгоритм) 11 апр 2017 в 12:09
  • @LmTinyToon В чём моё решение грубой силой? Оно работает за куб. Разве это очень плохо? Я могу ускорить его до квадрата. 2^N -- это в том случае, если осуществлять перебор по всем маскам рёбер. Т.е. 111111 -- все рёбра есть. 1011111 -- нет ребра #2. Проверяем, подходит ли данное решение или нет. И т.д. Перебрав все маски, получим ответ. 11 апр 2017 в 12:16
  • За сколько Вы хотите решить эту задачу? Думаю, что быстрее чем за O(NlogN) не получится. Возможно, выйдет за O(N) с предподсчётом в виде O(N) или O(N^2) 11 апр 2017 в 12:17
  • ну грубая сила (в моем понимании) потому, что выполняете полный перебор вариантов. Конечно решение за N^3 тоже подойдет, просто знаете, иногда хочется найти очень красивое решение - может существует уже какой-то известный результат подобной проблемы 11 апр 2017 в 12:24
  • @LmTinyToon, Вы тогда оговаривайте, что есть грубая сила в Вашем понимании. Хорошо, допишу решение за O(N^2). Вероятно, я могу его сделать. В таком случае, предлагайте своё решение, а не пишите вопрос, как сделали это Вы: у меня есть задача, хочу алгоритм. 11 апр 2017 в 12:28
2

Ясно, что для выполнения разбиения надо удалить ровно два ребра. Ясно также, что каждая компонента будет деревом. Также заранее ясно, чему будет равен суммарный вес вершин в каждом из трех поддеревьев. Пусть это будет Starget.

Обозначим любую вершину дерева корнем и далее рассматриваем корневое дерево.

  • Будем строить наши связные компоненты путем наращивания (и объединения) множества поддеревьев снизу-вверх, от листьев к корню. Начинаем с набора стартовых поддеревьев, каждое из которых состоит из одной листовой вершины дерева.

  • Если на каком-то этапе построения мы обнаруживаем поддерево T с суммой Starget, то существует решение, включающее поддерево T (если у задачи вообще есть решение). Все остальные варианты разбиения могут лишь "наращивать" T дополнительными вершинами, суммарный вес которых равен нулю. Будем назвать поддерево с суммой Starget завершенным.

  • Рассмотрим незавершенное поддерево T, корневая вершина которого являются сыном вершины P. Ясно, что P должно входить в одну и ту же связную компоненту, что и T.

  • Из последнего утверждения сразу следует, что если у нас есть несколько незавершенных поддеревьев, корневые вершины которых являются сыновьями одного и того же предка P, то все они должны входить в одну и ту же связную компоненту, включающую также и P.

Отсюда автоматически следует, что решение задачи достаточно тривиально:

  1. Начинаем с набора стартовых поддеревьев T, каждое из которых состоит из одной листовой вершины дерева.
  2. Циклически обрабатываем текущий набор поддеревьев T, пока у нас не останется ровно одно поддерево:
  3.     Если суммарный вес какого-то поддерева строго равен Starget (завершенное поддерево), то считаем его частью результата и исключаем из дальнейшего рассмотрения (исключаем из T и условно исключаем из исходного дерева).
  4.     Если в процессе такого исключения какая-то вершина исходного дерева становится листовой, то добавляем ее в T как отдельное поддерево.
  5.     Если у нас в T присутствуют все незавершенные поддеревья, чьи корни являются сыновьями некоей вершины P, то объединяем их в одно поддерево с корнем P.
  6. По завершению работы цикла 2-5 мы получим набор связных компонент, полученных на шаге 3, а также единственное оставшееся поддерево в T.
  7.     Если на шаге 3 получено ровно 2 завершенных поддерева, а вес оставшегося поддерева в T тоже равен Starget - то это наше решение.
  8.     Если на шаге 3 получено ровно 3 завершенных поддерева, а вес оставшегося поддерева в T равен нулю - то объединяем оставшееся поддерево с любым из завершенных и получаем решение.
  9.     В противном случае задача решения не имеет.
2
  • У меня примерно такие мысли и были - решение задачи за линейный проход 12 апр 2017 в 19:28
  • Только идея у меня такая была - сгруппировать узлы дерева по глубине, затем процессить с самых глубоких до корня. На каждом шаге для каждого узла заданной глубины идти к родительскому + накапливать суммарный вес. При каждой обработки либо мержить, либо находить компоненты связности 12 апр 2017 в 19:29

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.