Предположим, что - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение , количество узлов в дереве. Цель состоит в том, чтобы минимизировать время, необходимое для вывода дерева в терминах .x a b n n
Существует ли алгоритм для вышеуказанной задачи?
Предположим, что степень любого узла в не больше 3.
Что я знаю
Случай с ограниченным диаметром прост . Если диаметр дерева равен , то мы можем получить алгоритм «разделяй и властвуй»:
Любое двоичное дерево имеет хороший разделитель, который делит дерево на компоненты размером не менее 1/3n.
- Выберите любую вершину х. Если это хороший разделитель меток то и рекурсивно.
- Найти всех 3 соседей х.
- Двигайтесь в направлении соседа, который имеет наибольшее количество узлов. Повторите шаг 2 с соседом.
Поскольку нахождение разделителя занимает не более шагов, мы получаем алгоритм .
рандомизированный алгоритм. (перенесено из комментариев ниже)
Выберите две вершины x и y случайным образом. С вероятностью 1/9 они будут лежать на противоположных сторонах разделителя. Укажите средний узел пути от до . Посмотрите, если это разделитель, если не делать бинарный поиск.
Требуется ожидаемое время нахождения разделителя. Таким образом, мы получаем рандомизированный алгоритм.
Фон. Я узнал об этой проблеме от друга, который работает в вероятностных графических моделях. Вышеупомянутая проблема примерно соответствует изучению структуры дерева соединений с использованием оракула, который, учитывая три случайные величины X, Y и Z, может сообщать значение взаимной информации между X и Y, учитывая значение Z. Если значение близко к нулю, мы можем предположить, что Z лежит на пути от X до Y.
Ответы:
Нет . Следующая простая стратегия противника подразумевает, что любой алгоритм для восстановления дерева узлов требует, по крайней мере, ( n - 1N «промежуточных» запросов.(n−12)=n(n−1)/2
Произвольно пометить узлы . Противник отвечает на все запросы, как будто дерево является звездой с вершиной 0 в центре; думайте о 0 как о корне, а другие узлы как о его дочерних элементах .0,1,2,…,n−1 0 0
Теперь предположим, что алгоритм останавливается после выполнения менее чем запросов. Тогда должно быть две вершины y и z , не равные нулю, чтобы алгоритм не запрашивал перестановку тройки ( 0 , y , z ) . Если алгоритм утверждает, что дерево не является звездой с центром 0 , злоумышленник раскрывает свои данные, доказывая, что алгоритм неверен. Затем противник обнаруживает, что x на самом деле является единственным потомком y , что снова доказывает неправильность алгоритма.n(n−1)/2 y z (0,y,z) 0 x y
Обновление: Ой, только что заметил ограничение степени.
К счастью, это не главное препятствие. Замените узел вашим любимым двоичным деревом, оставив n - 1 узлов в некотором неизвестном порядке, а затем откройте это поддерево алгоритму реконструкции. Реконструкция получающегося двоичного дерева с ( 2 n - 3 ) узлами все еще требует по крайней мере n ( n - 1 ) / 2 запросов. Эквивалентно, для реконструкции двоичного дерева с m- узлами требуется как минимум ( m + 3 )0 n−1 (2n−3) n(n−1)/2 m запросов. (Я уверен, что более тонкая конструкция улучшит константу.)(m+3)(m+2)/8 Как указывает Джагадиш, это обобщение не работает; запросы о внутренних узлах в дереве накладывают упорядочение на листья, что уменьшает количество необходимых запросов.источник
источник