Восстановление дерева по запросам разделителей

18

Предположим, что T - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение , количество узлов в дереве. Цель состоит в том, чтобы минимизировать время, необходимое для вывода дерева в терминах .x a b n nTИксaбNN

Существует ли алгоритм о(N2) для вышеуказанной задачи?

Предположим, что степень любого узла в T не больше 3.


Что я знаю

Случай с ограниченным диаметром прост . Если диаметр дерева равен D , то мы можем получить алгоритм «разделяй и властвуй»:

Любое двоичное дерево имеет хороший разделитель, который делит дерево на компоненты размером не менее 1/3n.

  1. Выберите любую вершину х. Если это хороший разделитель меток то и рекурсивно.
  2. Найти всех 3 соседей х.
  3. Двигайтесь в направлении соседа, который имеет наибольшее количество узлов. Повторите шаг 2 с соседом.

Поскольку нахождение разделителя занимает не более D шагов, мы получаем алгоритм О(NDжурналN) .

О(Nжурнал2N) рандомизированный алгоритм. (перенесено из комментариев ниже)

Выберите две вершины x и y случайным образом. С вероятностью 1/9 они будут лежать на противоположных сторонах разделителя. Укажите средний узел пути от Икс до y . Посмотрите, если это разделитель, если не делать бинарный поиск.

Требуется O(nlogn) ожидаемое время нахождения разделителя. Таким образом, мы получаемO(nlog2n) рандомизированный алгоритм.


Фон. Я узнал об этой проблеме от друга, который работает в вероятностных графических моделях. Вышеупомянутая проблема примерно соответствует изучению структуры дерева соединений с использованием оракула, который, учитывая три случайные величины X, Y и Z, может сообщать значение взаимной информации между X и Y, учитывая значение Z. Если значение близко к нулю, мы можем предположить, что Z лежит на пути от X до Y.

Jagadish
источник
7
Пожалуйста, расскажите, что вы уже знаете о проблеме, чтобы мы не тратили время на повторное изобретение колеса.
Джефф
@ Jɛ ff E Я отредактировал свой вопрос.
Jagadish

Ответы:

5

Нет . Следующая простая стратегия противника подразумевает, что любой алгоритм для восстановления дерева узлов требует, по крайней мере, ( n - 1N«промежуточных» запросов.(n12)=n(n1)/2

Произвольно пометить узлы . Противник отвечает на все запросы, как будто дерево является звездой с вершиной 0 в центре; думайте о 0 как о корне, а другие узлы как о его дочерних элементах .0,1,2,,n100

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Теперь предположим, что алгоритм останавливается после выполнения менее чем запросов. Тогда должно быть две вершины y и z , не равные нулю, чтобы алгоритм не запрашивал перестановку тройки ( 0 , y , z ) . Если алгоритм утверждает, что дерево не является звездой с центром 0 , злоумышленник раскрывает свои данные, доказывая, что алгоритм неверен. Затем противник обнаруживает, что x на самом деле является единственным потомком y , что снова доказывает неправильность алгоритма.n(n1)/2yz(0,y,z)0Иксy

Обновление: Ой, только что заметил ограничение степени. К счастью, это не главное препятствие. Замените узел вашим любимым двоичным деревом, оставив n - 1 узлов в некотором неизвестном порядке, а затем откройте это поддерево алгоритму реконструкции. Реконструкция получающегося двоичного дерева с ( 2 n - 3 ) узлами все еще требует по крайней мере n ( n - 1 ) / 2 запросов. Эквивалентно, для реконструкции двоичного дерева с m- узлами требуется как минимум ( m + 3 )0n1(2n3)n(n1)/2m запросов. (Я уверен, что более тонкая конструкция улучшит константу.)(m+3)(m+2)/8 Как указывает Джагадиш, это обобщение не работает; запросы о внутренних узлах в дереве накладывают упорядочение на листья, что уменьшает количество необходимых запросов.

Jeffε
источник
Мой вопрос о деревьях постоянной степени. Этот аргумент не работает для этого случая, верно?
Джагадиш,
2
@Jagadish: (1) Я не думаю, что это доказательство нижней границы работает для рандомизированных алгоритмов. Противник все еще может построить неудачный пример, но это не противоречит гипотезе о том, что рандомизированный алгоритм работает правильно с высокой вероятностью. (2) Кстати, кажется, что вы задали вопрос, зная ответ. Зачем ты это сделал?
Tsuyoshi Ito
2
Понимаю. Спасибо за объяснение, а также спасибо за редактирование вопроса!
Tsuyoshi Ito
4
Если у вас есть рандомизированный алгоритм, то у вас есть алгоритм. Детерминизм переоценен.
Джефф
1
O(nlogn)O(nlogn)