Деревоподібна декомпозиція
Деревоподібна декомпозиція або кластеризація (Tree-clustering) (Dechter&Pearl[14]) перетворює довільне -арне завдання УО в ациклічну форму у поданні у вигляді двоїстого графа шляхом формування кластерів із змінних, граф взаємозв'язків яких має структуру дерева. -арна задача УО називається ациклічною, якщо її первинний граф обмежень має наступні властивості:
- хордальність: кожен цикл, що містить не менше 4 вершин, містить хорду (ребро, що з'єднує 2 непослідовні вершини циклу).
- конформність: кожна з максимальних клік графа відповідає одному обмеженню задачі УО.
Алгоритм тріангуляції (Tarjan&Yannakakis[15]) може бути використаний для досягнення зазначених властивостей, використовуючи два кроки: a) Знайти впорядкування з максимальним ступенем (maximum cardinality) та б) рекурсивно додати ребра між вершинами, що з'єднують вершини, з великим порядком відповідно до зазначеного упорядкування. На рисунках 10.12 a і b (з (Dechter&Pearl[16])) відповідно показано первинний граф обмежень задачі УО до і після процесу тріангуляції.
Максимальними кліками цього графа є кластери, які становлять обмеження перетвореної задачі УО (див. рис. 10.10 а).
Мал. 10.9. Побудова хордального первинного графа.
Для побудови дерева із цього уявлення досить видалити зайві ребра із графа, тобто. ті ребра, видалення яких впливає безліч рішень.
У двоїстому графі дуга надмірна, якщо безліч змінних, яким вона позначена, є загальним всім дуг на окремому шляху між кінцевими вершинами дуги.
Мал. 10.10. Побудова дерева здвоїстого графа.
На рис. 10.10 b) показаний один спосіб побудови дерева для завдання УО.
Складність цієї процедури , де розмір найбільшої максимальної кліки.
Поняття ширини дерева запровадили теоретично графів Робертсон і Сеймур (Robertson&Seymour, 1986)[17].(Dechter&Pearl, 1987, 1989) застосовували те саме поняття (назване нимиіндукованою шириною) до завдань УО і розробили підхід, що використовуєдеревоподібну декомпозицію(tree decomposition) (див. тему 8) графа обмежень та створення безлічі пов'язаних підзадач. Кожне підзавдання вирішується незалежно, та був підсумкові рішення комбінуються. Цей алгоритм працює успішно, якщо підзавдання не надто великі. Будь-яка деревоподібна декомпозиція повинна задовольняти три наведені нижче вимоги.
1) Кожна змінна з початкової задачі з'являється щонайменше на одній із підзадач.
2) Якщо дві змінні первісної задачі пов'язані обмеженням, то повинні з'явитися разом (поряд із цим обмеженням) щонайменше в одній із підзавдань.
3) Якщо якась змінна з'являється у двох підзавданнях у дереві, то повинна з'являтися в кожній підзадачі вздовж шляху, що з'єднує ці підзавдання.
Перші дві умови гарантують, що в декомпозиції будуть представлені всі змінні та обмеження. Третя умова просто відображає те обмеження, що будь-яка конкретна змінна повинна мати те саме значення в кожній підзадачі, в якій з'являється; дотримання цього обмеження гарантують зв'язки, що з'єднують підзавдання у дереві.
Кожне підзавдання вирішується незалежно; якщо якась із них не має рішення, то все завдання також не має рішення. Після вирішення всіх підзадач складається рішення вихідного завдання шляхом вирішеннязавдання з обмеженнями, що пов'язують підзавдання; для цього використається ефективний алгоритм для дерев. Обмеження, що пов'язують підзавдання, вказують на те, що рішення підзавдання мають бути узгодженими за їх загальним змінним. Будь-який конкретний граф обмежень припускає велику кількість деревоподібних декомпозицій; при виборі декомпозиції потрібно прагнути до того, щоб підзавдання були якнайменше.Ширина деревадеревоподібної декомпозиції графа на одиницю менше розміру найбільшої підзадачі; ширина дерева самого графа визначається як мінімальна ширина дерева серед усіх деревоподібних декомпозицій. Якщо граф має ширину дерева і дана відповідна деревоподібна декомпозиція, то відповідне завдання може бути вирішене за час. Це означає, щозавдання УО з графами обмежень, що характеризуються кінцевою шириною дерева, можуть бути вирішені за поліноміальний час. На жаль, завдання пошуку декомпозиції з мінімальною шириною дерева є NP-важкою, але є евристичні методи, які добре працюють на практиці.