Блог

Рассмотрим полное троичное дерево глубины h, состоящее из корня, присоединенного к трем полным троичным деревьям глубины h — 1. Существует n = 3 ^ h листьев, и с каждым листом связано логическое значение. Каждый внутренний узел, включая корневой, равен значению большинства его дочерних элементов.

Вот пример дерева глубины 2:

Учитывая входной вектор листьев [0, 0, 1, 0, 1, 0, 1, 1, 1], мы хотели бы найти корень дерева. Чтобы найти корень, мы могли бы оценить все листья и внутренние узлы (т. Е. 3 ^ h операций). Но мы можем оценить меньшее количество узлов. В приведенном выше примере мы можем видеть, что значение первого внутреннего узла (самого левого) может быть оценено после изучения его первых двух дочерних элементов. Аналогично, при глубине = 1 первых двух узлов достаточно, чтобы найти корень дерева.

Я думал над этой проблемой, но не могу найти хорошего способа решения проблемы.

 import numpy as np
import random

class node:
def __init__(self):
    self.low = None
    self.mid = None
    self.high = None

def put(self, low, mid, high):
    self.low = low
    self.mid = mid
    self.high = high
    return self

class ternary_tree:

def __init__(self, leaves, count= 0):
    self.leaves = leaves
    self.root = node()
    self.value = None
    self.count = count

def get_root(self):
    self.root.put(self.leaves[0], self.leaves[1], self.leaves[2])
    self.value = majority(self.root)
    return self.value

def majority(node):
    global ops_count
    r1, r2, r3 = random.sample([node.low, node.mid, node.high], 3)
    if r1 > 0:
        ops_count  = 1
        if r2 > 0:
            ops_count  = 1
            return 1;
        elif r3 > 0:
            ops_count  = 1
            return 1;
        else:
            return 0;
    else:
        ops_count  = 1
        if r2 == 0:
            ops_count  = 1
            return 0;
        elif r3 == 0:
            ops_count  = 1
            return 0;
        else:
            return 1;

if __name__ == "__main__":
    h = 2 # depth of the tree
    my_leaves = [random.randint(0,1) for i in range(0, 3**h)] #input vector
    ops_count = 0 #Counting the number of steps
    nb_trees = len(my_leaves) // 3
    my_trees = [ternary_tree(leaves=my_leaves[i:i 3]) for i in range(0, nb_trees)]
    new_leaves = []
    t1, t2, t3 = random.sample(my_trees, 3)
    new_leaves.append(t1.get_root())
    new_leaves.append(t2.get_root())
    if new_leaves[0] == new_leaves[1]:
        new_leaves.append(new_leaves[0])
    else:
        new_leaves.append(t3.get_root())
    ternary_tree(leaves=new_leaves).get_root()
  

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

Я был бы признателен, если бы вы могли дать мне какие-либо указания о том, как решить эту проблему. Спасибо!

Иллюстрация взята отсюда: http://www.math.ucsd.edu /~gptesler/188/MajTree/majtree.html .

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

Вот как majority может выглядеть функция, когда ей предоставляется только список конечных значений:

 import random

def majority(leaves):
    counter = 0

    def recur(start, size):
        nonlocal counter
        if size == 1:
            counter  = 1  # about to access a leaf's value
            return leaves[start]
        size //= 3
        # Randomly choose which child we will leave as "plan B" in case
        #  two others give opposite values
        last = random.randint(0, 2)
        # Get the values of the two other children, using recursion
        val1 = recur(start   ((last 1)%3)*size, size)
        val2 = recur(start   ((last 2)%3)*size, size)
        # If equal, we do not need to retrieve the remaining child's value
        if val1 == val2:
            return val1
        # Too bad,... we need the value of the third child to break the tie
        return recur(start   last*size, size)
    
    rootval = recur(0, len(leaves))
    return rootval, counter
  

Вы бы назвали это так:

 h = 2
leaves = [random.randint(0,1) for i in range(0, 3**h)]

rootval, counter = majority(leaves)

print("The leaves are {}".format(leaves))
print("Accessed {} leaves to find that root's value is {}".format(counter, rootval))