О средней временной сложности деревьев решений

• Автор: Чикалов, Игорь Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Нижний Новгород
• Количество страниц: 73 с.

Содержание
1 Введение

1.1 Общая характеристика работы

1.2 Основные определения и обозначения

1.3 Основные результаты работы

2 Деревья решений для тестовых таблиц

2.1 Оценки средней взвешенной глубины

2.2 О возможности декомпозиции задачи

2.3 Алгоритм А построения деревьев решений

3 Некоторые приложения

3.1 О средней глубине деревьев решений, реализующих булевы функции

3.2 О бинарных программах с минимальной средней глубиной
4 Задачи над системами проверок
4.1 Об оценках средней глубины деревьев решений, зависящих только от энтропии
4.2 Критерий полиномиальности алгоритма А
Список литературы

1 Введение
1.1 Общая характеристика работы
Деревья решений используются для представления знаний и описания алгоритмов решения различных прикладных задач. Многие из них могут быть сформулированы как задача идентификации, которая характеризуется универсумом объектов, множеством проверок и разбиением множества объектов на классы, и состоит в нахождении класса, к которому принадлежит объект, путем вычисления для него значений проверок. Сложность деревьев решений и алгоритмы их построения исследуются в теории тестов [3, 4, 10, 11, 13, 20, 23, 27, 43], теории грубых множеств [50, 51, 52, 53, 61], теории вопросников [18, 54], теории таблиц решений [39, 55], теории поиска [29], теории машинного обучения [38, 44, 58]. Из приложений, в которых широко используются деревья решений, следует отметить непроцедурные языки программирования [39], анализ сложности алгоритмов [5], дискретную оптимизацию [7, 8, 9, 12], распознавание образов [2, 20, 27, 42], диагностику неисправностей [16, 19, 23, 60], вычислительную геометрию [57]. Средняя временная сложность деревьев решений исследована для многих частных случаев задач идентификации.
В диссертационной работе обобщен ряд известных результатов о средней временной сложности детерминированных деревьев решений и изучены некоторые новые проблемы. Основной целью работы является получение оценок минимальной средней временной сложности деревьев решений для задач идентификации и разработка эффективных алгоритмов построения деревьев решений для некоторых классов систем проверок. При доказательстве результатов использовались комбинаторные методы, методы теории вероятностей и теории сложности алгоритмов, а также методы и подходы из различных разделов дискретной математики и математической кибернетики. Результаты, приведенные в диссертации, носят преимущественно теоретический характер. Они могут быть использованы для разработки эффективных алгоритмов построения деревьев решений и при анализе сложности представления различных объектов деревьями решений.
Диссертация состоит из четырех глав и списка литературы. Первая глава носит вводный характер. В ней дана общая характеристика работы, приведен обзор некоторых известных результатов, введены основные определения и обозначения и кратко описаны результаты работы.
Во второй главе рассматриваются оценки минимальной средней временной сложности деревьев решений и алгоритм построения оп-

тимальных деревьев решений. Эта глава состоит из трех параграфов. В первом параграфе приведены нижняя оценка средней взвешенной глубины дерева решений для некоторых типов задач, верхняя оценка средней взвешенной глубины, а также более точная оценка средней глубины. Ранее были известны верхняя и нижняя оценки минимальной средней временной сложности деревьев решений для задач идентификации с полным набором проверок. Эти оценки зависят только от энтропии распределения вероятностей, они следуют из результатов теории кодирования [6, 59] и хорошо известны в теории поиска (см., например, [29]). В этом параграфе данные оценки обобщены на случай средней взвешенной глубины деревьев решений для произвольной задачи идентификации. Во втором параграфе описано достаточное условие декомпозиции задачи, при выполнении которого оптимальное дерево решений для задачи может быть получено из оптимальных деревьев решений для нескольких подзадач с помощью простых преобразований. Также этот параграф содержит результат, свидетельствующий о том, что верхняя оценка средней глубины из параграфа 2.1 близка к неулучшаемой. В третьем параграфе приведен алгоритм А построения оптимального (в смысле одной из нескольких мер сложности) дерева решений по задаче, представленной в форме тестовой таблицы. Идея алгоритма близка к дескриптивным методам оптимизации [7, 8, 9, 12].
Третья глава посвящена некоторым приложениям, в которых может быть эффективно использован аппарат деревьев решений. Эта глава состоит из двух параграфов. В первом параграфе изучается средняя глубина деревьев решений, реализующих булевы функции. Для каждого замкнутого класса булевых функций [28] получены верхняя и нижняя оценки значения функции шенноновского типа, характеризующей рост средней глубины деревьев решений в худшем случае с ростом числа переменных функции. Также проведено сравнение полученных результатов с аналогичными результатами для глубины деревьев решений, приведенными в работах [14, 41]. Используемое в доказательствах понятие разбиения таблицы функции сходно с понятием системы непересекающихся покрытий булева куба, использующимся в спектральных методах цифровой логики [30], но для оценки вида покрытия используются не спектральные свойства функции, а информация о принадлежности функции к конкретному замкнутому классу. В некоторых случаях это позволяет улучшить нижние оценки средней глубины деревьев решений (например, для функции голосования и функции логической суммы). Во втором параграфе показано, что каждая бинарная программа, имеющая минимальную среднюю глубину, обладает свойством бесповторности. Этот факт позволяет для

основным проверкам, и Я (Г) < Я(Г) — 1.
2) Пусть Tzir{path(r,vt+i)) ф Тгтг(раЩГ,ум))(/?,а) для а = 0,1. Тогда из неравенств (i) и (ii) следует, что t > 3, и для некоторых fci,&2 G {1,...,£} вершине Vk± приписана проверка из множества и вершине Vk2 приписана проверка из множества
{/ii •■•>/«}• Обозначим а число, приписанное вершине ut+i. Припишем вершине Vt+1 проверку проведем из нее две дуги, и припишем им числа 0 и 1 соответственно. Добавим к дереву решений Г две вершины wo и W. припишем им число а и преобразуем дерево Г так, чтобы для а = 0,1 дуга е(Г, vt+i, сг) входила в вершину wa. Обозначим Г дерево, полученное в результате этого преобразования. Очевидно, что Г - дерево решений для задачи z, решающее z, и h(t, Р) = h(T, Р) + ■ Обозначим £ полный путь в дереве Г,
заканчивающийся в вершине wo- Тогда Щ(£) + Ni(£) — N(Tzn(£), Р). Применим к пути £ операцию упорядочения пути и обозначим полученное дерево Г. Из леммы 2.2.1 следует, что Г - дерево решений для задачи z, решающее z, и h(F, Р) < h(t,P) — р) - Тогда
h(T,P) < h(T,P), и дерево решений Г оптимально для z и Р. Легко видеть, что каждый полный путь в дереве Г упорядочен по основным проверкам, и Я(Г) < Я(Г) — 1.
Применим указанное выше преобразование, взяв дерево Г в качестве исходного дерева Г, и будем повторять эту процедуру до тех пор, пока R(T) > 0. Таким образом, за конечное число шагов мы получим искомое дерево решений. □
Доказательство теоремы 2.2.1. Покажем, что дерево решений Ф = Ф(Го, Г1,..., Гот) решает задачу z. Обозначим А,..., Ат классы эквивалентности задачи zq. Пусть TZo = {<г,..., dm}, где dl = (/{J(a,),
...,/° (a,-)), a* E A[, i = 1,,m. Рассмотрим произвольную строку 5 = (5?,... Д°о,..., 6?,..., 6%J Е Tz. Пусть (<*§,..., 5®e) = имеем 1/(5) = щ(5[,..., 5гп ). Следовательно, дерево Ф решает задачу z.
Покажем, что Ф - оптимальное дерево решений для г и Р. Из леммы 2.2.4 следует, что существует дерево решений G для задачи z, решающее z, оптимальное для z и Р, которое полностью упорядочено. Для г = 1 ,...,т обозначим V{ вершину дерева G такую, что