Содержание к диссертации
Введение
1. «И/ИЛИ» деревья решения задач 7
1.1 Понятие задачи 7
1.1.1 Формулировка задачи. Неопределенности 8
1.1.2 Представление задачи в пространстве состояний 10
1.1.3 Представление задачи в пространстве задач 12
1.2 «И/ИЛИ» деревья 15
1.2.1 Определение дерева в теории графов 15
1.2.2 «И/ИЛИ» дерево целей 17
1.2.3 Операции над графами 19
1.3 Получение знаний 23
1.3.1 Задачи формирования знаний 25
1.3.2 Классификация систем добычи данных 32
1.4. Выводы к главе 1 35
2. Технология построения обобщенного «И/ИЛИ» дерева 37
2.1 «И» и «И/ИЛИ» деревья 37
2.2 Совпадающие кластеры 38
2.3 Понятие полного и частичного совпадения «И» деревьев 40
2.4 Понятие полного и частичного совпадения «И/ИЛИ» деревьев 41
2.5 Построение обобщенного «И/ИЛИ» дерева 42
2.6 Разделение пересекающихся кластеров 47
2.7 Сходимость процесса построения обобщенного «И/ИЛИ» дерева 51
2.8 Выводы к главе 2 58
3. Экпериментальные исследования 59
3.1 Цели и задачи экспериментального исследования 59
3.2 Описание программно - аппаратной системы для проведения эксперимента 59
3.3 Исходные данные 63
3.4 Ход эксперимента 64
3.5 Выводы к главе 3 93
Заключение 94
Список литературы 96
- Представление задачи в пространстве задач
- Задачи формирования знаний
- Построение обобщенного «И/ИЛИ» дерева
- Описание программно - аппаратной системы для проведения эксперимента
Введение к работе
Актуальность темы. Одним из способов описания структуры предметной области, в решающих системах, основанных на знаниях, являются «И/ИЛИ» деревья решения задач. При этом обобщенное «И/ИЛИ» дерево должно быть априори задано в явном виде. Решающая система, взаимодействуя с пользователем, способна в процессе решения задачи строить решающее «И» дерево для конкретной задачи, однако, такие системы не способны к накоплению обобщенного знания о структуре предметной области. Построение же, корректировка и дополнение обобщенного «И/ИЛИ» дерева производится с помощью компонента «приобретение знаний», пользователем которой является инженер по знаниям (когнитолог). В этих условиях актуальной является разработка технологии построения адекватной базы знаний и соответствующего обобщенного «И/ИЛИ» дерева решающей системой в процессе взаимодействия с пользователем-природоведом.
Цель работы. Целью диссертационной работы является разработка технологии построения решающей системой «И/ИЛИ» дерева, изоморфного статической структуре оригинала.
Для достижения цели решаются следующие задачи:
1. Анализ применимости операции над графами теории графов к «И/ИЛИ» деревьям решения задач.
2. Определение операции объединения вершин «И/ИЛИ» дерева, представляющих цели в пространстве целей.
3. Определение операции объединения решающих «И» деревьев в «И/ИЛИ» дерево.
4. Разработка алгоритма объединения решающих «И» деревьев в «И/ИЛИ» дерево.
5. Исследование сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.
Методы исследований. При решении поставленных задач использовались методы: дискретной математики, теории графов, теории алгоритмов, теории решения задач, теории классификации, кластерного анализа, теории искусственного интеллекта, теории экспертных систем. Научная новизна работы:
1. Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей.
2. Определена операция объединения «И/ИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач.
3. Сформулировано определение сходимости итерационного процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Данное определение базируется на измерении степени сходства получаемых «И/ИЛИ» деревьев на каждом шаге объединения «И/ИЛИ» дерева с очередным решающим «И» деревом задачи данного класса. Сформулирован и доказан критерий сходимости такого процесса.
4. Выведена теоретическая оценка скорости сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.
Практическая ценность работы. Разработан программно-аппаратный комплекс, позволяющий осуществлять объединение решающих «И» деревьев задач анализа сложных в обобщенное «И/ИЛИ» дерево. Использование результатов диссертации. Основные результаты работы были внедрены в Институте леса им. В.Н. Сукачёва СО РАН, а также в учебном процессе СФУ.
Личный вклад автора. Автором лично получены основные выносимые на защиту результаты. В работах, опубликованных лично и в соавторстве, автором разработаны теоретические основы, проведены аналитические выкладки и получены экспериментальные результаты.
Апробация работы. Материалы работы обсуждались: на семинаре кафедры «Системы искусственного интеллекта» Красноярского государственного технического университета (2008г.); на семинаре лаборатории мониторинга леса в Институте леса им. В.Н. Сукачёва СО РАН (2008г.).
Публикации. По материалам исследований опубликовано пять статей, из которых: одна опубликована в сборниках, рекомендованных ВАК, две статьи депонированы.
Структура и объем диссертации. Диссертационная работа включает: содержание, введение, три главы, и заключение. Работа содержит 104 страницы машинописного текста, 43 рисунка и 21 таблицу. Список литературы содержит 110 наименований.
В первой главе проводится описание методов представления статической структуры оригинала в виде графоподобных структур. Анализируется соответствие понятия «И/ИЛИ» дерева решения задач понятию дерева в теории графов. Проводится анализ применимости операций над графами теории графов к «И/ИЛИ» деревьям. Анализируются существующие подходы к формированию баз знаний решающих систем. Во второй главе вводится понятие совпадающих кластеров и определяется операция объединения совпадающих кластеров. Вводится понятие совпадающих «И/ИЛИ» деревьев решения задач. Определяется операция объединения «И» дерева с «И/ИЛИ» деревом, предлагается алгоритм объединения. Дается определение сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач, формулируется и доказывается критерий сходимости. Формулируются теоретические оценки скорости сходимости такого процесса. В третьей главе на примере решения задач анализа космофотоснимков проиллюстрирован процесс построения обобщенного «И/ИЛИ» дерева и исследована сходимость этого процесса, описаны начальные данные и ход эксперимента. В заключении сформулированы основные научные и практические результаты данной работы.
Представление задачи в пространстве задач
Целью задачи формирования знаний является производство нового знания, которое решающая система сможет в дальнейшем применить для решения задач пользователя. Авторы [50,51] выделяют семь подходов к формированию знаний: 1) классификация, 2) регрессия, 3) кластеризация, 4) анализ ассоциаций, 5) прогнозирование временных последовательностей (рядов), 6) агрегирование (обобщение), 7) обнаружение отклонений. Первые два подхода относят к управляемому обучению (обучение с учителем), а остальные – к неуправляемому (обучение без учителя).
В [52] дается общее понятие обучения: обучение – формирование и накопление опыта отражения оригинала при достижении некоторой цели в процессе взаимодействия с оригиналом (и) или обучающей системой.
Классификация является наиболее распространенным методом анализа данных. Существует два способа постановки задачи классификации [23]: 1) В признаковом пространстве X задано n классов множеством своих эталонов , (x, y) – функция расстояния или метрика, определенная в пространстве X. Всякий объект xi относится к тому классу, для которого (xсрi, xi) принимает минимальное значение. Таким образом, всё пространство X разбивается на n кластеров. В этом случае любой исследуемый объект всегда может быть отнесён к одному из n известных классов. Данный способ классификации основан на концепции «всезнайства» классификатора. 2) В признаковом пространстве X задано n классов множеством своих эталонов , (x, y) – метрика, определенная в пространстве X. Для каждого класса задан критерий компактности i. Всякий объект xi относится к тому классу, для которого (xсрi, xi) i, т.е. расстояние между исследуемым объектом и эталоном класса, удовлетворяет критерию компактности данного класса. Если же объект не будет отнесён ни к одному известному классу, он будет классифицирован как «неизвестный» или как фон. Данный способ классификации учитывает неполноту знаний классификатора, устраняя проблему «всезнайства» предыдущего. Необходимым условием решения указанных задач классификации является требование непересекаемости [53] подмножеств множества объектов в пространстве X. Сформулированные задачи классификации основаны на вычислении меры сходства исследуемых объектов. Для формализации понятия сходства вводится функция расстояния или метрика (x, y) в пространстве объектов X. Поэтому алгоритмы, основанные на анализе сходства объектов, часто называют метрическими алгоритмами, даже в тех случаях, когда функция не удовлетворяет всем аксиомам метрики. В качестве методов решения задачи классификации могут использоваться алгоритмы типа Lazy-Learning [55,56], в том числе известные алгоритмы ближайшего соседа и k-ближайших соседей [57,58], байесовские сети [59-61], деревья решений [62-67], индукция символьных правил [68,69], нейронные сети [70]. Регрессионный анализ [71,72] используется в том случае, если отношения между переменными могут быть выражены количественно в виде некоторой комбинации этих переменных. Полученная комбинация далее используется для предсказания значения, которое может принимать целевая (зависимая) переменная, вычисляемая на заданном наборе значений входных (независимых) переменных. В простейшем случае для этого используются стандартные статистические методы, такие как линейная регрессия. Формально задача восстановления регрессии формулируется следующим образом: Задано пространство объектов X и множество возможных ответов Y. Существует неизвестная целевая зависимость y : X Y, значения которой известны только на объектах обучающей выборки X = (xi, yi)i=1, yi = y (xi). Требуется построить алгоритм a: X Y, аппроксимирующий целевую зависимость y . Основные проблемы, с которыми сталкиваются при решении задач классификации и регрессии – это неудовлетворительное качество исходных данных, в которых встречается как шум, так и пропущенные значения, различные типы атрибутов (числовые и категорические), разная значимость атрибутов, а также, так называемые, проблемы "overfitting" и "underfitting" [71]. Суть первой из них, заключается в том, что классификационная функция при построении "чересчур хорошо" адаптируется к данным. И встречающийся в данных шум эта функция пытается интерпретировать как часть внутренней структуры данных. Очевидно, что такой классификатор будет некорректно работать в дальнейшем с другими данными, где характер шума будет несколько иной. Вторая проблема обозначают ситуацию, когда слишком велико количество ошибок при проверке классификатора на обучающем множестве. Это означает, что особых закономерности в данных не было обнаружено и, либо их нет вообще, либо необходимо выбрать иной метод их обнаружения. Кластеризация [54,73] логически продолжает идею классификации на более сложный случай, когда сами классы не предопределены. Результатом кластеризации является определение присущего исследуемым данным разбиения на группы. Задача кластеризации заключается в следующем: Задана обучающая выборка X = {x1,...,x} X и функция расстояния между объектами (x, y). Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике , а объекты разных кластеров существенно отличались. При этом каждому объекту xi X приписывается метка (номер) кластера yi. Алгоритм кластеризации – это функция a: X Y , которая любому объекту x X ставит в соответствие метку кластера y Y . Множество меток Y может быть задано априори. В противном случае решается задача определения оптимального числа кластеров, с точки зрения того или иного критерия качества кластеризации. Решение задачи кластеризации принципиально неоднозначно и весьма субъективно в силу нескольких причин: 1) Не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд достаточно разумных критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию. Все они могут давать разные результаты. 2) Число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым критерием. 3) Результат кластеризации сильно зависит от метрики , выбор которой, как правило, субъективен и определяется экспертом. Кластеризация отличается от классификации тем, что метки исходных объектов yi изначально не заданы, и часто неизвестно само множество Y. Цели кластеризации могут быть различными в зависимости от особенностей конкретной прикладной задачи: 1) Выявить структуру множества объектов X путем разбиения его на группы схожих объектов. 2) Сократить объём хранимых данных в случае сверхбольшой выборки X, заменив элементы кластера его эталоном. 3) Выделить неклассифицированные объекты, которые не подходят ни к одному из кластеров. Эту задачу называют одноклассовой классификацией или обнаружением нетипичности, новизны. В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а число кластеров может быть любым. В третьем случае наибольшую важность имеют объекты, не вписывающиеся ни в один из кластеров.
Задачи формирования знаний
Системы добычи данных, как правило, интегрируют в себе несколько подходов к добыче данных. При этом в каждой системе имеется один основной подход, на который делается главная ставка. Авторами [50,51] приводится классификация систем добычи данных по основному используемому подходу к добыче данных: 1) статистические методы; 2) нейронные сети; 3) деревья решений; 4) системы рассуждения на основе аналогичных случаев; 5) нечеткая логика; 6) генетические алгоритмы; 7) эволюционное программирование; 8) алгоритмы ограниченного перебора; Статистические методы [90-93] включают в себя: корреляционный, регрессионный, факторный анализ и другие. Недостатком систем, использующих статистические методы, является требование к специальной подготовке пользователя. Существенным недостатком статистических пакетов, ограничивающим их применение, является то, что большинство методов, входящих в состав пакетов, опираются на статистическую парадигму, в которой главными фигурантами служат усредненные характеристики выборки, которые при решении сложных задач имеют характер фиктивных величин. Нейронные сети [94-96] относятся к классу нелинейных адаптивных систем с архитектурой, условно имитирующей нервную ткань из нейронов. Математическая модель нейрона представляет собой некоторый универсальный нелинейный элемент с возможностью широкого изменения и настройки его характеристик. Основным недостатком нейросетевой парадигмы является необходимость иметь очень большой объем обучающей выборки. Другой существенный недостаток заключается в том, что всякая нейронная сеть, в том числе и обученная, представляет собой черный ящик. Знания, зафиксированные как веса нескольких сотен межнейронных связей, поддаются анализу и интерпретации человеком. Деревья решений [97-102] являются одним из наиболее популярных подходов к решению задач добычи данных. Они создают иерархическую структуру классифицирующих правил типа "если-то", имеющую вид дерева. Для того чтобы решить, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Постепенно принимая решение в каждом узле дерева, начиная от корня, добираемся до одного из возможных вариантов решения. Большинство систем поддержки принятия решения используют именно этот метод. Нечеткая логика [95,103,104] применяется для таких наборов данных, где причисление данных к какой-либо группе является вероятностью, находящейся в интервале от 0 до 1, но не принимающей крайние значения. Четкая логика манипулирует результатами, которые могут быть либо истиной, либо ложью. Нечеткая логика применяется в тех случаях, когда необходимо манипулировать степенью "может быть" в дополнении к "да" и "нет". Генетические алгоритмы [105-108], ориентированные в первую очередь на решение разнообразных комбинаторных задач и задач оптимизации, используются и как метод добычи данных. Достоинство генетические алгоритмов в удобстве их распараллеливания. Недостаток заключается в том, что постановка задачи в терминах генетических алгоритмов не дает возможности проанализировать статистическую значимость получаемого с их помощью решения. Кроме того, для постановки задачи в терминах генетических алгоритмов пользователь должен обладать специальными знаниями в этой области.
Суть эволюционного программирования [95,109,110] заключается в том, что гипотезы о виде зависимости целевой переменной от других переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Если это универсальный язык, то теоретически на нем можно выразить зависимость любого вида. Процесс построения этих программ строится подобно эволюции в мире программ. Когда система находит программу, достаточно точно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Таким образом, система строит несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Алгоритмы ограниченного перебора [50,102] вычисляют частоты комбинаций простых логических событий в подгруппах данных. Ограничением служит длина комбинации простых логических событий. На основании анализа вычисленных частот делается заключение о полезности той или иной комбинации для установления ассоциации в данных, для классификации, прогнозирования и пр.
В заключение параграфа 1.3 можно отметить, что среди рассмотренных подходов и систем добычи знаний не обнаружено методов, которые бы позволяли решающей системе строить обобщенные «И/ИЛИ» деревья, описывающие структуру предметной области. Распространены системы, которые могут строить решающие древовидные структуры, но данные структуры представляют собой решение конкретной задачи и не описывают обобщенной структуры предметной области. Вместе с тем существуют системы ориентированные на автоматизированное построение «И/ИЛИ» деревьев, но данные системы ориентированы на работу с инженером по знаниям, а не пользователем-природоведом. 1. Установлено, что «И/ИЛИ» дерево, используемое для представления решения сложных задач, существенно отличается от дерева теории графов. Основное отличие заключается в том, что теория графов оперирует с наборами вершин и ребер дерева, как с априори определенными множествами. При этом вершины и отношения между вершинами в дереве решения задач могут определяться только в процессе решения задачи. 2. Операции над графами и деревьями теории графов малоприменимы к «И/ИЛИ» деревьям решения задач, т.к. порождены теоретико-множественными операциями над априори заданными множествами вершин и ребер дерева. Соответствующие операции над «И/ИЛИ» деревьями формально не определены, т.к. множества вершин не могут быть поименованы для применения к ним теоретико-множественных операций. Кроме того, множество вершин «И/ИЛИ» дерева, являющегося результатом операций с другими деревьями, определяется только в процессе выполнения данных операций. 3. Установлено, что решающие «И» деревья могут быть построены решающей системой в процессе машинного обучения (обучения без учителя) с помощью различных методов формирования знаний. При этом решающая система не способна строить обобщенные «И/ИЛИ» деревья, описывающие структуру оригинала. Обобщенное «И/ИЛИ» дерево задается априори и может корректироваться и дополняться когнитологом посредством компоненты «приобретение знаний».
Построение обобщенного «И/ИЛИ» дерева
Видно, что с увеличением числа операций объединения «И/ИЛИ» дерева с «И» деревьями, коэффициенты изменения вершин и прироста дерева уменьшаются. Исходя из оценки, данной в следствии 1, при максимальном количестве узлов в решающих «И» деревьях M = 7 коэффициент прироста дерева достигнет заданной точности = 0,01 не более чем за шагов. При этом на первом шаге d(T1,G2) = 0,429 и , а на третьем d(G3,G4) = 0,0467 и т.е. изменения структуры дерева кластеров имеет все менее выраженный характер. Это позволяет предположить, что требуемая точность = 0,01 может быть достигнута гораздо быстрее. Из этого можно сделать вывод, что решающие «И» деревья для задач одного класса обладают большей степенью сходства, чем используемое в теоретической оценке требование совпадения корневых вершин. 1. Экспериментально продемонстрирована работоспособность технологии построения обобщенных «И/ИЛИ» деревьев путем многократного объединения решающих «И» деревьев. 2. Процесс построения обобщенного «И/ИЛИ» дерева проиллюстрирован на примере решения задач анализа космофотоснимков лесов Саян, сформировано «И/ИЛИ» дерево 3. Исследована сходимость процесса формирования «И/ИЛИ» дерева. На каждом шаге объединения «И/ИЛИ» дерева с «И» деревом вычислены коэффициенты приоста дерева и коэффициенты изменения кластера. 4. Экспериментально установлено, что процесс формирования «И/ИЛИ» дерева для класса задач сходится значительно быстрее приведенной точной верхней грани скорости сходимости. Это указывает на наличие большего сходства между решающими «И» деревьями задач одного класса, чем совпадение корневых вершин. В заключение кратко сформулируем положения, характеризующие научную и практическую значимость работы. К основным научным результатам относятся: 1. Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей. 2. Определена операция объединения «И/ИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач. 3. Сформулировано определение сходимости итерационного процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Данное определение базируется на измерении степени сходства получаемых «И/ИЛИ» деревьев на каждом шаге объединения «И/ИЛИ» дерева с очередным решающим «И» деревом задачи данного класса. Сформулирован и доказан критерий сходимости такого процесса. 4. Выведена теоретическая оценка скорости сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Практическая ценность диссертационной работы заключается в разработке программно-методического комплекса, реализующего алгоритмы построения объединенного кластера для пары совпадающих кластеров, объединения «И» деревьев в «И/ИЛИ» дерево, расчета коэффициентов изменения деревьев. С помощью разработанного комплекса проверена работоспособность предложенной технологии формирования обобщенного «И/ИЛИ» дерева на примере анализа космофотоснимков лесов Саян.
Описание программно - аппаратной системы для проведения эксперимента
Если из вершины выходят только ребра, связанные отношением «И», то такая вершина называется «И» вершиной.
Если из вершины выходят только ребра, связанные отношением «ИЛИ», то такая вершина называется «ИЛИ» вершиной. Если из вершины выходит только одно ребро, то такую вершину можно считать как «И» вершиной, так и «ИЛИ» вершиной. Возможны ситуации, когда из одной вершины выходят как ребра, связанные отношением «И», так и ребра, связанные отношением «ИЛИ». Такую вершину нельзя отнести к одному типу вершин. Граф, содержащий такие вершины, может быть преобразован в эквивалентный граф, содержащий только «И» и «ИЛИ» вершины. Делается это включением в граф дополнительных вершин. Вершину P нельзя отнести к вершинам «И» или «ИЛИ» типа (рис. 1.2а). Путем добавления вершин P11 и P12 получается граф (рис. 1.2б), где каждую вершину можно отнести к «И» или «ИЛИ» типу. При этом образовавшиеся ребра PP11 и PP12 означают не переход от задачи P к подзадачам P11 или P12, а переформулировку задачи P. Вершина «И/ИЛИ» графа, не имеющая родительских вершин и соответствующая исходной задаче, называется начальной вершиной. Вершины, не имеющие дочерних вершин и соответствующие простым задачам, называются заключительными вершинами. Цель процесса поиска, осуществляемого на «И/ИЛИ» графе, – показать, что начальная вершина разрешима. Определение разрешимой вершины «И/ИЛИ» графа дается рекурсивно [11]: - Заключительные вершины разрешимы, т.к. соответствуют элементарным задачам. - Если вершина, не являющейся заключительной, относится к типу «ИЛИ», то она разрешима тогда и только тогда, когда разрешима, по крайней мере, одна из ее дочерних вершин. - Если вершина, не являющейся заключительной, относится к типу «И», то она разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин. Если у некоторой вершины «И/ИЛИ» графа, не являющейся заключительной, нет дочерних вершин, это означает, что данная вершина неразрешима. Определение неразрешимой вершины «И/ИЛИ» графа дается рекурсивно [11]: - Вершины, не являющиеся заключительными и не имеющие дочерних вершин, неразрешимы. - Если вершина, не являющейся заключительной, относится к типу «ИЛИ», то она неразрешима тогда и только тогда, когда неразрешима каждая из ее дочерних вершин. - Если вершина, не являющейся заключительной, относится к типу «И», то она неразрешима тогда и только тогда, когда неразрешима хотя бы одна из ее дочерних вершин. «И/ИЛИ» граф редукции задачи на подзадачи может задаваться в явном и неявном виде. В неявном виде «И/ИЛИ» граф задается в виде описания исходной задачи и операторов редукции задачи. Процесс решения задачи в этом случае состоит в построении такого подграфа «И/ИЛИ» графа, из которого видно, что начальная вершина, соответствующая исходной задаче, разрешима. В заключение параграфа 1.1 можно отметить, что «И/ИЛИ» граф редукции задачи на подзадачи является способом описания структуры оригинала, другими словами, «И/ИЛИ» граф изоморфен структуре оригинала. Наличие в явном виде априори заданного «И/ИЛИ» графа устраняет неопределенность по статической структуре оригинала в формулировке задачи. Во многих источниках [20-25] в смысле понятия «И/ИЛИ» графа используется понятие «И/ИЛИ» дерева. При этом модель «И/ИЛИ» дерева целей лишь частично соответствует строгому определению понятия "дерево" теории графов. В теории графов существует три строгих определения дерева [13]: Определение 1: Неориентированное дерево – это связный неориентированный граф без циклов. Определение 2: Неориентированное дерево – это связный неориентированный граф, содержащий n вершин и n-1 ребер. Определение 3: Неориентированное дерево – это неориентированный граф, в котором каждая пара вершин связана одной и только одной цепью. Данные три определения дерева являются эквивалентными.
Пусть в дереве G отмечена вершина v0. Эту вершину называют корнем дерева G или корневой вершиной, а само дерево G – деревом с корнем. В таком дереве можно естественным образом ориентировать ребра. Вершину vi ребра vivj можно соединить единственной цепью L с корнем v0. Если эта цепь не содержит ребра vivj, в последнюю вводится ориентация от vi к vj; в противном случае – от vj к vi. Такая ориентация согласована с ориентацией того же ребра, определенной через вершину vj. Действительно, если цепь L не содержит ребра vivj, то, добавив это ребро, получим единственную цепь L1, связывающую v0 и vj и проходящую через рассматриваемое ребро. Если же цепь L содержит ребро vivj, то, отбросив ее, получаем цепь L1, связывающую v0 и vj и не содержащую этого ребро.
Ориентированное таким образом дерево с корнем называется ориентированным деревом. В нем все ребра имеют направление от корня (рис 1.3). Если изменить направление всех ребер ориентированного дерева на противоположные (к корню), получится ориентированный граф, который тоже является ориентированным деревом. Деревья, ориентированные к корню часто называют сетью сборки.
