Деревья и сфера их применения

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

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

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

Рассмотрим более подробно различные применения деревьев: дерево проблем; дерево свойств; дерево целей.

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

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

иерархическая структура свойств, формирующих качество; классификация свойств, определяющих качество; схема декомпозиции свойств, выражающих качество.

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

Дерево целей представляет теоретико-графовую модель, используемую для декомпозиционного анализа возможности достижения некоторой сложной цели.

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

При построении дерева целей чаще всего используется нижнестороннее дерево (т. е. растущее вниз), реже — верхнестороннее (т. е. растущее вверх) или правостороннее (растущее слева направо). Дерево целей обычно изображают в строгой или нестрогой форме графа.

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

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

Известны случаи, когда дерево целей имело 8-10 уровней ветвления и на последнем уровне помещалось свыше 2000 подцелей. Например, в дереве целей, использовавшемся в 1965-1968 годах в США для перспективного планирования деятельности НАСА.

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

Основная сфера применения дерева целей: в планировании (системный анализ плановых решений, анализ поставленных целей, распределение бюджетных ассигнований, научно-техническое прогнозирование);

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