Поиск всех самых длинных уникальных путей в дереве

Question

Предположим, что мы имеем дерево, состоящее из N узлов. Задача состоит в том, чтобы найти все самые длинные уникальные пути в дереве. Например, если дерево выглядит следующим образом:

Тогда есть три длинные уникальные пути в дереве: 1 - 2 - 3 - 4 - 5, 6 - 2 - 3 - 4 - 5 и 1 - 2 - 6.

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

• Возможно ли вычислить эту информацию меньше чем O (N^2)? Я не мог придумать решение, которое было бы быстрее, чем O (N^2).
• Если да, не могли бы вы быть добрыми, чтобы вести меня к решению.

Причина, почему я хочу попробовать его, потому что я пытаюсь решить эту проблему: KNODES

Answer 1

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

Так что если я правильно понял, то если узел имеет только одно ребро, то допустимый путь запускается или останавливается на этом узле. Если дерево подключено, вы можете перейти от любого узла к любому узлу одним допустимым путем.

Итак, вы выбираете все узлы с одним ребром, назовите его S. Затем выберите один из S и проведите все дерево, сохраняя пути до концов (путь, а не порядок ходьбы). Затем вы делаете это с каждым другим элементом на S и удаляете дублированные пути (они могут быть в обратном порядке: например, начиная с 1: 1 - 2 - 6 и начиная с 6: 6 - 2 - 1).

Так что здесь вы должны посетить все узлы в дереве столько раз, сколько у вас есть листья в дереве. Таким образом, сложность зависит от фактора ветвления (в худшем случае это O (n^2). Существуют некоторые оптимизации, которые могут уменьшить количество операций, например, вам не нужно ходить по дереву с последнего из S.

Answer 2

В этой картине самые длинные пути являются {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 3, 7}, {1, 2, 3, 8}, {1, 2, 3, 9}, {1, 2, 3, 10}

Для такого дерева сохранение всех длинных путей будет стоить вам O (N)

Answer 3

Предположим, у вас есть Двоичное дерево, как на картинке.

class Node(object): 
    def __init__(self, key): 
    self.key = key 
    self.right = None 
    self.left = None 
    self.parent = None 

    def append_left(self, node): 
    self.left = node 
    node.parent = self 

    def append_right(self, node): 
    self.right = node 
    node.parent = self 

root = Node(3) 
root.append_left(Node(2)) 
root.append_right(Node(4)) 
root.left.append_left(Node(1)) 
root.left.append_right(Node(6)) 
root.right.append_right(Node(5)) 

И мы должны получить все пути между всеми листьями.Так что в вашем дереве они:

• 1, 2, 6
• 6, 2, 3, 4, 5
• 1, 2, 3, 4, 5

Вы можете сделайте это в (править: не линейное, квадратичное) время.

def leaf_paths(node, paths = [], stacks = {}, visited = set()): 
    visited.add(node) 

    if node.left is None and node.right is None: 
    for leaf, path in stacks.iteritems(): 
     path.append(node) 
     paths.append(path[:]) 
    stacks[node] = [node] 
    else: 
    for leaf, path in stacks.iteritems(): 
     if len(path) > 1 and path[-2] == node: 
     path.pop() 
     else: 
     path.append(node) 

    if node.left and node.left not in visited: 
    leaf_paths(node.left, paths, stacks, visited) 
    elif node.right and node.right not in visited: 
    leaf_paths(node.right, paths, stacks, visited) 
    elif node.parent: 
    leaf_paths(node.parent, paths, stacks, visited) 

    return paths 

for path in leaf_paths(root): 
    print [n.key for n in path] 

Выход для дерева будет:

[1, 2, 6]

[6, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

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

Answer 4

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

Предположим, что полное двоичное дерево с n листьями (N=n log n). Решение проблемы будет содержать путь для каждого набора из 2 листов. Это означает, что в решении будет O(n^2) элементов. Таким образом, для этого случая мы можем кодировать решение как 2-элементные множества листьев.

Теперь рассмотрим почти полное двоичное дерево с листьями m, которое было создано только путем удаления произвольных листьев из полного двоичного дерева с листьями n. Сравнивая решение этого дерева с решением полного бинарного дерева, оба будут совместно использовать пустые пулы. Фактически для каждого подмножества путей решения полного бинарного дерева будет существовать хотя бы одно двоичное дерево с остатками m, как указано выше, в котором содержится каждое решение такого подмножества. (Мы намеренно игнорируем тот факт, что дерево с листьями m может иметь еще несколько путей в решении, где по крайней мере некоторые из концов пути не являются листьями полного бинарного дерева.)

Только эта часть решения для бинарное дерево с m листьями будет закодировано числом с (n^2)/2 бит. Индекс бит в этом числе представляет собой элемент в верхней правой половине матрицы с столбцами и строками n.

Для n=4 это было бы:

x012 
xx34 
xxx5 

Бит с индексом i будет установлен, если неориентированный путь row(i),column(i) содержится в растворе.

Как мы уже statet, что решение для дерева с m листьев может содержать любое подмножество раствора до полного бинарного дерева с n>=m листьями, каждый двоичное число с (n^2)/2 бит будет представлять собой решение для дерева с m листьями ,

Теперь кодирование всех возможных номеров с помощью (n^2)/2 бит с числом менее (n^2)/2 невозможно. Таким образом, мы показали, что решения, по крайней мере, требуют наличия O(n^2) места для представления. Используя N=n log n сверху, мы получаем требование к пространству не менее O(N^2).

Поэтому doens't существует алгоритм со сложностью времени меньше, чем O(N^2)

Answer 5

Давайте возьмем дерево, которое выглядит как звезда с n узлами и n-1 краями.

Тогда у вас есть C(n-1, 2) уникальные самые длинные пути.

Таким образом, нижняя граница сложности не может быть меньше O (n^2).

Answer 6

Рисовать дерево. Пусть v - вершина, p - ее родитель. Длина самого длинного пути, включая v, но не p = (высота левого поддерева v) + (высота правого поддерева v).

Максимальное значение по всему v - это самый длинный путь на графике. Вы можете рассчитать это значение в O (n):

Сначала вычислите все промежуточные высоты. Начинайте с листьев и обрабатывайте: (высота ниже v) = 1 + max (высота ниже левого ребенка, высота ниже правого ребенка)

Затем вычислите сумму (высота левого поддерева v) + (высота правого поддерева) v) для каждой вершины v и взять максимум. Это длина самого длинного пути на графике.