Модель дерева решений

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

Операции ветвления называются «тестами» или «запросами». В этой настройке рассматриваемый алгоритм можно рассматривать как вычисление логической функции $f:\; \{0,\; 1\}\; n\; \to \; \{0,\; 1\}\; \{\backslash \; displaystyle\; f:\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; rightarrow\; \backslash \; \{0,1\; \backslash \}\}$где входными данными является серия запросов, а выходными данными - окончательное решение. Каждый запрос может зависеть от предыдущих запросов.

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

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

• 1 Классификация по вычислительной сложности запроса
  • 1.1 Простое дерево решений
  • 1.2 Линейное дерево решений
  • 1.3 Алгебраическое дерево решений
• 2 Классификация по вычислительной модели запроса
  • 2.1 Детерминированное дерево решений
  • 2.2 Рандомизированное дерево решений
  • 2.3 Недетерминированное дерево решений
  • 2.4 Квантовое дерево решений
• 3 Взаимосвязь между различными моделями
• 4 См. Также
• 5 Ссылки
  • 5.1 Обзоры

Простое дерево решений

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

Простейшей иллюстрацией этого метода нижней границы является задача поиска наименьшего числа среди $n\; \{\backslash \; displaystyle\; n\; \}$числа, использующие только сравнения. В этом случае модель дерева решений - это двоичное дерево. Алгоритмы для этой проблемы поиска могут привести к $n\; \{\backslash \; displaystyle\; n\}$различным результатам (поскольку любой из $n\; \{\backslash \; displaystyle\; n\}$заданных чисел может оказаться быть самым маленьким). Известно, что глубина двоичного дерева с $n\; \{\backslash \; displaystyle\; n\}$листьями не менее $log\; \; n\; \{\backslash \; displaystyle\; \backslash \; log\; n\}$, что дает нижнюю границу $\Omega \; (log\; \; n)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (\backslash \; log\; n)\}$для задачи поиска.

Однако известно, что эта нижняя граница является слабой, поскольку следующий простой аргумент показывает, что требуется как минимум $n\; -\; 1\; \{\backslash \; displaystyle\; n-1\}$сравнений: Перед может быть определено наименьшее число, каждое число, кроме наименьшего, должно «проиграть» (сравнить большее) хотя бы в одном сравнении.

В тех же строках нижняя граница $\Omega \; (n\; log\; \; n)\; \{\; \backslash \; displaystyle\; \backslash \; Omega\; (n\; \backslash \; log\; n)\}$для сортировки может быть подтверждено. В этом случае существование множества алгоритмов сравнения-сортировки, имеющих такую ​​временную сложность, таких как mergesort и heapsort, демонстрирует, что граница жесткая.

Линейное дерево решений

Линейные деревья решений, как и простые деревья решений, принимают решение о ветвлении на основе набора значений в качестве входных. В отличие от двоичных деревьев решений, линейные деревья решений имеют три выходных ветви. Линейная функция, которая представляет собой любую функцию вида $a\; 0\; +\; \sum \; i\; =\; 1\; naixi\; \{\backslash \; displaystyle\; a\_\; \{0\}\; +\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; a\_\; \{i\}\; x\_\; \{i\}\; \}$для некоторых действительных чисел $a\; 0,\dots ,\; an\; \{\backslash \; displaystyle\; a\_\; \{0\},\; \backslash \; dots,\; a\_\; \{n\}\}$проверяется, и принимаются решения о ветвлении в зависимости от знака функции (отрицательный, положительный или 0).

Геометрически $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$определяет гиперплоскость в R . Набор входных значений, достигающих любого конкретного узла, представляет собой пересечение полуплоскостей, определенных узлами.

Алгебраическое дерево решений

Алгебраическое дерево решений - это обобщение линейных деревьев решений, которые позволяют тестовым функциям быть полиномами степени $d\; \{\backslash \; displaystyle\; d\}$. Геометрически пространство разделено на полуалгебраические множества (обобщение гиперплоскости). Оценить сложность обычно труднее.

Детерминированное дерево решений

Если результат дерева решений равен $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$, для всех $x\; \in \; \{0,\; 1\}\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}$дерево решений называется "вычислить" $f\; \{\backslash \; displaystyle\; f\}$. Глубина дерева - это максимальное количество запросов, которое может произойти до того, как будет достигнут лист и получен результат. $D\; (f)\; \{\backslash \; displaystyle\; D\; (f)\}$, детерминированное дерево решений сложность $f\; \{\backslash \; displaystyle\; f\}$равна наименьшая глубина среди всех детерминированных деревьев решений, которые вычисляют $f\; \{\backslash \; displaystyle\; f\}$.

рандомизированное дерево решений

Один из способов определить рандомизированное дерево решений - добавить дополнительные узлы к дереву, каждая из которых контролируется вероятностью $pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\}$. Другое эквивалентное определение - определить его как распределение по детерминированным деревьям решений. На основе этого второго определения сложность рандомизированного дерева определяется как наибольшая глубина среди всех деревьев, поддерживающих базовое распределение. $R\; 2\; (f)\; \{\backslash \; displaystyle\; R\_\; \{2\}\; (f)\}$определяется как сложность рандомизированного дерева решений с наименьшей глубиной, результатом которого является $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$с вероятностью не менее $2/3\; \{\backslash \; displaystyle\; 2/3\}$для всех $x\; \in \; \{0,\; 1\}\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}$(т. е. с ограниченной двусторонней ошибкой).

$R\; 2\; (f)\; \{\backslash \; displaystyle\; R\_\; \{2\}\; (f)\}$известна как Монте-Карло рандомизированная сложность дерева решений, потому что результат может быть неверным с ограниченными двусторонняя ошибка. Лас-Вегас сложность дерева решений $R\; 0\; (f)\; \{\backslash \; displaystyle\; R\_\; \{0\}\; (f)\}$измеряет ожидаемую глубину дерева решений, которое должно быть правильным. (т. е. имеет нулевую ошибку). Существует также версия с односторонней ограниченной ошибкой, которая обозначается $R\; 1\; (f)\; \{\backslash \; displaystyle\; R\_\; \{1\}\; (f)\}$.

Недетерминированное дерево решений

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

Квантовое дерево решений

Сложность квантового дерева решений $Q\; 2\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{2\}\; (f)\}$- это глубина дерево квантовых решений с наименьшей глубиной, которое дает результат $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$с вероятностью не менее $2/3\; \{\backslash \; displaystyle\; 2/3\}$для всех $x\; \in \; \{0,\; 1\}\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}$. Другая величина, $QE\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{E\}\; (f)\}$, определяется как глубина дерева квантовых решений с наименьшей глубиной, которая дает результат $f\; (\; x)\; \{\backslash \; displaystyle\; f\; (x)\}$с вероятностью 1 во всех случаях (т.е. точно вычисляет $f\; \{\backslash \; displaystyle\; f\}$). $Q\; 2\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{2\}\; (f)\}$и $QE\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{E\}\; (f)\}$более широко известны как сложности квантовых запросов, потому что прямое определение дерева квантовых решений сложнее, чем в классическом случае. Подобно случайному случаю, мы определяем $Q\; 0\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{0\}\; (f)\}$и $Q\; 1\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{1\}\; (\; f)\}$.

Из определений сразу следует, что для всех $n\; \{\backslash \; displaystyle\; n\}$-битных булевых функций $f\; \{\backslash \; displaystyle\; f\}$, $Q\; 2\; (f)\; \le \; R\; 2\; (f)\; \le \; R\; 1\; (f)\; \le \; R\; 0\; (f)\; \le \; D\; (f)\; \le \; n\; \{\backslash \; displaystyle\; Q\_\; \{2\}\; (f)\; \backslash \; leq\; R\_\; \{\; 2\}\; (f)\; \backslash \; leq\; R\_\; \{1\}\; (f)\; \backslash \; leq\; R\_\; \{0\}\; (f)\; \backslash \; leq\; D\; (f)\; \backslash \; leq\; n\}$и $Q\; 2\; (f)\; \le \; QE\; (f)\; \le \; D\; (f)\; \le \; n\; \{\backslash \; displaystyle\; Q\_\; \{2\}\; (f)\; \backslash \; leq\; Q\_\; \{E\}\; (f)\; \backslash \; leq\; D\; (f)\; \backslash \; leq\; n\}$.

Блюм и Импальяццо, Хартманис и Хемачандра, и Тардос независимо обнаружил, что $D\; (f)\; \le \; R\; 0\; (f)\; 2\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; R\_\; \{0\}\; (f)\; ^\; \{2\}\}$. Ноам Нисан найдено что сложность рандомизированного дерева решений Монте-Карло также полиномиально связана со сложностью детерминированного дерева решений: $D\; (f)\; =\; O\; (R\; 2\; (f)\; 3)\; \{\backslash \; displaystyle\; D\; (f)\; =\; O\; (R\_\; \{2\}\; (\; е)\; ^\; \{3\})\}$. (Нисан также показал, что $D\; (f)\; =\; O\; (R\; 1\; (f)\; 2)\; \{\backslash \; displaystyle\; D\; (f)\; =\; O\; (R\_\; \{1\}\; (f)\; ^\; \{2\})\}$.) Между моделями Монте-Карло и Лас-Вегас известна более тесная взаимосвязь: $R\; 0\; (f)\; =\; O\; (R\; 2\; (f)\; 2\; log\; \; R\; 2\; (f))\; \{\backslash \; displaystyle\; R\_\; \{0\}\; (\; е)\; =\; O\; (R\_\; \{2\}\; (f)\; ^\; \{2\}\; \backslash \; log\; R\_\; \{2\}\; (f))\}$. Это отношение оптимально с точностью до полилогарифмических факторов.

Сложность квантового дерева решений $Q\; 2\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{2\}\; (f)\}$также полиномиально связана с $D\; (f)\; \{\backslash \; displaystyle\; D\; (f)\}$. Мидриджанис показал, что $D\; (f)\; =\; O\; (QE\; (f)\; 3)\; \{\backslash \; displaystyle\; D\; (f)\; =\; O\; (Q\_\; \{E\}\; (f)\; ^\; \{3\})\}$, улучшая граница квартики из-за Beals et al. Beals et al. также показал, что $D\; (f)\; =\; O\; (Q\; 2\; (f)\; 6)\; \{\backslash \; displaystyle\; D\; (f)\; =\; O\; (Q\_\; \{2\}\; (f)\; ^\; \{6\})\}$, и это по-прежнему самая известная граница. Однако самый большой известный разрыв между детерминированной и квантовой сложностями запросов только квадратичный. Квадратичный разрыв достигается для функции ИЛИ ; $D\; (ИЛИ\; n)\; =\; n\; \{\backslash \; displaystyle\; D\; (OR\_\; \{n\})\; =\; n\}$, а $Q\; 2\; (OR\; n)\; =\; \Theta \; (n)\; \{\backslash \; displaystyle\; Q\_\; \{2\; \}\; (OR\_\; \{n\})\; =\; \backslash \; Theta\; (\{\backslash \; sqrt\; \{n\}\})\}$.

Важно отметить, что эти полиномиальные отношения действительны только для полных булевых функций. Для частичных логических функций, у которых есть домен подмножества $\{0,\; 1\}\; n\; \{\backslash \; displaystyle\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}$, экспоненциальное разделение между $QE\; (f)\; \{\backslash \; displaystyle\; Q\_\; \{E\}\; (f)\}$и $D\; (f)\; \{\backslash \; displaystyle\; D\; (f)\}$равно возможный; Первый пример такой проблемы был обнаружен Дойч и Йозса.

Эти отношения можно резюмировать следующими неравенствами, которые верны с точностью до постоянных факторов:

• $D\; (f)\; \le \; R\; 0\; (f)\; 2\; \{\backslash \; Displaystyle\; D\; (е)\; \backslash \; leq\; R\_\; \{0\}\; (f)\; ^\; \{2\}\}$
• $D\; (f)\; \le \; R\; 1\; (f)\; R\; 2\; (f)\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; R\_\; \{1\}\; (е)\; R\_\; \{2\}\; (f)\}$
• $D\; (f)\; \le \; R\; 2\; (f)\; 3\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; R\_\; \{2\}\; (f)\; ^\; \{3\}\}$
• $R\; 0\; (е)\; \le \; R\; 2\; (f)\; 2\; журнал\; \; R\; 2\; (f)\; \{\backslash \; displaystyle\; R\_\; \{0\}\; (f)\; \backslash \; leq\; R\_\; \{2\}\; (f)\; ^\; \{2\}\; \backslash \; log\; R\_\; \{2\}\; (f)\}$
• $D\; (f)\; \le \; Q\; 2\; (f)\; 6\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; Q\_\; \{2\}\; (f)\; ^\; \{6\}\}$
• $D\; (f)\; \le \; QE\; (f)\; 2\; Q\; 2\; (е)\; 2\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; Q\_\; \{E\}\; (f)\; ^\; \{2\}\; Q\_\; \{2\}\; (f)\; ^\; \{2\}\}$
• $D\; (f)\; \le \; Q\; 1\; (е)\; 2\; Q\; 2\; (е)\; 2\; \{\backslash \; Displaystyle\; D\; (f)\; \backslash \; leq\; Q\_\; \{1\}\; (f)\; ^\; \{2\}\; Q\_\; \{2\}\; (f)\; ^\; \{2\}\}$
• $R\; 0\; (f)\; \le \; Q\; 1\; (е)\; Q\; 2\; (е)\; 2\; журнал\; \; N\; \{\backslash \; displaystyle\; R\_\; \{0\}\; (f)\; \backslash \; leq\; Q\_\; \{1\}\; (f)\; Q\_\; \{2\}\; (f)\; ^\; \{2\}\; \backslash \; log\; N\}$
• $D\; (f)\; \le \; Q\; 1\; (f)\; Q\; 2\; (f)\; 2\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; Q\_\; \{1\}\; (f)\; Q\_\; \{2\}\; (f)\; ^\; \{2\}\}$

• Минимальное связующее дерево # Деревья решений

Опросы

• Бурман, Гарри; де Вольф, Рональд (2002), «Меры сложности и сложность дерева решений: обзор» (PDF), Теоретическая информатика, 288 (1): 21–43, doi : 10.1016 / S0304-3975 (01) 00144-X