Модель дерева решений - Decision tree model

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

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

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

Например, дерево решений аргумента используется , чтобы показать , что сравнение рода из пунктов должен сравнивать. Для сортировок сравнения запрос представляет собой сравнение двух элементов с двумя результатами (при условии, что нет одинаковых элементов): либо или . Сортировки сравнения могут быть выражены в виде дерева решений в этой модели, поскольку такие алгоритмы сортировки выполняют только эти типы запросов. ${\ displaystyle n}$${\ Displaystyle п \ журнал (п)}$${\ displaystyle a, \, b}$${\ displaystyle a <b}$${\ displaystyle a> b}$

Деревья сравнения и нижние границы для сортировки

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

Например, многие алгоритмы сортировки являются сравнение сортов , что означает , что они только получить информацию о последовательности входных данных с помощью локальных сравнений: тестирование ли , или . Если предположить, что элементы, которые нужно отсортировать, различны и сопоставимы, это можно перефразировать как вопрос типа «да» или «нет»: есть ли? ${\ Displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} <x_ {j}}$${\ displaystyle x_ {i} = x_ {j}}$${\ displaystyle x_ {i}> x_ {j}}$${\ displaystyle x_ {i}> x_ {j}}$

Эти алгоритмы могут быть смоделированы как двоичные деревья решений, где запросы являются сравнениями: внутренний узел соответствует запросу, а дочерние узлы соответствуют следующему запросу, когда ответ на вопрос - да или нет. Для конечных узлов выходные данные соответствуют перестановке , описывающей, как входная последовательность была скремблирована из полностью упорядоченного списка элементов. (Обратный к этой перестановке , переупорядочивает входную последовательность.) ${\ displaystyle \ pi}$${\ displaystyle \ pi ^ {- 1}}$

Можно показать, что сортировки сравнения должны использовать сравнения с помощью простого аргумента: для того, чтобы алгоритм был правильным, он должен иметь возможность выводить все возможные перестановки элементов; в противном случае алгоритм не сможет использовать эту конкретную перестановку в качестве входных данных. Таким образом, соответствующее дерево решений должно иметь как минимум столько же листьев, сколько и перестановок: листьев. Любое двоичное дерево с как минимум листьями имеет глубину как минимум , так что это нижняя граница времени выполнения алгоритма сортировки сравнения. В этом случае существование множества алгоритмов сравнения-сортировки, имеющих такую ​​временную сложность, таких как сортировка слиянием и heapsort , демонстрирует, что граница жесткая. ${\ Displaystyle \ Омега (п \ журнал (п))}$${\ displaystyle n}$${\ displaystyle n!}$${\ displaystyle n!}$${\ Displaystyle \ журнал _ {2} (п!) = \ Омега (п \ журнал _ {2} (п))}$

В этом аргументе ничего не говорится о типе запроса, поэтому он фактически доказывает нижнюю границу для любого алгоритма сортировки, который можно смоделировать как двоичное дерево решений. По сути, это переформулировка теоретико-информационного аргумента о том, что правильный алгоритм сортировки должен узнавать хотя бы биты информации о входной последовательности. В результате это также работает и для рандомизированных деревьев решений. ${\ Displaystyle \ журнал _ {2} (п!)}$

В других нижних границах дерева решений используется то, что запрос является сравнением. Например, рассмотрим задачу использования только сравнений для поиска наименьшего числа среди чисел. Прежде чем можно будет определить наименьшее число, каждое число, кроме наименьшего, должно «проиграть» (сравнить большее) хотя бы в одном сравнении. Итак, чтобы найти минимум , нужно хотя бы сравнения. (Теоретико-информационный аргумент здесь дает только нижнюю границу .) Аналогичный аргумент работает для общих нижних оценок для вычисления статистики порядка . ${\ displaystyle n}$${\ displaystyle n-1}$${\ Displaystyle \ журнал (п)}$

Линейные и алгебраические деревья решений

Линейные деревья решений обобщают приведенные выше деревья решений сравнения на вычислительные функции, которые принимают на вход действительные векторы . Тесты в линейных деревьях решений являются линейными функциями: для конкретного выбора действительных чисел выведите знак . (Алгоритмы в этой модели могут зависеть только от знака вывода.) Деревья сравнения - это линейные деревья решений, потому что сравнение между и соответствует линейной функции . Согласно определению, линейные деревья решений могут определять только функции , слои которых могут быть построены путем объединения и пересечения полупространств. ${\ Displaystyle х \ в \ mathbb {R} ^ {п}}$${\ displaystyle a_ {0}, \ dots, a_ {n}}$${\ displaystyle a_ {0} + \ textstyle \ sum _ {i = 1} ^ {n} a_ {i} x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {i} -x_ {j}}$${\ displaystyle f}$

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

Эти модели дерева решений, определенные Рабином и Рейнгольдом, часто используются для доказательства нижних оценок в вычислительной геометрии . Например, Бен-Ор показал, что уникальность элемента (задача вычисления , где 0, если и только если существуют различные координаты, такие, что ) требует алгебраического дерева решений глубины . Впервые это было продемонстрировано Добкиным и Липтоном для линейных моделей решений. Они также показывают нижнюю оценку линейных деревьев решений для задачи о ранце, обобщенную Стилом и Яо на алгебраические деревья решений. ${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ {0,1 \}}$${\ displaystyle f (x)}$${\ displaystyle i, j}$${\ displaystyle x_ {i} = x_ {j}}$${\ Displaystyle \ Омега (п \ журнал (п))}$${\ Displaystyle п ^ {2}}$

Сложности логического дерева решений

Для булевых деревьев решений задача состоит в том, чтобы вычислить значение n-битной логической функции для входа . Запросы соответствуют чтению бита ввода , а вывод - . Каждый запрос может зависеть от предыдущих запросов. Существует много типов вычислительных моделей, использующих деревья решений, которые можно рассматривать, допуская несколько понятий сложности, называемых мерами сложности . ${\ displaystyle f: \ {0,1 \} ^ {n} \ к \ {0,1 \}}$${\ Displaystyle х \ в \ {0,1 \} ^ {п}}$${\ displaystyle x_ {i}}$${\ displaystyle f (x)}$

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

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

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

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

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

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

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

Формально сложность сертификата at - это размер наименьшего подмножества индексов, таких что для всех , если для всех , то . Сложность сертификата - это максимальная сложность сертификата . Обозначено аналогичное понятие, в котором требуется, чтобы проверяющий был прав с вероятностью 2/3 . ${\ displaystyle f}$${\ displaystyle x}$${\ Displaystyle S \ подмножество [п]}$${\ Displaystyle у \ в \ {0,1 \} ^ {п}}$${\ Displaystyle у_ {я} = х_ {я}}$${\ displaystyle i \ in S}$${\ Displaystyle f (y) = f (x)}$${\ displaystyle f}$${\ displaystyle x}$${\ Displaystyle RC (f)}$

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

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

Эти понятия обычно ограничиваются понятиями степени и приблизительной степени. Степени из , обозначенная , является наименьшая степень любого многочлена , удовлетворяющего для всех . Приблизительная степень из , обозначенная , является наименьшая степень любого полинома , удовлетворяющего всякий раз , когда и когда . ${\ displaystyle f}$${\ Displaystyle \ deg (е)}$${\ displaystyle p}$${\ Displaystyle е (х) = р (х)}$${\ Displaystyle х \ в \ {0,1 \} ^ {п}}$${\ displaystyle f}$${\ Displaystyle {\ widetilde {\ deg}} (е)}$${\ displaystyle p}$${\ Displaystyle р (х) \ в [0,1 / 3]}$${\ displaystyle f (x) = 0}$${\ Displaystyle р (х) \ в [2 / 3,1]}$${\ displaystyle f (x) = 1}$

Beals et al. установил, что и . ${\ Displaystyle Q_ {0} (е) \ geq \ deg (f) / 2}$${\ Displaystyle Q_ {2} (е) \ geq {\ widetilde {\ deg}} (е) / 2}$

Связь между мерами сложности булевых функций

Непосредственно из определений следует , что для всех битовых булевых функций , и . Поиск лучших верхних границ в обратном направлении - основная цель в области сложности запросов. ${\ displaystyle n}$${\ displaystyle f}$${\ Displaystyle Q_ {2} (е) \ Leq R_ {2} (е) \ Leq R_ {1} (е) \ Leq R_ {0} (е) \ Leq D (f) \ Leq n}$${\ Displaystyle Q_ {2} (е) \ Leq Q_ {0} (е) \ Leq D (е) \ Leq п}$

Все эти типы сложности запроса полиномиально связаны. Блюм и Импальяццо, Хартманис и Хемачандра и Тардос независимо друг от друга открыли это . Ноам Нисан обнаружил , что Монте - Карло рандомизированы сложность дерева решений также полиномиально связаны с детерминированным решением сложности дерева: . (Нисан также показал , что .) Более плотно связь известна между моделями Монте - Карло и Лас - Вегас: . Это соотношение оптимально с точностью до полилогарифмических факторов. Что касается сложностей квантового дерева решений, и эта граница жесткая. Мидриджанис показал, что , улучшая оценку четвертой степени за счет Beals et al. ${\ Displaystyle D (е) \ leq R_ {0} (е) ^ {2}}$${\ Displaystyle D (е) = О (R_ {2} (е) ^ {3})}$${\ Displaystyle D (е) = О (R_ {1} (е) ^ {2})}$${\ Displaystyle R_ {0} (е) = O (R_ {2} (f) ^ {2} \ log R_ {2} (f))}$${\ Displaystyle D (е) = О (Q_ {2} (е) ^ {4})}$${\ Displaystyle D (е) = О (Q_ {0} (е) ^ {3})}$

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

Гипотеза о чувствительности

Для булевой функции , то чувствительность из определяются как максимальная чувствительность по всем , где чувствительности при этом количестве однобитовых изменений в этом изменить значение . Чувствительность связана с понятием общего влияния анализа булевых функций , которое равно средней чувствительности по всем параметрам . ${\ displaystyle f: \ {0,1 \} ^ {n} \ к \ {0,1 \}}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle x}$

Гипотеза о чувствительности - это гипотеза о том, что чувствительность полиномиально связана со сложностью запроса; то есть, существует показатель такой , что для всех , и . Это можно показать с помощью простого аргумента , поэтому гипотеза конкретно касается поиска нижней границы чувствительности. Поскольку все ранее обсуждавшиеся меры сложности полиномиально связаны, точный тип меры сложности не имеет значения. Однако это обычно формулируется как вопрос о связи чувствительности с чувствительностью к блоку. ${\ displaystyle c, c '}$${\ displaystyle f}$${\ Displaystyle D (е) = О (s (f) ^ {c})}$${\ Displaystyle s (е) = О (D (е) ^ {с '})}$${\ Displaystyle s (е) \ Leq D (е)}$

Чувствительности блока из , обозначается , определяется как максимальная чувствительность блока над всем . Чувствительность блока at - это максимальное количество непересекающихся подмножеств , так что для любого из подмножеств переключение битов, соответствующих изменению значения . ${\ displaystyle f}$${\ displaystyle bs (f)}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle t}$${\ Displaystyle S_ {1}, \ ldots, S_ {t} \ подмножество [п]}$${\ displaystyle S_ {i}}$${\ displaystyle x}$${\ displaystyle S_ {i}}$${\ displaystyle f (x)}$

Поскольку чувствительность блока занимает максимум за более широкий выбор подмножеств, . Кроме того, чувствительность к блокам полиномиально связана с ранее обсужденными мерами сложности; например, статья Нисана о чувствительности к блокам показала это . Таким образом, можно было бы перефразировать гипотезу чувствительности , как показывает , что для некоторых , . В 1992 году Нисан и Сегеди предположили, что этого достаточно. Это было бы сложно, поскольку Рубинштейн в 1995 году показал квадратичное разделение между чувствительностью и чувствительностью к блокам. ${\ Displaystyle s (е) \ Leq BS (е)}$${\ Displaystyle шс (е) \ leq D (е) = О (шс (е) ^ {4})}$${\ displaystyle c}$${\ displaystyle bs (f) = O (s (f) ^ {c})}$${\ displaystyle c = 2}$

В июле 2019 года, через 27 лет после первоначального высказывания гипотезы, Хао Хуан из Университета Эмори доказал гипотезу о чувствительности, продемонстрировав это . Это доказательство особенно лаконично, доказывая это утверждение на двух страницах, когда предыдущий прогресс в отношении гипотезы о чувствительности был ограничен. ${\ displaystyle bs (f) = O (s (f) ^ {4})}$

Резюме известных результатов

Наиболее известные разделения по комплексным мерам по состоянию на октябрь 2020 г.

	${\ displaystyle D}$	${\ displaystyle R_ {0}}$	${\ displaystyle R_ {2}}$	${\ displaystyle C}$	${\ displaystyle RC}$	${\ displaystyle bs}$	${\ displaystyle s}$	${\ displaystyle Q_ {0}}$	${\ displaystyle \ deg}$	${\ displaystyle Q}$	${\ displaystyle {\ widetilde {\ deg}}}$
${\ displaystyle D}$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
${\ displaystyle R_ {0}}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
${\ displaystyle R}$	1	1		2	2, 3	2, 3	3, 6	1,5, 3	2, 3	3, 4	4
${\ displaystyle C}$	1	1	1, 2		2	2	2,22, 5	1,15, 3	1,63, 3	2, 4	2, 4
${\ displaystyle RC}$	1	1	1	1		1,5, 2	2, 4	1,15, 2	1,63, 2	2	2
${\ displaystyle bs}$	1	1	1	1	1		2, 4	1,15, 2	1,63, 2	2	2
${\ displaystyle s}$	1	1	1	1	1	1		1,15, 2	1,63, 2	2	2
${\ displaystyle Q_ {0}}$	1	1,33, 2	1,33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
${\ displaystyle \ deg}$	1	1,33, 2	1,33, 2	2	2	2	2	1		2	2
${\ displaystyle Q}$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\ displaystyle {\ widetilde {\ deg}}}$	1	1	1	2	2	2	2	1	1	1

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

Число в -й строке и -м столбце обозначает границы экспоненты , которая представляет собой точную нижнюю грань всех удовлетворяющих всем логическим функциям . Например, запись в строке D и столбце s - «3, 6», так что для всех существует такая функция , что . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle c}$${\ displaystyle k}$${\ Displaystyle А (е) = О (В (е) ^ {к})}$${\ displaystyle f}$${\ Displaystyle D (е) = О (\ OperatorName {s} (f) ^ {6 + о (1)})}$${\ displaystyle f}$${\ displaystyle g}$${\ Displaystyle D (g) = \ Omega (\ operatorname {s} (g) ^ {3-o (1)})}$

Смотрите также

• Сравнительная сортировка
• Древо решений
• Гипотеза Андераа – Карпа – Розенберга
• Минимальное остовное дерево # Деревья решений

Рекомендации

Обзоры

• Бурман, Гарри; де Вольф, Рональд (2002), "Меры сложности и принятие решения Сложности: Обзор" (PDF) , теоретическая информатика , 288 (1): 21-43, DOI : 10.1016 / S0304-3975 (01) 00144-X