Разделяй и властвуй алгоритм для деревьев

Question

Я пытаюсь написать алгоритм «разделяй и властвуй» для деревьев.Для шага деления мне нужен алгоритм, который разбивает данный неориентированный граф G = (V, E) с n узлами и m ребрами на поддеревья, удаляя узел .Все подграфы должны иметь свойство не содержать более n / 2 узлов (дерево должно быть разбито как можно более одинаковым).Сначала я попытался рекурсивно удалить все листья из дерева, чтобы найти последний оставшийся узел, затем я попытался найти самый длинный путь в G и удалить его средний узел.Приведенный ниже график показывает, что оба подхода не работают:

Есть ли какой-то рабочий алгоритм, который делает то, что я хочу (возвращает узел H в приведенном выше случае).

Answer 1

Один точный алгоритм таков:

Начните с листьев и создайте непересекающиеся графы (на самом деле все они - K1), на каждом шаге найдите родителя этих листьев и объедините их в новое дерево, в каждомшаг, если у узла x есть r известный дочерний элемент и степень узла j такая, что j = r+1, просто узел, который не находится в дочернем узле x, является родителем текущего узла, в этом случае мы говорим, что узелx равно nice, в противном случае есть некоторые дочерние элементы, для которых связанное корневое поддерево их не построено, в этом случае мы говорим, что узел x равен bad.

Таким образом, на каждом шаге подключайтесьnice узлов к их родителю, и очевидно, что каждый шаг занимает sum of {degree of parent nice nodes}, также на каждом шаге у вас есть хотя бы один красивый узел (потому что вы начинаете с листа), поэтому алгоритм равен O (n), и он будетсделано полностью, но для нахождения узла, который должен быть удален. Фактически на каждом шаге требуется проверить размер непересекающегося списка (списков поддеревьев), это можно сделать в O (1) при построении, также если размер списка равенравно или бибольше чем n / 2, затем выберите связанный хороший узел.(на самом деле найдите симпатичный узел в минимальном списке, который удовлетворяет этому условию).

Очевидно, что если возможно правильно разделить дерево (каждая часть имеет не более n / 2 узла), вы можете сделать этопо этому алгоритму, но если это не так (на самом деле вы не можете разделить его на две или более части размера, меньшего, чем n / 2), это даст вам хорошее приближение для него.Также, как вы можете видеть, в дереве ввода нет допущений.

примечание: я не знаю, возможно ли иметь такое дерево, чтобы его нельзя было разбить на части размером меньше n / 2 с помощьюудаление одного узла.

Answer 2

Я думаю, что вы могли бы сделать это с помощью алгоритма, подобного следующему:

Начните с корня (если дерево не имеет корня, выберите какой-либо узел).
На каждом шаге попытайтесь спуститься вдочерний узел, который имеет наибольшее поддерево (число узлов «ниже», оно является самым большим).
Если при этом количество узлов «выше» будет больше n / 2, остановитесь, в противном случае продолжите работу с этим дочерним узлом..

Этот алгоритм должен быть O (log n), если дерево разумно сбалансировано и у нас есть размеры поддеревьев, предварительно вычисленные для каждого узла.Если одно из этих условий не применяется, это будет O (n).

Answer 3

Вот метод, который я использовал и протестировал.

Начав с поиска корня вашего дерева, вы можете сделать это, создав набор со всеми узлами в нем, а затем сделав другой массив NeighboursNumber []с количеством соседей каждого узла хранится соответствующий индекс.Затем выполните итерацию по набору и удалите листья (узлы i, имеющие NeighboursNumber [i] == 1), убедитесь, что вы добавили эти узлы в другой набор RemovedSet (чтобы избежать проблем с обновлением), а затем после каждой итерации проходите через RemovedSet и уменьшайтезапись NeighboursNumber [] для всех соседей каждого элемента набора.В конце у вас будет корневой узел.(убедитесь, что вы реализовали случай, когда осталось 2 узла с 1 соседями).После нахождения корня мы приступаем к поиску размера каждого поддерева.Хитрость заключается в том, чтобы сделать это при поиске корня: прежде чем удалять листья на первой итерации, начните с создания массива SubTreeSize [], и каждый раз, удаляя узел из нашего набора, мы добавляем значение этого узла +1 к значению родителя: SubTreeSize [parent] = SubTreeSize [parent] + SubTreeSize [удаленный узел] + 1;таким образом, когда мы находим корень, у нас также есть размер каждого поддерева.Затем мы начинаем с корня и проверяем каждого соседа по размеру его поддерева + 1> node / 2, если да, тогда мы выбираем этот узел и начинаем снова.Когда все дочерние узлы имеют размер <= node / 2, прервите цикл и выведите этот узел. </p>

Этот метод занял менее секунды для дерева с 10 ^ 5 узлами.

Answer 4

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

Вы можете вычислить накопленные веса для всех поддеревьев для каждого узла.Затем выберите тот, который наиболее сбалансирован, чтобы никакое поддерево не весило больше n/2.Вероятно, это задача для некоторого динамического программирования.