close

Вход

Забыли?

вход по аккаунту

?

Алгоритм построения дерева декомпозиции гиперграфа на основе ацикличности.

код для вставкиСкачать
Программные продукты и системы
5. Мокрозуб В.Г., Мариковская М.П., Красильников В.Е.
Интеллектуальная автоматизированная система проектирова-
№ 1, 2011 г.
ния химического оборудования // Системы управления и информационные технологии. 2007. № 4.2(30). С. 264–267.
УДК 519.179.1+004.021
АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА
ДЕКОМПОЗИЦИИ ГИПЕРГРАФА НА ОСНОВЕ АЦИКЛИЧНОСТИ
В.В. Быкова, к.т.н.
(Институт математики Сибирского федерального университета, г. Красноярск,
bykvalen@mail.ru)
Задача нахождения оптимального дерева декомпозиции гиперграфа возникает во многих приложениях. Между
тем она является NP-трудной. В данной работе предлагается новый полиномиальный по времени эвристический алгоритм, основанный на пополнении гиперграфа до ациклического. Алгоритм использует жадную стратегию, направленную на минимизацию ширины конструируемого дерева декомпозиции.
Ключевые слова: алгоритмы на графах, гиперграфы, дерево декомпозиции, древовидная ширина, ацикличность.
Структура многих NP-трудных задач комбинаторной оптимизации может быть описана гиперграфом. Такие задачи возникают в системах
принятия решений, БД, при анализе информационных и коммуникационных сетей, конструкторском проектировании радиоэлектронной и вычислительной аппаратуры, лингвистической трансляции, при формировании трафика компьютерных
сетей и т.д. Дерево декомпозиции гиперграфа дает
возможность организовать процесс поиска оптимального решения по принципу «разделяй и властвуй». Если древовидная ширина гиперграфа ограничена сверху некоторой константой, то многие
NP-трудные задачи комбинаторной оптимизации
могут быть решены за полиномиальное время [1].
Древовидная ширина – это числовая характеристика гиперграфа, определяемая через оптимальное дерево декомпозиции. К сожалению, сама
задача нахождения оптимального дерева декомпозиции также NP-трудная, поэтому в алгоритмической практике востребованы эвристики,
позволяющие получать хорошие деревья декомпозиции за разумное время.
В данной работе предлагается эвристический
алгоритм CTDA (Computing Tree Decomposition by
Acyclicity), основанный на пополнении гиперграфа
до М-ациклического. Свойство М-ацикличности
(называемое также -ацикличностью) широко
эксплуатируется в различных приложениях теории гиперграфов, так как обеспечивает полиномиальную вычислимость ряда важных характеристик
и графических конструкций, связанных с гиперграфами [2–4]. Употребление данного свойства в
алгоритме CTDA дает возможность создавать за
полиномиальное время дерево декомпозиции гиперграфа с разной степенью приближения к оптимальному дереву декомпозиции.
Гиперграф и дерево декомпозиции. Используем терминологию и обозначения, принятые в
64
[3–5]. Пусть задан гиперграф H=(X, U) с конечным множеством вершин X и ребер U. В общем
случае U – конечное семейство произвольных
подмножеств множества X. Гиперграф H=(, )
считается пустым. Пусть U(x) – множество ребер,
инцидентных в H вершине xX; X(u) – множество
всех вершин, инцидентных в H ребру uU. Число
U(x) определяет степень вершины x, а X(u) 
степень ребра u. Элемент гиперграфа степени 0
считают голым, степени 1 – висячим. Два ребра
u, vU кратны в H, если X(u)=X(v). Ребро u вложено в ребро v, когда X(u)X(v). Гиперграф называется минимальным, если он не содержит голых
элементов, вложенных и кратных ребер. Ранг гиперграфа H=(X, U) определяется как максимальная степень его ребра: r(H)=maxuUX(u).
Существуют различные способы задания гиперграфа. Так, если X={x1, x2, ..., xn}, n1, и U={u1,
u2, ..., um}, m1, то (n, m)-гиперграф H=(X, U) однозначно описывается матрицей инциденций
A(H)={aij}, где aij=1 при xiX(uj) и aij=0 при
xiX(uj), i=1, 2, ..., n, j=1, 2, ..., m. Универсальным
способом задания гиперграфа также является кенигово представление. Кенигово представление
гиперграфа H=(X, U) – это обыкновенный двудольный граф K(H), отражающий отношение инцидентности различных элементов гиперграфа, с
множеством вершин XU и долями X, U. Многие
структурные свойства гиперграфа определяются
через одноименные свойства кенигова представления. Так, гиперграф H считается связным, если
граф K(H) связный. Далее в качестве исходных
гиперграфов будем рассматривать, не нарушая
общности, только непустые, минимальные и связные гиперграфы.
Частично структурные особенности гиперграфа H=(X, U) описывают ассоциированные с ним
обыкновенные графы L(2)(H) и L(H). Граф L(2)(H)
Программные продукты и системы
представляет отношение смежности вершин, а
граф L(H)  отношение смежности ребер гиперграфа H. Граф L(H)=(U, E) полагают помеченным,
если всякому его ребру {ui, uj}E поставлена в соответствие метка fij=X(ui)X(uj), 1i<jm.
Число fij рассматривают как вес ребра {ui, uj}.
Граф L(H), для каждого ребра {ui, uj} которого
указан вес fij=X(ui)X(uj), именуют взвешенным
реберным графом гиперграфа H. Свойства графов
L(2)(H) и L(H) определяют ряд важных свойств
гиперграфа H. Так, гиперграф H комплектный,
если каждой максимальной клике графа L(2)(H)
отвечает некоторое ребро этого гиперграфа.
С гиперграфом связана еще одна графовая
структура, именуемая деревом декомпозиции. Под
деревом декомпозиции гиперграфа H=(X, U) понимают пару ({Xi, iI}, T=(I, E)), где {Xi, iI} –
семейство мешков  непустых подмножеств множества X, T=(I, E) – дерево, удовлетворяющее условиям [1]:
 iIXi=X, то есть множество мешков покрывает множество вершин гиперграфа;
 если uU, то всегда существует iI, такое,
что X(u)Xi, то есть для всякого ребра гиперграфа
всегда существует хотя бы один мешок, содержащий все вершины этого ребра;
 для любой вершины гиперграфа xX множество {iI | xXi} индуцирует связное поддерево
дерева T=(I, E).
Ширина дерева декомпозиции ({Xi, iI}, T=
=(I, E)) – наибольшая вместимость его мешка,
уменьшенная на единицу, то есть maxiI{Xi1}.
Древовидная ширина гиперграфа H (обозначается
tw(H)) определяется как наименьшая ширина всех
возможных деревьев декомпозиции, которые существуют для H. Дерево декомпозиции, ширина
которого равна tw(H), принято называть оптимальным деревом декомпозиции. Древовидная ширина есть числовой параметр, характеризующий
меру древовидности гиперграфа: чем меньше
tw(H), тем ближе H к обычному дереву. Если H –
несвязный гиперграф, то tw(H)=0. Следует отметить, что для каждого (n,m)-гиперграфа всегда
существует хотя бы одно дерево декомпозиции.
Например, таковым является тривиальное дерево
декомпозиции, состоящее из одного узла с мешком
X и имеющее ширину n–1. Ясно, что тривиальное
дерево декомпозиции в общем случае не является
оптимальным. Очевидны оценки: r(H)–1tw(H),
0tw(H)n–1.
Характеризация М-ациклических гиперграфов. Пусть в (n,m)-гиперграфе H=(X, U) задана последовательность его ребер P=(u1, u2, ..., uk,
uk+1), 3km. Если fi=X(ui)X(ui+1), i=1, 2, ..., k,
эту последовательность можно записать так:
P=(u1, f1, u2, f2, ..., uk, fk, uk+1).
В гиперграфе H последовательность P задает
М-цикл длины k, если
№ 1, 2011 г.
1) u1, u2, ..., uk+1 – различные ребра гиперграфа
H (различные как элементы семейства U);
2) каждые два соседних ребра в P смежные, то
есть fi, i=1, 2, ..., k;
3) fifi+1, i=1, 2, ..., k;
4) u1=uk+1 и f1fk.
М-цикл P=(u1, f1, u2, f2, ..., uk, fk, uk+1) считается
бесхордовым, когда для любой его тройки множеств fa, fb, fc, 1a<b<ck, в H нет такого ребра u,
что fafbfcX(u). Если хотя бы для одной тройки
fa, fb, fc, 1a<b<ck, такое ребро u существует в H
(u играет роль хорды и необязательно принадлежит P), то P – хордовый М-цикл гиперграфа H.
Гиперграф, не содержащий бесхордовых М-циклов, называется M-ациклическим. Наличие хотя
бы одного бесхордового цикла приводит к M-цикличности гиперграфа. Отметим, что существуют
различные трактовки ацикличности и цикличности гиперграфа. Приведенное выше определение
М-ацикличности возникло в теории реляционных
БД [2] и получило уточнение в работах [3, 4].
Теорема 1. Для (n, m)-гиперграфа H=(X, U)
следующие высказывания эквивалентны [2–4]:
1) H является М-ациклическим гиперграфом;
2) H комплектный, и его граф L(2)(H) триангулированный;
3) для H существует дерево соединений;
4) дерево соединений гиперграфа H – остовное дерево наибольшего веса взвешенного реберного графа L(H);
5) дерево клик графа L(2)(H) изоморфно дереву
соединений гиперграфа H;
6) алгоритм Грэхема завершается успешно;
7) H не содержит блоков при условии, что H
минимальный и U=m>1.
Данная теорема определяет свойства М-ациклического гиперграфа, используемые далее в алгоритме CTDA. Дадим краткие пояснения.
Пусть L(H)=(U, E) – взвешенный реберный
граф гиперграфа H=(X, U) и Tjoin(H) – остовное
дерево для L(H). Дерево Tjoin(H) называется деревом соединений гиперграфа H, если для всякой пары ui, ujU и любого xX(ui)X(uj) в Tjoin(H)
существует x-путь P=(ui, ui+1, ..., uj), который следует из ui в uj и x лежит вдоль этого пути: xX(ui),
xX(ui+1), …, xX(uj). Нетрудно убедиться, что
для М-ациклического (n, m)-гиперграфа дерево
соединений является оптимальным деревом декомпозиции, каждый мешок которого содержит
вершины в точности одного ребра гиперграфа.
Также I =m, tw(H)=r(H)1. Из эквивалентности
высказываний теоремы 1, пп. 1 и 4, вытекает полиномиальный по времени способ нахождения оптимального дерева декомпозиции для М-ациклического графа: построить взвешенный реберный
граф L(H) и найти для него остовное дерево наибольшего веса. Распознать М-ацикличность можно с помощью алгоритма Грэхема [2].
65
Программные продукты и системы
Алгоритм Грэхема является элиминационной
схемой последовательного применения к гиперграфу следующих операций: СУВ – слабое удаление висячих вершин (без удаления инцидентных
им ребер); СУР – слабое удаление кратных, вложенных ребер (без удаления инцидентных им
вершин). Обозначим через red(H) гиперграф, полученный в результате применения алгоритма
Грэхема к гиперграфу H. Говорят, что алгоритм
Грэхема для H завершается успешно, если
red(H)=(, ). Алгоритм Грэхема всегда приводит
к одному и тому же гиперграфу red(H) независимо
от порядка и числа удаляемых элементов на каждом шаге. Кроме того, операции СУВ и СУР сохраняют связность гиперграфа. Все это свидетельствует о рекурсивном характере алгоритма Грэхема и наследственности свойства М-ацикличности
относительно операций СУВ и СУР (все гиперграфы, полученные из М-ациклического гиперграфа
путем применения к нему этих операций, также
М-ацикличны). Алгоритм Грэхема прост в реализации и имеет полиномиальную временную сложность. Операция СУР алгоритма Грэхема осуществляет минимизацию текущего гиперграфа.
Многие известные эвристические алгоритмы
построения дерева декомпозиции гиперграфа опираются на свойства триангулированных графов
[1]. Суть их в следующем: вначале для заданного
гиперграфа H находится минимальная триангуляция графа L(2)(H) (минимальное пополнение
L(2)(H) до триангулированного графа), а затем создается дерево клик для минимальной триангуляции. При этом структурные особенности самого
гиперграфа H эксплуатируются лишь частично.
Напомним, что граф называется триангулированным, если всякий его цикл длиной k4 обладает
хордой  ребром, соединяющим две несмежные
вершины данного цикла (сам цикл при этом называется хордовым).
Описание и обоснование алгоритма. Эвристический алгоритм CTDA конструирует дерево
декомпозиции путем минимального пополнения
исходного гиперграфа до М-ациклического. Стратегия алгоритма CTDA: использование в полном
объеме характеризации М-ациклических гиперграфов и информации о структуре исходного гиперграфа H=(X, U). Это достигается разделением
процесса решения задачи на три этапа.
Этап 1. Уменьшение размерности решаемой
задачи путем сокращения числа элементов исходного гиперграфа с помощью алгоритма Грэхема и
выделения блоков гиперграфа.
Этап 2. Устранение в каждом блоке бесхордовых М-циклов путем добавления в H множества
дополнительных ребер Uadd.
Этап 3. Построение для результирующего гиперграфа Hadd=(X, UUadd) дерева соединений,
используя эквивалентность высказываний теоремы 1, пп. 1, 3, 4.
66
№ 1, 2011 г.
Алгоритм CTDA на этапе 2 применяет эвристику «минимальная степень». Поскольку предварительно на этапе 1 размерность задачи снижается, область действия погрешностей, вносимых эвристикой, сокращается. Это позволяет добавлять в
H дополнительные ребра минимально необходимой мощности для устранения бесхордовых
М-циклов и получать в итоге деревья декомпозиции с шириной, близкой к tw(H).
Дадим разъяснения к каждому из трех этапов
алгоритма CTDA. Будем по-прежнему полагать,
что исходный (n, m)-гиперграф H=(X, U) является
непустым, минимальным и связным. Кроме того,
будем исходить из того, что U=m>1 и m=O(n),
1, то есть число ребер гиперграфа полиномиально зависит от числа его вершин. Если H имеет
только одно ребро, решение известно: тривиальное дерево декомпозиции гиперграфа H является
оптимальным и tw(H)=n–1.
Пусть YX и Y=X(ui)X(uj)=fij для некоторой пары ребер ui, ujU гиперграфа H=(X, U),
1i<jm. Множество Y считается множеством
сочленения связного гиперграфа H=(X, U), если
гиперграф H(X \ Y) несвязен. Здесь H(X \ Y) 
часть гиперграфа H, порожденная множеством
вершин X \ Y, то есть полученная из H слабым
удалением вершин, входящих в Y. Блоком гиперграфа H называется всякая его часть H(Z), порожденная множеством ZX и не имеющая множества сочленения. Блок тривиальный, если у него
лишь одно ребро.
Вначале Uadd=. Если исходный гиперграф
H=(X, U) является М-ациклическим, для него
алгоритм Грэхема завершается успешно. Это означает, что в H нет нетривиальных блоков и бесхордовых М-циклов. Необходимости в выполнении
этапа 2 нет – можно сразу перейти на этап 3 без
изменения Uadd. Если оказалось, что гиперграф
H=(X, U) М-циклический, то B=red(H) – непустой, минимальный и М-циклический гиперграф.
Согласно высказыванию теоремы 1, п. 7, B=red(H)
содержит хотя бы один нетривиальный блок. Найти все блоки гиперграфа B можно за время O(m2),
используя для этого метки fij=X(ui)X(uj) помеченного графа L(B). В выделенных блоках возможно появление висячих вершин, а после их удаления – кратных и вложенных ребер. Также некоторые блоки могут быть тривиальными. Значит, к
каждому блоку гиперграфа B=red(H) целесообразно вновь применить алгоритм Грэхема. Учитывая, что временная сложность алгоритма Грэхема
для (n,m)-гиперграфа составляет O(nm) и
m=O(n), 1, этап 1 алгоритма CTDA можно реализовать за время O(n2).
Пусть B1, B2, …, Bs – блоки, выделенные из
гиперграфа B=red(H) и подвергнутые обработке
алгоритмом Грэхема так, что каждый из них есть
непустой, минимальный, связный гиперграф. По-
Программные продукты и системы
скольку гиперграф B=red(H) М-циклический, всякий блок Bi, i=1, 2, …, s, имеет хотя бы один бесхордовый М-цикл. Связь между бесхордовыми
М-циклами гиперграфа и структурными свойствами графа L(2) устанавливает теорема 2, сформулированная применительно к Bi, i=1, 2, …, s.
Теорема 2. Для любого гиперграфа Bi верны
следующие высказывания:
1) всякий бесхордовый М-цикл длины k=3 гиперграфа Bi порождает в L(2)(Bi) один или несколько соответствующих простых хордовых
циклов длины k3;
2) всякий бесхордовый М-цикл длины k>3 гиперграфа Bi порождает в L(2)(Bi) соответствующий простой цикл, не содержащий хорды и
имеющий длину l>3 (k и l необязательно равны);
3) каждый простой цикл графа L(2)(Bi) длины
k>3, не имеющий хорды, продуцирует в Bi соответствующий бесхордовый М-цикл длины k>3;
4) гиперграф Bi некомплектен тогда и только
тогда, когда содержит хотя бы один бесхордовый
М-цикл длины k=3.
Некоторые из утверждений теоремы 2 доказаны в [3], другие очевидны. Из построения Bi, i=1,
2, …, s, и теоремы 2 следует, что каждый блок Bi
содержит не менее трех вершин и не менее трех
ребер. В силу теорем 1, 2 и того, что Bi  непустой, минимальный, связный и М-циклический гиперграф, возможна одна из трех ситуаций.
Ситуация I. Гиперграф Bi некомплектен, а его
граф L(2)(Bi) триангулированный.
В этом случае все бесхордовые М-циклы гиперграфа Bi имеют длину k=3.
Ситуация II. Гиперграф Bi комплектный, но
граф L(2)(Bi) не является триангулированным.
В данном случае гиперграф Bi содержит бесхордовые М-циклы только длины k>3.
Ситуация III. Гиперграф Bi некомплектен, и
L(2)(Bi) не является триангулированным графом.
В этой ситуации гиперграф Bi содержит хотя
бы один бесхордовый М-цикл длины k=3 и не менее одного бесхордового М-цикла длины k>3.
Ситуация I самая простая. Поскольку граф
L(2)(Bi) триангулированный, он содержит не более
X=n максимальных клик и все они могут быть
найдены за время O(n2). Если для какой-либо максимальной клики YX графа L(2)(Bi) в гиперграфе
Bi нет такого ребра u, что YX(u), множество Y
необходимо добавить в Uadd в качестве дополнительного ребра. Подобные ребра устраняют в Bi
бесхордовые М-циклы длины k=3, точнее, они
становятся хордами для этих циклов. Тем самым
гиперграф Bi превращается в комплектный, а значит, и в М-ациклический гиперграф. Нетрудно
убедиться, что хорды для Bi являются также хордами для соответствующих бесхордовых М-циклов исходного гиперграфа H.
Ситуацию I можно легко распознать с помощью свойств триангулированных графов: любой
№ 1, 2011 г.
триангулированный граф имеет симплициальную
вершину; свойство триангулированности не утрачивается при удалении из графа отдельной вершины. Вершина графа называется симплициальной, если ее окрестность – клика. Таким образом,
если последовательный поиск в L(2)(Bi) симплициальных вершин и их удаление из L(2)(Bi) приводят
к пустому графу, то L(2)(Bi) – триангулированный
граф. Так как граф L(2)(Bi) содержит не более n
вершин, распознать его триангулированность
можно за время O(n2).
Ситуации II и III мало чем отличаются друг от
друга, так как требуют прежде всего триангуляции
графа L(2)(Bi) – приведения его к триангулированному графу. Процесс триангуляции графа L(2)(Bi) –
это насыщение графа новыми ребрами (хордами),
что может привести к появлению новых клик. Даже если гиперграф Bi ранее был комплектным, после триангуляции графа L(2)(Bi) он может утратить
это свойство. Чрезвычайно важно выполнять триангуляцию графа L(2)(Bi) наилучшим образом.
Пусть L(2)(Bi)=(V, W), VX, и Gi=(V, W
Wadd)  триангулированный граф, полученный
насыщением графа L(2)(Bi) множеством хорд Wadd.
Известно, что задача нахождения наименьшей
триангуляции произвольного графа (наименьшего
пополнения графа до триангулированного) является NP-трудной. Между тем триангуляцию хорошего качества можно всегда отыскать за время
O(n3). Для этого достаточно воспользоваться эвристикой «минимальная степень». Суть ее в следующем: в графе L(2)(Bi) выбирается вершина
наименьшей степени, ее окрестность дополняется
до клики; затем данная вершина удаляется из
L(2)(Bi). Указанные действия повторяются до тех
пор, пока L(2)(Bi) не выродится в пустой граф. Эвристика «минимальная степень» в большинстве
случаев дает триангуляцию, близкую к наименьшей триангуляции. Когда триангуляция Gi=(V,
WWadd) для L(2)(Bi) построена, ситуации II и III
вырождаются в ситуацию I. Поскольку число блоков для гиперграфа B=red(H) не превышает
U=m>1, все действия этапа 2 алгоритма CTDA
можно реализовать за время O(n3m) или при
m=O(n), 1, за время O(n+3).
Этап 3 алгоритма CTDA включает в себя следующие действия: создание взвешенного реберного графа L(Hadd), построение для L(Hadd) остовного дерева наибольшего веса. Построенное дерево –
дерево декомпозиции исходного гиперграфа
H=(X, U). Все эти действия можно выполнить за
время O(m2) или при m=O(n), 1, за время
O(n2). В целом алгоритм CTDA позволяет конструировать дерево декомпозиции гиперграфа
H=(X, U) за время O(n2). Это дерево может содержать узлы, мешки которых вложены. Если
XiXj, то к ребру {i, j} в T=(I, E) можно применить операцию сжатия. Подобные действия сокращают число узлов построенного дерева де67
Программные продукты и системы
№ 1, 2011 г.
Слабое удаление этой вершины приводит к блокам B1 и B2.
 Блок B1  некомплектный гиперграф, для
которого граф L(2)(B1) нетриангулированный. После добавления в L(2)(B1) ребра {x5, x8} получаем
минимальную триангуляцию графа L(2)(B1), содержащую две максимальные клики – {x5, x6, x7,
x8} и {x5, x7, x8, x9}. В H нет ребер с таким составом вершин. Поэтому к Uadd добавляем ребра u8 и
u9, где X(u8)={x5, x6, x7, x8} и X(u9)={x5, x7, x8, x9}.
Блок B2  некомплектный гиперграф, но граф
L(2)(B2) триангулированный. Граф L(2)(B2) имеет
одну максимальную клику {x14, x15, x16}. Для этой
клики в H нет подходящего ребра. Добавляем в
Uadd ребро u10, где X(u10)={x14, x15, x16}.
 Результирующий гиперграф Hadd=(X, U
Uadd) является М-ациклическим. Его помеченный реберный граф L(Hadd) изображен на рисунке
2d. Остовное дерево наибольшего веса для L(Hadd)
(оно выделено на рисунке 2d жирными линиями)
определяет дерево декомпозиции гиперграфа
H=(X, U) ширины 5. Построенное дерево декомпозиции имеет узлы с вложенными мешками, поэтому возможно сокращение числа узлов этого
дерева без изменения его ширины.
Заметим, что гиперграф B=red(H) имеет 9
вершин, что больше r(H). Однако блоки B1 и B2
состоят из 5 и 3 вершин соответственно. Это уже
меньше r(H). После выделения блоков и без дальнейшего их анализа можно сразу образовать два
дополнительных ребра – u8, u9, где
X(u8)={x5, x6, x7, x8, x9} и X(u9)={x14,
u1
x15, x16}. Это приведет к дереву деx3
x2
композиции с меньшим числом узx1x2x3x4x5x6
L(2)(H)
L(H)
лов, чем на рисунке 2d, и той же шиx6
x5
x1
x4
рины 5. Можно убедиться, что для
x7
заданного (16, 7)-гиперграфа H не
u2
u
3
x6x7x8
x5x7x9
x5
x6
существует дерева декомпозиции с
u4
шириной меньше 5. Таким образом,
x8
x7
x9
алгоритм CTDA в данном конкретx9
u7 x x
x15 x8
14 16
x8x9x10x11x12x13
ном случае конструирует оптимальные деревья декомпозиции.
x14
x16
x16
x13
x10
В заключение необходимо отмеx13
x15
тить,
что представленный в работе
u6
u
x15x16
x13x14x15 5
x11
x14
x12
эвристический алгоритм CTDA основан на характеризациях М-ацикРис. 1.
лических гиперграфов. В нем применяется эвристика «минимальная
Процесс построения для H дерева декомпозистепень». Оптимальность алгоритма CTDA может
ции изображен на рисунке 2 и включает в себя
быть потеряна только за счет этой эвристики. Осследующие действия.
новное преимущество алгоритма CTDA перед дру Вначале Uadd=. Ребра u1, u4U содержат
гими подобными алгоритмами  использование в
висячие вершины x1, x2, x3, x4, x10, x11, x12. Их слаполном объеме информации о структуре исходнобое удаление дает гиперграф B=red(H). Единстго гиперграфа. Алгоритм CTDA реализован в виде
венным множеством сочленения гиперграфа
программы на языке C++. Вычислительные эксB=red(H) является {x13}.
перименты показали, что алгоритм создает дерево
декомпозиции, которое оптимально или близко к
 Множество сочленения {x13} порождает два
оптимальному, когда в исходном гиперграфе поблока, в каждом из которых вершина x13 висячая.
композиции ({Xi, iI}, T=(I, E)), не изменяя его
ширины. Важно, что данный алгоритм допускает
построение требуемого дерева с разной степенью
приближения к оптимальному дереву декомпозиции.
1. Если H=(X, U) – М-ациклический гиперграф, созданное дерево декомпозиции является
оптимальным и ширина этого дерева определяет
tw(H).
2. На этапе 1 в Uadd можно сразу внести ребро,
содержащее все вершины гиперграфа B=red(H).
После этого гиперграф Hadd=(X, UUadd) станет
М-ациклическим. Дерево соединений для Hadd 
дерево декомпозиции исходного гиперграфа. Оно
приемлемо, когда число вершин гиперграфа
B=red(H) меньше r(H). Однако, если H=red(H),
то, действуя подобным образом, получим тривиальное дерево декомпозиции.
3. На этапе 1 можно сформировать s более
мелких дополнительных ребер, включив в каждое
такое ребро все вершины из Bi, i=1, 2, …, s. Тем
самым получим дерево декомпозиции меньшей
ширины, чем в предыдущем случае.
4. Выполнение этапа 2 исчерпывает все возможности алгоритма CTDA по построению дерева
декомпозиции гиперграфа.
Иллюстрация работы алгоритма CTDA.
Рассмотрим (16, 7)-гиперграф H=(X, U), который
на рисунке 1 представлен помеченным реберным
графом L(H) и графом L(2)(H). Ранг гиперграфа H
равен 6.
68
Программные продукты и системы
L(B)
№ 1, 2011 г.
x5x6
x6
x7
x6x7x8
x5x7x9
x8
x15
x15x16
x14x16
x13
x16
x13x14x15
x15x16
x9
x8x9
x14
x15
x14x15
a)
L(2)(B1)
L(B2)
b)
x6
x5
x7
x8
x6
u2
x6x7x8
x9
u8
x15
L(2)(B2)
x5x7x9
x8
x8x9x13
x14
x16
x5
x7
x6x7x8
x9
x14x16
x5x6
L(B1) x6
x5
x8
u7
x16
x14x16
x14
c)
x16
x15x16
u6
u1
x5
u3
x5x6
x7
x5
x5x7x9
x5x7x9
x6x7x8
x
x
x
5
7
8
x8
x8
u9
xx85x7xx88x9
x8 xx58x6x7x8
x8
x9
x8 x8x89
x8 x8 x8
x8
x8
x8xx9x10x11x12x13 x8
8
x8
x8 u4
x8x14
x13 x8
x15
x8
x8
u5
x13x14x15
x14x16
x14x15
x15x16
Рис. 2
сле предобработки алгоритмом Грэхема все ребра
имеют приблизительно одну и ту же степень.
Возможно включение в алгоритм CTDA новых эвристик, расширяющих область эффективного
применения данного алгоритма.
Литература
1. Bodlaender H.L. Discovering treewidth. In Proceedings of
the 31st Conference SOFSEM 2005, Springer-Verlag, Lecture
x1x2x3x4x5x6
x14x15x16
u10
d)
Notes in Computer Science 3381, 2005, pp. 1–16.
2. Мейер Д. Теория реляционных баз данных. М.: Мир,
1987.
3. Быкова В.В. Полиномиальные достаточные условия бихроматичности гиперграфа // Вест. КрасГУ: сер. Физ.-мат. науки. 2006. № 7. С. 98–106.
4. Быкова В.В. М-ациклические и древовидные гиперграфы // Изв. Томского политех. ун-та. 2010. Т. 317. № 2. С. 25–30.
5. Зыков А.А. Гиперграфы // Успехи математических наук. 1974. Т. 29. Вып. 6. С. 89–154.
УДК 004.9
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
НАВЫКОВОЙ СИСТЕМЫ ПРИНЯТИЯ РЕШЕНИЙ
(Работа выполнена при поддержке РФФИ, проект № 09-07-99013-р_офи)
В.Н. Мещеряков, д.т.н.; В.В. Кавыгин, к.т.н.; С.В. Полозов, к.т.н.; М.С. Бессонов
(Липецкий государственный технический университет, kabugun@mail.ru)
В статье описан навыко-вычислительный метод принятия решений в ситуациях, характеризуемых трудноформализуемой информацией большой размерности. В результате автоматического обучения устанавливается разбросная
зависимость между исходными факторами и откликами системы. В качестве примера представлена навыковая система диагностики «Гепатиты 1.0».
Ключевые слова: множество, алгоритм, итерация, обучение, обучающая выборка, навыки, отклик, принятие
решений.
Повышение эффективности работы интеллектуальных, диагностических, экспертных, инфор-
мационно-измерительных систем основано на разработке и внедрении прогрессивных методов при69
Документ
Категория
Без категории
Просмотров
4
Размер файла
1 574 Кб
Теги
ацикличности, построение, алгоритм, гиперграфов, декомпозиция, основы, дерево
1/--страниц
Пожаловаться на содержимое документа