Программные продукты и системы

Структура многих NP-трудных задач комбинаторной оптимизации может быть описана гиперграфом. Такие задачи возникают в системах принятия решений, БД, при анализе информационных и коммуникационных сетей, конструкторском проектировании радиоэлектронной и вычислительной аппаратуры, лингвистической трансляции, при формировании трафика компьютерных сетей и т.д. Дерево декомпозиции гиперграфа дает возможность организовать процесс поиска оптимального решения по принципу «разделяй и властвуй». Если древовидная ширина гиперграфа ограничена сверху некоторой константой, то многие NP-трудные задачи комбинаторной оптимизации могут быть решены за полиномиальное время. Древовидная ширина – это числовая характеристика гиперграфа, определяемая через оптимальное дерево декомпозиции. К сожалению, сама задача нахождения оптимального дерева декомпозиции также NP-трудная, поэтому в алгоритмической практике востребованы эвристики, позволяющие получать хорошие деревья декомпозиции за разумное время. 

Предлагается эвристический алгоритм CTDA (Computing Tree Decomposition by Acyclicity), основанный на пополнении гиперграфа до М-ациклического. Свойство М-ацикличности (называемое также a-ацикличностью) широко эксплуатируется в различных приложениях теории гиперграфов, так как обеспечивает полиномиальную вычислимость ряда важных характеристик и графических конструкций, связанных с гиперграфами. Употребление данного свойства в алгоритме CTDA дает возможность создавать за полиномиальное время дерево декомпозиции гиперграфа с разной степенью приближения к оптимальному дереву декомпозиции. 

Подробное описание дается в статье «Алгоритм построения дерева декомпозиции гиперграфа на основе ацикличности», автор Быкова В.В. (Институт математики Сибирского федерального университета, г. Красноярск).