Metoda dekompozycji (spełnienie ograniczeń)

W przypadku spełniania ograniczeń metoda dekompozycji przekłada problem spełniania ograniczeń na inny problem spełniania ograniczeń, który jest binarny i acykliczny . Metody dekompozycji polegają na grupowaniu zmiennych w zestawy i rozwiązywaniu podproblemu dla każdego zestawu. Te tłumaczenia są wykonywane, ponieważ rozwiązywanie binarnych problemów acyklicznych jest problemem łatwym do rozwiązania .

Każde ograniczenie strukturalne określało miarę złożoności rozwiązania problemu po konwersji; miara ta nazywana jest szerokością . Ustalenie maksymalnej dozwolonej szerokości jest sposobem na zidentyfikowanie podklasy problemów spełniania ograniczeń. Rozwiązywanie problemów w tej klasie jest wielomianowe dla większości dekompozycji; jeśli dotyczy to rozkładu, klasa problemów o stałej szerokości tworzy podklasę problemów spełniania ograniczeń.

Przegląd

Metody dekompozycji przekładają problem na nowy, łatwiejszy do rozwiązania. Nowy problem zawiera tylko ograniczenia binarne ; ich zakresy tworzą skierowany graf acykliczny . Zmienne nowego problemu reprezentują każdy zestaw zmiennych pierwotnego problemu. Zestawy te niekoniecznie są rozłączne, ale obejmują zbiór oryginalnych zmiennych. Tłumaczenie znajduje wszystkie rozwiązania cząstkowe względem każdego zestawu zmiennych. Problem wynikający z translacji reprezentuje interakcje między tymi lokalnymi rozwiązaniami.

Z definicji metoda dekompozycji tworzy binarny problem acykliczny; takie problemy można rozwiązać w czasie wielomianu w swojej wielkości. W rezultacie pierwotny problem można rozwiązać, najpierw go tłumacząc, a następnie rozwiązując wynikowy problem; jednak ten algorytm działa w czasie wielomianowym tylko wtedy, gdy rozkład nie zwiększa rozmiaru superwielomianowo. Szerokość metody dekompozycji jest miarą rozmiaru problemu, który stworzyła . Pierwotnie szerokość była definiowana jako maksymalna liczność zbiorów oryginalnych zmiennych; jedna metoda, dekompozycja hiperdrzewa, wykorzystuje inną miarę. Tak czy inaczej, szerokość rozkładu jest zdefiniowana w taki sposób, że rozkłady o rozmiarze ograniczonym stałą nie powodują zbyt dużych problemów. Instancje mające rozkład o stałej szerokości można przetłumaczyć przez dekompozycję na instancje o rozmiarze ograniczonym wielomianem w rozmiarze oryginalnej instancji.

Szerokość problemu to szerokość jego rozkładu na minimalną szerokość. Podczas gdy dekompozycje o stałej szerokości mogą być wykorzystane do skutecznego rozwiązania problemu, ograniczenie szerokości instancji musi koniecznie powodować możliwe do usunięcia ograniczenie strukturalne. Rzeczywiście, problem o stałej szerokości ma rozkład stałej szerokości, ale znalezienie go może nie być wielomianem. Aby problem stałej szerokości został skutecznie rozwiązany przez dekompozycję, należy skutecznie znaleźć jedną z jego dekompozycji o małej szerokości. Z tego powodu metody dekompozycji i powiązana z nimi szerokość są definiowane w taki sposób, że nie tylko rozwiązują problem, biorąc pod uwagę jego rozkład o stałej szerokości w czasie wielomianowym, ale także znalezienie rozkładu o stałej szerokości problemu o stałej szerokości jest wielomianem- czas.

Metody rozkładu

Metody dekompozycji tworzą problem, który można łatwo rozwiązać z dowolnego. Każda zmienna tego nowego problemu jest powiązana z zestawem oryginalnych zmiennych; jego dziedzina zawiera krotki wartości dla zmiennych w powiązanym zbiorze; w szczególności są to krotki, które spełniają zestaw ograniczeń dotyczących tych zmiennych. Ograniczenia nowego problemu powodują, że wartości dwóch nowych zmiennych mają jako wartości dwie krotki, które są zgodne co do wspólnych oryginalnych zmiennych. Trzy dalsze warunki zapewniają, że nowy problem jest równoważny ze starym i może być skutecznie rozwiązany.

Aby nowy problem mógł być skutecznie rozwiązany, graf pierwotny nowego problemu musi być acykliczny. Innymi słowy, patrząc na zmienne jako wierzchołki, a ograniczenia (binarne) jako krawędzie, wynikowy graf musi być drzewem lub lasem .

Aby nowy problem był równoważny ze starym, każde pierwotne ograniczenie jest wymuszane w ramach definicji dziedziny co najmniej jednej nowej zmiennej. Wymaga to, aby dla każdego ograniczenia starego problemu istniała zmienna nowego problemu, taka, że powiązany z nią zestaw oryginalnych zmiennych obejmuje zakres ograniczenia, a wszystkie krotki w jego domenie spełniają to ograniczenie.

Kolejnym warunkiem koniecznym do zapewnienia równoważności jest to, aby ograniczenia binarne były wystarczające do wymuszenia, aby wszystkie „kopie” każdej oryginalnej zmiennej przyjmowały tę samą wartość. Ponieważ ta sama oryginalna zmienna może być powiązana z kilkoma nowymi zmiennymi, wszystkie wartości tych nowych zmiennych muszą być zgodne z wartością starej zmiennej. Ograniczenia binarne służą do wymuszenia równości starych zmiennych współdzielonych przez dwie nowe zmienne. Dwie kopie nowej zmiennej są wymuszane jako równe, jeśli istnieje ścieżka ograniczeń binarnych między ich nowymi zmiennymi, a wszystkie nowe zmienne w tej ścieżce zawierają starą zmienną.

	Przykładowy problem spełnienia ograniczeń; ten problem jest binarny, a ograniczenia są reprezentowane przez krawędzie tego grafu.
	Drzewo rozkładu; dla każdej krawędzi oryginalnego wykresu istnieje węzeł, który zawiera oba jego punkty końcowe; wszystkie węzły zawierające zmienną są połączone
	Rozwiązywanie podproblemu. Ten przykład pokazuje rozwiązanie podproblemu złożonego ze wszystkich ograniczeń na zmienne pierwszego zestawu. $z \}}$ , Podobna procedura jest wykonywana dla innych zestawów i ${u, x, z \}}$ $w \}} { u , x , z$ }
\ Displaystyle \ {
	drzewo staje się zmienną. Jego dziedziną jest zbiór rozwiązań problemu cząstkowego, który jest zbiorem krotek. Ograniczenia nowego problemu dopuszczają tylko krotki zawierające równe wartości oryginalnych zmiennych. Na rysunku pokazano równość $tylko$ przez pierwszą krotkę z ${\ Displaystyle (x, y, z)}$ i pierwszą krotkę ${\ Displaystyle (y, w)}$ i drugą krotką ${\ Displaystyle (x, y, z)}$ i drugą krotką ${\ styl wyświetlania (y,w)}$ . Co więcej, druga krotka $)}$ $)$ krotki w swoim lewym potomku ( $, x,$ ). $_$ druga _

Metoda dekompozycji jest zwykle definiowana przez dostarczenie drzewa, którego węzły są zmiennymi nowego problemu; dla każdego węzła zapewniony jest również powiązany zestaw oryginalnych zmiennych i ewentualnie zestaw oryginalnych ograniczeń użytych do zbudowania dziedziny zmiennej w nowym problemie. Z powyższych trzech warunków (struktura drzewa, wymuszanie ograniczeń i równoważność kopii oryginalnych zmiennych) pierwszy jest automatycznie wymuszany przez tę definicję. Warunek wymuszenia ograniczeń jest najczęściej formułowany jako: zakres każdego ograniczenia jest podzbiorem zmiennych jakiegoś węzła; jednak inny warunek może być użyty, gdy węzły są również powiązane z zestawami ograniczeń. Równoważność wszystkich kopii oryginalnych zmiennych jest zwykle formułowana w następujący sposób: podgraf indukowany przez węzły powiązane ze zmienną oryginalną jest spójny.

Metody dekompozycji problemów binarnych

Istnieje wiele metod rozkładu. Większość z nich generuje wykonalną klasę, ograniczając szerokość instancji. Poniżej przedstawiono metody dekompozycji zdefiniowane dla binarnych problemów spełniania ograniczeń. Ponieważ problem można uczynić binarnym, tłumacząc go na problem podwójny lub używając zmiennych ukrytych , metody te można pośrednio wykorzystać do zapewnienia dekompozycji drzewa dla dowolnych problemów spełniania ograniczeń.

Dwupołączone komponenty

W teorii grafów wierzchołek oddzielający jest węzłem grafu, który „łamie” wykres po usunięciu z niego. Formalnie jest to węzeł, którego usunięcie z grafu zwiększa liczbę połączonych z nim składowych. Dwuspójny składnik grafu to maksymalny zbiór jego wierzchołków, którego indukowany podgraf jest spójny i nie ma żadnego rozdzielającego wierzchołka. Z teorii grafów wiadomo, że dwupołączone składowe i rozdzielające wierzchołki grafu tworzą drzewo. Drzewo to można zbudować w następujący sposób: jego węzłami są dwupołączone komponenty i oddzielające wierzchołki grafu; krawędzie łączą tylko podwójnie połączony komponent z wierzchołkiem oddzielającym, aw szczególności dzieje się tak, jeśli wierzchołek jest zawarty w komponencie. Można udowodnić, że ten graf jest w rzeczywistości drzewem.

Jeśli ograniczenia binarnego problemu spełniania ograniczeń są postrzegane jako krawędzie grafu, którego węzłami są zmienne, to drzewo to jest dekompozycją problemu. Szerokość dekompozycji to maksymalna liczba wierzchołków w podwójnie połączonym komponencie.


Pierwotny wykres problemu spełniania ograniczeń (każdy węzeł reprezentuje zmienną, a każda krawędź ograniczenie między dwiema zmiennymi)	Jego dwupołączone komponenty (kolorowe) i wierzchołki oddzielające (czarne, w tym przypadku tylko jeden)	Dekompozycja dwupołączeniowa: węzły drzewa oddzielają wierzchołki i dwupołączone komponenty

Cięcie cykliczne

Metoda dekompozycji cykli dzieli problem na część cykliczną i acykliczną. Chociaż nie pasuje do definicji innych metod dekompozycji, które tworzą drzewo, którego węzły są oznaczone zestawami węzłów, można go łatwo przeformułować w takich kategoriach.

Ta metoda dekompozycji opiera się na założeniu, że po nadaniu wartości niektórym zmiennym to, co pozostaje z problemu po wyeliminowaniu tych zmiennych, może być acykliczne. Formalnie cykliczny zestaw przekrojów grafu to zestaw węzłów, który powoduje, że wykres jest acykliczny, gdy są z niego usuwane. Podobną definicję można podać dla problemu spełnienia ograniczeń, używając jego pierwotnego wykresu. Szerokość rozkładu cyklu to liczba zmiennych w zbiorze fragmentów. Szerokość problemu to minimalna szerokość jego dekompozycji zbioru cykli.


Graficzna reprezentacja problemu spełnienia ograniczeń	Zestaw fragmentów cyklu wykresu (inne istnieją)	Po usunięciu zestawu fragmentów cyklu pozostaje acykliczny wykres (w tym przypadku drzewo, ale ogólnie las)

Wybierając węzeł b jako korzeń, jest to drzewo podobne do drzew utworzonych innymi metodami dekompozycji

Taka dekompozycja nie pasuje do schematu innych dekompozycji, ponieważ wynikiem dekompozycji nie jest drzewo, ale raczej zbiór zmiennych (te z zestawu odcinkowego) i drzewo (utworzone przez zmienne spoza zbioru). Jednak drzewo podobne do tych wygenerowanych innymi metodami dekompozycji można uzyskać z drzewa powstałego w wyniku usunięcia zbioru fragmentów; odbywa się to poprzez wybranie korzenia, dodanie wszystkich zmiennych zbioru fragmentów do wszystkich jego węzłów oraz zmiennych każdego węzła do wszystkich jego dzieci. W rezultacie powstaje drzewo, którego maksymalna liczba zmiennych powiązanych z węzłem jest równa rozmiarowi zestawu cięć plus dwa. Oprócz dodania dwóch jest to szerokość dekompozycji, którą określa się jako liczbę zmiennych w rozpatrywanym zbiorze przekrojowym.

Niestety, określenie minimalnego zestawu do usunięcia jest problemem NP-trudnym .

Rozkład drzewa

Dekompozycja drzewa jest dobrze znaną koncepcją z teorii grafów. Przeformułowany w kategoriach ograniczeń binarnych, dekompozycja drzewa to drzewo, którego węzły są powiązane ze zbiorami zmiennych; zakres każdego ograniczenia jest zawarty w zbiorze zmiennych jakiegoś węzła, a poddrzewo węzłów powiązanych z każdą zmienną jest połączone. Jest to najbardziej ogólna forma dekompozycji ograniczeń binarnych, która jest zgodna ze schematem przedstawionym powyżej, ponieważ warunki nałożone na drzewo to tylko te warunki, które są niezbędne do zagwarantowania równoważności pierwotnego i nowego problemu.

Szerokość takiej dekompozycji to maksymalna liczba zmiennych powiązanych z tym samym węzłem minus jeden. Szerokość drzewa problemu to minimalna szerokość jego dekompozycji drzewa.

Eliminację wiadra można przeformułować jako algorytm działający na dekompozycji konkretnego drzewa. W szczególności, biorąc pod uwagę kolejność zmiennych, każda zmienna jest powiązana z koszykiem zawierającym wszystkie ograniczenia, tak że zmienna jest największa w swoim zakresie. Eliminacja wiadra odpowiada dekompozycji drzewa, która ma węzeł dla każdego wiadra. Węzeł ten jest powiązany ze wszystkimi swoimi ograniczeniami i odpowiada zbiorowi wszystkich zmiennych tych ograniczeń. Rodzic węzła powiązanego z zasobnikiem jest węzłem powiązanym z zasobnikiem $Displaystyle$ $x_ {j}}$ gdzie $displaystyle x_ {j}}$ $jest największym$ $,$ ograniczony z poprzedza w kolejności.

Metody dekompozycji dla dowolnych problemów

Następujące metody mogą być użyte do tłumaczenia dowolnego problemu spełniania ograniczeń, binarnego lub innego. Ponieważ można ich również użyć w problemach binarnych, można ich również użyć w wyniku uczynienia ograniczeń binarnymi, albo przez przełożenie na problem dualny, albo przez użycie zmiennych ukrytych .

Niektóre z tych metod wiążą ograniczenia z węzłami drzewa i definiują szerokość, biorąc pod uwagę liczbę ograniczeń związanych z węzłami. Może to zmniejszyć szerokość niektórych problemów. Na przykład dekompozycja, w której dziesięć zmiennych jest powiązanych z każdym węzłem, ma szerokość dziesięć; jeśli jednak każdy z tych zestawów dziesięciu zmiennych jest zakresem ograniczenia, każdy węzeł może być zamiast tego powiązany z tym ograniczeniem, co daje szerokość jeden.

Dwupołączone komponenty

Dwupowiązana dekompozycja dowolnego problemu spełnienia ograniczeń jest dwupowiązaną dekompozycją jego pierwotnego wykresu. Każde ograniczenie można narzucić na węźle drzewa, ponieważ każde ograniczenie tworzy klikę dla swoich zmiennych na grafie pierwotnym, a klika jest komponentem połączonym podwójnie lub podzbiorem składnika połączonego podwójnie.

Rozkład drzewa

Dekompozycja drzewa dowolnego problemu spełnienia ograniczeń jest dekompozycją drzewa jego grafu pierwotnego. Każde ograniczenie można narzucić na węźle drzewa, ponieważ każde ograniczenie tworzy klikę dla swoich zmiennych na grafie pierwotnym, a dla każdej dekompozycji drzewa zmienne kliki są całkowicie zawarte w zmiennych jakiegoś węzła.

Cykl hipercięć

Jest to ta sama metoda cięcia cyklicznego przy użyciu definicji cięcia hipergrafu: hipergraf hipergrafu to zbiór krawędzi (a nie wierzchołków), który powoduje, że hipergraf jest acykliczny, gdy wszystkie jego wierzchołki zostaną usunięte. Dekompozycję można uzyskać, grupując wszystkie zmienne hipercięcia w jedną. Prowadzi to do drzewa, którego węzłami są zbiory hiperkrawędzi. Szerokość takiej dekompozycji to maksymalny rozmiar zbiorów powiązanych z węzłami, który wynosi jeden, jeśli pierwotny problem jest acykliczny, a rozmiar jego minimalnego zestawu hipercięć w przeciwnym razie. Szerokość problemu to minimalna szerokość jego dekompozycji.

Rozkład zawiasów

Zawias jest podzbiorem węzłów hipergrafu o pewnych właściwościach zdefiniowanych poniżej. Dekompozycja zawiasowa opiera się na zbiorach zmiennych, które są minimalnymi zawiasami hipergrafu, którego węzłami są zmienne problemu spełniania ograniczeń, a hiperkrawędziami są zakresy jego ograniczeń.

Definicja zawiasu jest następująca. Niech $zbiorem$ . $,$ względem to sekwencja krawędzi taka że przecięcie każdej z nich z następną nie jest puste i nie jest zawarte w węzłach ${\ displaystyle H}$ . Zbiór krawędzi $jeśli$ połączony względem, dla każdej pary jego krawędzi istnieje ścieżka względem $węzły$ są pierwszą i ostatnią krawędzią. Połączony komponent w odniesieniu do jest maksymalnym zbiorem połączonych krawędzi w odniesieniu do $displaystyle$ $H}$ .

Przeguby są definiowane dla zredukowanych hipergrafów, które są hipergrafami, w których żaden hipergraf nie jest zawarty w innym. Zestaw co najmniej dwóch krawędzi jest zawiasem, jeśli dla każdego połączonego komponentu $fa$ odniesieniu do $wszystkich$ węzłów w H. {\ displaystyle H}, $również$ { $displaystyle F}$ w wszystkie są zawarte w jednej krawędzi $displaystyle$ $H}$ .

Dekompozycja zawiasów opiera się na zgodności między problemami spełniania ograniczeń a hipergrafami. Hipergraf powiązany z problemem ma zmienne problemu, ponieważ węzły są zakresami ograniczeń jako hiperkrawędzie. Dekompozycja zawiasowa problemu spełniania ograniczeń to drzewo, którego węzłami są pewne minimalne zawiasy hipergrafu związanego z problemem i takie, że spełnione są inne warunki. Dzięki zgodności problemów z hipergrafami zawias jest zbiorem zakresów ograniczeń i dlatego może być uważany za zbiór ograniczeń. Dodatkowymi warunkami definicji dekompozycji zawiasów są trzy, z których dwa pierwsze zapewniają równoważność problemu pierwotnego z nowym. Dwa warunki równoważności to: zakres każdego ograniczenia jest zawarty w co najmniej jednym węźle drzewa, a poddrzewo indukowane przez zmienną pierwotnego problemu jest połączone. Dodatkowym warunkiem jest to, że jeśli dwa węzły są połączone, to dzielą dokładnie jedno ograniczenie, a zakres tego ograniczenia obejmuje wszystkie zmienne wspólne dla tych dwóch węzłów.

Maksymalna liczba wiązań węzła jest taka sama dla wszystkich dekompozycji zawiasów tego samego problemu. Liczba ta nazywana jest stopniem cykliczności problemu lub jego szerokością zawiasową.

Grupowanie drzew

Klastrowanie drzew lub grupowanie drzewa łączenia opiera się na łączeniu ograniczeń w taki sposób, że wynikowy problem ma drzewo łączenia , to drzewo łączenia jest wynikiem dekompozycji.

Drzewo łączenia problemu spełniania ograniczeń to drzewo, w którym każdy węzeł jest powiązany z ograniczeniami (i odwrotnie) i tak, że poddrzewo węzłów, których ograniczenie zawiera zmienną, jest połączone. W rezultacie tworzenie drzewa sprzężeń można postrzegać jako szczególną formę dekompozycji, w której każdy węzeł drzewa jest powiązany z zakresem ograniczenia.

Nie wszystkie problemy spełniania ograniczeń mają drzewo łączenia. Jednak problemy można modyfikować, aby uzyskać drzewo łączenia poprzez łączenie ograniczeń. Grupowanie drzew opiera się na fakcie, że problem ma drzewo łączenia wtedy i tylko wtedy, gdy jego graf pierwotny jest akordowy i zgodny z problemem, co oznacza, że zmienne każdej maksymalnej kliki grafu pierwotnego są zakresem ograniczenia i nawzajem. Grupowanie drzew modyfikuje dowolny problem w taki sposób, aby te dwa warunki były spełnione. Akordowość jest wymuszana przez dodanie nowych ograniczeń binarnych. Zgodność uzyskuje się przez łączenie ograniczeń.

W szczególności akordowość jest wymuszana przez dodanie do problemu pewnych „fałszywych” ograniczeń binarnych. Są to ograniczenia binarne, które spełniają dowolna para wartości i służą tylko do dodawania krawędzi do pierwotnego wykresu problemu. W szczególności akordowość uzyskuje się przez dodanie krawędzi tworzących wykres indukowany grafu pierwotnego zgodnie z dowolnym uporządkowaniem. Ta procedura jest poprawna, ponieważ indukowany wykres jest zawsze akordowy i uzyskuje się go dodając krawędzie do oryginalnego wykresu.

Zgodność wymaga, aby maksymalne kliki grafu pierwotnego dokładnie pokrywały się z zakresem ograniczeń. Chociaż zakres każdego pierwotnego ograniczenia jest kliką na grafie pierwotnym, ta klika niekoniecznie jest maksymalna. Co więcej, nawet jeśli początkowo była maksymalna, wymuszanie akordów może stworzyć większą klikę. Zgodność jest wymuszana przez łączenie ograniczeń. W szczególności dla każdej maksymalnej kliki wykresu wynikającej z wymuszenia akordowości tworzone jest nowe ograniczenie z kliką jako zakresem. Zadowalające wartości tego nowego ograniczenia to te, które spełniają wszystkie pierwotne ograniczenia, których zakres jest zawarty w kliku. Dzięki tej transformacji każde pierwotne ograniczenie jest „zawarte” w co najmniej jednym nowym ograniczeniu. Rzeczywiście, zakres każdego pierwotnego ograniczenia jest kliką grafu pierwotnego. Ta klika pozostaje kliką nawet po narzuceniu akordów, ponieważ ten proces wprowadza tylko nowe krawędzie. W rezultacie ta klika jest albo maksymalna, albo zawiera się w maksymalnej kliki.


Przykład: problem spełniania ograniczeń binarnych (grupowanie drzew łączących można również zastosować do ograniczeń niebinarnych). Ten graf nie jest akordowy (x3x4x5x6 tworzą cykl czterech węzłów bez cięciwy).	Wykres jest akordowy. Algorytm analizuje węzły od x6 do x1. Czerwona krawędź jest jedyną dodaną krawędzią, ponieważ x6 jest jedynym węzłem mającym dwóch nie połączonych rodziców. Reprezentuje ograniczenie między x4 i x5, które jest spełnione przez każdą parę wartości.	Zidentyfikowano maksymalne kliki wynikowego wykresu. Łączenie w klastry drzewa zastępuje ograniczenia na {x3, x4, x5, x6} dwoma równoważnymi ograniczeniami, jednym na {x3, x4, x5} i jednym na {x4, x5, x6}.

To tłumaczenie wymaga zidentyfikowania maksymalnych klik wykresu akordowego. Można to jednak łatwo zrobić, stosując tę samą kolejność, co do wymuszania akordów. Ponieważ wszyscy rodzice każdego węzła są ze sobą połączeni, maksymalne kliki składają się z węzła (maksymalny węzeł kliki w porządku o maksymalnej liczności) i wszystkich jego rodziców. W rezultacie te maksymalne kliki można wykryć, biorąc pod uwagę każdy węzeł z jego rodzicami.

Problem, który wynika z tego procesu, ma drzewo łączenia, a takie drzewo łączenia można uzyskać, stosując ponownie tę samą kolejność zmiennych. Przechodząc od ostatniego węzła do pierwszego, każde ograniczenie jest połączone z ograniczeniem poprzedzającym, które dzieli z nim więcej zmiennych. Grupowanie drzew łączonych można postrzegać jako metodę dekompozycji, w której:

elementami okładki są kliki wykresu wynikające z narzucenia akordowości;
drzewo jest drzewem łączącym;
każde ograniczenie jest przypisane do wszystkich węzłów drzewa, których zbiory zmiennych zawierają zakres ograniczenia.

Szerokość dekompozycji skupień drzewa to maksymalna liczba zmiennych powiązanych z każdym węzłem drzewa. Szerokość problemu to minimalna szerokość jego dekompozycji skupiających drzewa.

Dekompozycja zawiasów / klastrów

Wynik dekompozycji zawiasów można dodatkowo uprościć, rozkładając każdy zawias za pomocą grupowania drzew. Innymi słowy, po zidentyfikowaniu zawiasów tworzone jest drzewo klastrów każdego z nich. Jeśli chodzi o drzewo wynikowe, każdy węzeł jest zatem zastępowany drzewem.

Dekompozycja zapytania

Dekompozycja zapytania wiąże zestaw zmiennych i zestaw ograniczeń z każdym węzłem drzewa; każde ograniczenie jest powiązane z jakimś węzłem, a poddrzewo indukowane przez węzły powiązane z daną zmienną lub ograniczeniem jest połączone. Dokładniej, dla każdej zmiennej jest połączone poddrzewo węzłów powiązanych z tą zmienną lub z ograniczeniem mającym tę zmienną w swoim zasięgu. Szerokość dekompozycji to maksymalna łączna liczba zmiennych i ograniczeń związanych z węzłem.

Powiązanie ograniczeń z węzłami prawdopodobnie zmniejsza szerokość dekompozycji i instancji. Z drugiej strony ta definicja szerokości nadal pozwala na rozwiązywanie problemów o stałej szerokości w czasie wielomianowym, jeśli podany jest rozkład. W tym przypadku dziedzinę nowej zmiennej uzyskuje się przez rozwiązanie podproblemu, który może być wielomianowo duży, ale ma stałą liczbę ograniczeń. W rezultacie ta domena ma gwarantowany rozmiar wielomianu; ograniczenia nowego problemu, będące równościami dwóch dziedzin, również mają wielkość wielomianową.

Hipergraficzna reprezentacja problemu spełniania ograniczeń: ograniczenia mają nazwy (P, Q, R, S, T), a ich zakresy są pokazane (P (a, b, c) oznacza, że ograniczenie P dotyczy zmiennych {a , pne}

Dekompozycja zapytania problemu. Węzły mogą zawierać zmienne, ograniczenia lub jedno i drugie. Chociaż do prawego węzła jest powiązanych łącznie pięć zmiennych (tj. a,b,c,d,e wśród dwóch ograniczeń), jest to rozkład o szerokości 3, ponieważ żaden węzeł nie zawiera więcej niż trzy ograniczenia i izolowane zmienne (jest inną dekompozycję o szerokości 2 i można pokazać, że ta dekompozycja o szerokości 2 jest minimalną szerokością tego hipergrafu).

Czysta dekompozycja zapytania to dekompozycja zapytania, w której węzły są powiązane tylko z ograniczeniami. Z dekompozycji zapytania o danej szerokości można zbudować w przestrzeni logarytmicznej czystą dekompozycję zapytania o tej samej szerokości. Uzyskuje się to poprzez zastąpienie zmiennych węzła, które nie są objęte ograniczeniami węzła, pewnymi ograniczeniami zawierającymi te zmienne.

Wadą tej metody dekompozycji jest to, że sprawdzanie, czy instancja ma stałą szerokość, jest na ogół NP-zupełne ; udowodniono, że tak jest w przypadku szerokości 4

Dekompozycja Hypertree

Dekompozycja hiperdrzewa wiąże zestaw zmiennych i zestaw ograniczeń z każdym węzłem drzewa. Rozszerza dekompozycję zapytań, pozwalając, aby ograniczenia węzła zawierały zmienne, które nie są używane podczas tworzenia domeny nowej zmiennej powiązanej z węzłem. Oprócz typowych warunków dla metody dekompozycji (zakres każdego ograniczenia obejmuje co najmniej zestaw zmiennych powiązanych z węzłem, a poddrzewo indukowane przez pierwotną zmienną jest połączone), wymagane są następujące dwa warunki:

każda oryginalna zmienna w węźle mieści się w zakresie co najmniej jednego ograniczenia związanego z węzłem;
zmienne ograniczeń węzła, które nie są zmiennymi węzła, nie występują w poddrzewie zakorzenionym w węźle.

Szerokość rozkładu drzewa to maksymalna liczba ograniczeń związanych z każdym węzłem. Jeśli ta szerokość jest ograniczona stałą, problem równoważny oryginalnemu można zbudować w czasie wielomianowym. Zmienne, które nie są powiązane z węzłem, ale znajdują się w zakresie ograniczeń węzła, są „rzutowane” podczas budowania tej instancji. Można to zrobić, najpierw rzutując ograniczenia na zmienne węzła, a następnie znajdując wszystkie rozwiązania tego podproblemu lub najpierw rozwiązując podproblem ze wszystkimi ograniczeniami, a następnie usuwając dodatkowe zmienne.

Dekompozycja hiperdrzewa tego samego problemu co dekompozycja zapytania powyżej. R(b,d,e,-) oznacza, że ostatnia zmienna R nie jest zmienną powiązaną z pierwiastkiem. Dzięki zgrupowaniu dwóch zmiennych w jednym ograniczeniu w korzeniu szerokość zmniejsza się z trzech do dwóch

Powyższe dwa wymagania nie są konieczne do zagwarantowania równoważności pierwotnego i nowego problemu. Są one potrzebne, aby zagwarantować, że problemy o ograniczonej szerokości można rozwiązać w czasie wielomianowym.

Możliwość powiązania ograniczenia z węzłem, podczas gdy niektóre jego zmienne nie są skutecznie powiązane z węzłem, może spowodować powstanie szerokości mniejszej niż szerokość zapytania. $_$ węzeł _ re ${\ Displaystyle D (c, d, e, f)}$ hiperdrzewa może powiązać ten sam węzeł z ograniczeniami ${\ Displaystyle \ {C, D \}}$ i zmienne ${\ Displaystyle \ {a, b, c, d, e \}}$ . Ponieważ podczas sprawdzania szerokości obliczane są tylko ograniczenia, ten węzeł ma szerokość dwa. Ten sam węzeł ma szerokość cztery, gdy używana jest dekompozycja zapytania (jedno ograniczenie i trzy zmienne). Ta redukcja szerokości jest możliwa, jeśli dwie lub więcej zmiennych można zastąpić pojedynczym ograniczeniem, nawet jeśli to ograniczenie zawiera zmienną, która nie jest powiązana z węzłem.

Uogólniony rozkład hiperdrzewa

Uogólnione dekompozycje hiperdrzew są definiowane jak dekompozycje hiperdrzew, ale pominięto ostatnie wymaganie; jest to warunek „zmienne ograniczeń węzła, które nie są zmiennymi węzła, nie występują w poddrzewie zakorzenionym w węźle”. Problem można wyraźnie rozwiązać w czasie wielomianowym, jeśli podano jego rozkład o stałej szerokości. Jednak ograniczenie do stałej szerokości nie jest znane jako wykonalne, ponieważ złożoność znalezienia rozkładu o stałej szerokości, nawet jeśli wiadomo, że istnieje, nie jest znana od 2001 r.

Porównanie

Szerokość instancji jest formą efektywności metod dekompozycji. Rzeczywiście, biorąc pod uwagę, że problemy można rozwiązać za pomocą dekompozycji o stałej szerokości, im mniejsza szerokość zgodnie z dekompozycją, tym więcej przypadków można skutecznie rozwiązać za pomocą tej dekompozycji.

Niektóre dekompozycje wykorzystują liczbę zmiennych węzła (lub podobną ilość) jako szerokość. Inne: cykliczne hipercięcie, dekompozycja zawiasów, dekompozycja zapytań, dekompozycja hiperdrzewa i uogólniona dekompozycja hiperdrzewa nie wiążą ograniczeń (lub ich zakresów w postaci hiperkrawędzi) z węzłami i nie uwzględniają liczby ograniczeń związanych z węzłem na szerokości. Może to być znaczna oszczędność pod względem szerokości. Rzeczywiście, problemy z pojedynczym ograniczeniem na $zmienne$ rozłożyć tylko na drzewo z jednym węzłem. Ten węzeł można powiązać ze $.$ lub z pojedynczym ograniczeniem $,$ liczby zmiennych prowadzi do szerokości $gdy$ liczenie liczby ograniczeń prowadzi do szerokości .

Porównanie wszystkich innych metod dekompozycji opiera się na uogólnieniu i pobiciu. Uogólnienie oznacza, że każdy problem mający szerokość $zgodnie$ z metodą ma szerokość ograniczoną przez stałą $displaystyle$ $n + k$ . Bicie oznacza, że istnieją klasy problemów, które mają stałą szerokość zgodnie z metodą dekompozycji, ale nie według innej. Poniżej przedstawiono wyniki dla dowolnych problemów, w których nie uwzględnia się dekompozycji zapytania:

Dekompozycja hypertree uogólnia i pokonuje wszystkie inne metody
dekompozycja zawiasowa wzmocniona klastrowaniem drzew uogólnia i pokonuje zarówno dekompozycję zawiasową, jak i grupowanie drzew
grupowanie drzew jest równoważne dekompozycji drzewa (na grafie pierwotnym)
zarówno dekompozycja zawiasów, jak i grupowanie drzew uogólniają i pokonują dwupołączone komponenty
cykl cięcia (na pierwotnym wykresie) jest uogólniony i pokonywany zarówno przez hipercięcie cyklu, jak i grupowanie drzew

Można również wykazać, że szerokość grupowania drzew jest równa indukowanej szerokości problemu plus jeden. Algorytm spójności adaptacyjnej, który jest wielomianem dla problemu o ustalonej szerokości indukowanej, zamienia problemy na równoważne w taki sam sposób, jak pierwszy krok grupowania drzew.

Rozwiązywanie z rozkładu

Biorąc pod uwagę drzewo rozkładu, rozwiązanie można wykonać, konstruując problem podobny do drzewa binarnego, jak opisano powyżej, i rozwiązując go. Jest to problem w czasie wielomianowym, ponieważ można go rozwiązać w czasie wielomianowym, stosując na przykład algorytm wymuszający spójność łuku kierunkowego .

Wyspecjalizowany algorytm dla przypadku binarnych problemów acyklicznych wynikających z rozkładu opisano poniżej. Działa poprzez tworzenie ograniczeń, które są przekazywane wzdłuż krawędzi drzewa, od liści do korzenia iz powrotem. Ograniczenie przekazane wzdłuż krawędzi „podsumowuje” skutki wszystkich ograniczeń części wykresu po jednej stronie krawędzi do drugiej.

Ograniczenie przekazane z węzła i do węzła j podsumowuje wpływ węzłów po „stronie” i na zmienne j.

W drzewie każda krawędź dzieli graf na dwie części. Ograniczenie przekazywane wzdłuż krawędzi mówi, w jaki sposób część początkowego końca krawędzi wpływa na zmienne węzła docelowego. Innymi słowy, ograniczenie przekazane z węzła $w jaki sposób węzły „$ węzła mówi $,$ $displaystyle$ stronie” ograniczają zmienne węzła jot $}$ .

Jeśli zmiennymi tych dwóch węzłów są i ${\ Displaystyle X_ {$ $}}$ , węzły o rozmiarze nie wpływają na wszystkie zmienne ${\ displaystyle$ $\ displaystyle X_ {j}},$ $}$ ale tylko wspólne zmienne ${\ Displaystyle X_ {i} \ cap X_ {j}}$ . W rezultacie wpływ na węzły po stronie $}} \cap X_{j}}$ $Displaystyle X_ {j}}$ $można przedstawić$ ograniczenie zmiennych. . Takie ograniczenie można postrzegać jako „podsumowanie” tego, jak zestaw węzłów wpływa na inny węzeł.

Algorytm pochodzi z liści drzewa. W każdym węźle gromadzone są podsumowania jego dzieci (jeśli istnieją). Te podsumowanie i ograniczenie węzła są używane do generowania podsumowania węzła dla jego rodzica. Po osiągnięciu korzenia proces jest odwracany: generowane jest i wysyłane podsumowanie każdego węzła dla każdego dziecka. Po osiągnięciu wszystkich liści algorytm zatrzymuje się.


Drzewo dekompozycji z powiązanymi ograniczeniami. W tym przykładzie wszystkie zmienne mają domenę {0,...,10}.	Węzeł znajdujący się najbardziej na lewo zawiera ograniczenie, w którym <b and shares the variable b with its parent. These constraint allow b only to take values greater than or equal to 1. This constraint b>0 jest wysyłane do jego rodzica.</b>	Lewe dziecko korzenia otrzymuje ograniczenie b>0 i łączy je ze swoim ograniczeniem b 1. To ograniczenie jest wysyłane do jego rodzica.	Gdy korzeń otrzyma ograniczenia dla wszystkich swoich dzieci, łączy je i odsyła im ograniczenia. Proces kończy się, gdy wszystkie liście zostaną osiągnięte. W tym momencie dozwolone wartości zmiennych są jawne.

Zbiór zmiennych współdzielonych przez dwa węzły nazywany jest ich separatorem . Ponieważ separator jest przecięciem dwóch zbiorów powiązanych z węzłami, jego rozmiar nie może być większy niż indukowana szerokość grafu.

Podczas gdy szerokość wykresu wpływa na czas potrzebny do rozwiązania podproblemów w każdym węźle, rozmiar separatora wpływa na rozmiar ograniczeń przekazywanych między węzłami. Rzeczywiście, te ograniczenia mają separatory jako zakres. $,$ rezultacie ograniczenie dotyczące separatora o rozmiarze $domenę$ wymagać przechowywania rozmiaru jeśli wszystkie zmienne $rozmiarze$ .

Kompromis pamięć/czas

Algorytm rozwiązywania problemu z drzewa dekompozycji obejmuje dwie operacje: rozwiązanie podproblemu względem węzła oraz utworzenie ograniczenia względem zmiennych wspólnych (separatora) między dwoma węzłami. W przypadku tych dwóch operacji można zastosować różne strategie. W szczególności tworzenie ograniczeń na separatorach można wykonać za pomocą eliminacji zmiennych, która jest formą wnioskowania, podczas gdy podproblemy można rozwiązać przez wyszukiwanie (śledzenie wsteczne itp.)

Problem z tym algorytmem polega na tym, że ograniczenia przekazywane między węzłami mogą mieć wykładniczy rozmiar w rozmiarze separatora. Pamięć wymaganą do przechowywania tych ograniczeń można zmniejszyć, stosując dekompozycję drzewa z małymi separatorami. Takie drzewa dekompozycji mogą jednak mieć szerokość (liczbę węzłów w każdym węźle) większą niż optymalna.

Dla danego drzewa dekompozycji można wymusić ustalony maksymalny dozwolony rozmiar separatora, łącząc wszystkie pary węzłów, których separator jest większy niż ten rozmiar. Scalanie dwóch węzłów zwykle tworzy węzeł z powiązanym zestawem zmiennych większym niż dwa węzły. Może to zwiększyć szerokość drzewa. Jednak to scalanie nie zmienia separatorów drzewa poza usunięciem separatora między dwoma połączonymi węzłami.

To ostatnie jest konsekwencją acykliczności: dwa połączone węzły nie mogą być połączone z tym samym innym węzłem. ${\ Displaystyle n_ {1}}$ i $}$ {2} to dwa węzły do połączenia i ${\ displaystyle N_ {1}}$ i ${\ displaystyle N_ {2}}$ $w$ zestawami połączonych z nimi węzłów, to byłby cykl. W rezultacie węzeł uzyskany przez połączenie i ${\$ $Displaystyle n_ {2}}$ zostanie połączony z każdym z węzłów $Displaystyle N_ {1} }\kubek N_{2}}$ . W rezultacie separatory tego scalonego węzła są dokładnie separatorami dwóch pierwotnych węzłów.

W rezultacie połączenie pary węzłów połączonych separatorem nie zmienia pozostałych separatorów. W rezultacie można wymusić ustalony maksymalny rozmiar separatora, najpierw obliczając wszystkie rozmiary separatorów, a następnie iteracyjnie łącząc dowolną parę węzłów mających separator większy niż podana wielkość, a rozmiar separatorów nie musi być ponownie obliczany podczas wykonywania.

Ograniczenia strukturalne

Ograniczenie szerokości metody dekompozycji stałą tworzy ograniczenie strukturalne , to znaczy ogranicza możliwe zakresy ograniczeń, ale nie ich relacje. Uzupełniającym sposobem uzyskiwania dających się zastosować podklas spełniania ograniczeń jest nałożenie ograniczeń na relacje ograniczeń; nazywane są one ograniczeniami relacyjnymi , a zbiór dozwolonych relacji nazywany jest językiem ograniczeń .

Jeśli rozwiązywanie problemów o szerokości rozkładu ograniczonej stałą jest w P , rozkład prowadzi do możliwego do rozwiązania ograniczenia strukturalnego. Jak wyjaśniono powyżej, wykonalność wymaga spełnienia dwóch warunków. Po pierwsze, jeśli problem ma szerokość ograniczoną stałą, to można znaleźć rozkład ograniczonej szerokości w czasie wielomianowym. Po drugie, problem uzyskany przez przekształcenie pierwotnego problemu zgodnie z rozkładem nie jest superwielomianem większy niż pierwotny problem, jeśli rozkład ma stałą szerokość.

Podczas gdy większość możliwych do usunięcia ograniczeń strukturalnych wynika z ustalenia szerokości metody dekompozycji, opracowano inne. Niektóre można przeformułować pod kątem metod dekompozycji: na przykład ograniczenie do binarnego problemu acyklicznego można przeformułować jako problem o szerokości drzewa 1; ograniczenie indukowanej szerokości (która nie jest zdefiniowana w kategoriach dekompozycji) można przeformułować jako grupowanie drzew.

Wczesne ograniczenie strukturalne (które później przekształciło się w oparte na indukowanej szerokości) opiera się na szerokości pierwotnego wykresu problemu. Biorąc pod uwagę kolejność węzłów grafu, szerokość węzła to liczba węzłów, które go łączą i poprzedzają w kolejności. Jednak ograniczenie tylko szerokości nie prowadzi do wykonalnego ograniczenia: nawet ograniczenie tej szerokości do 4, ustalenie spełnialności pozostaje NP-zupełne . Tractability uzyskuje się poprzez ograniczenie relacji; $szczególności$ , jeśli problem ma szerokość $.$ jest silnie spójny, można go skutecznie rozwiązać Jest to ograniczenie, które nie jest ani strukturalne, ani relacyjne, ponieważ zależy zarówno od zakresów, jak i relacji ograniczeń.

Zobacz też

Dekompozycja drzewa w teorii grafów
Algorytm Junction Tree używany w uczeniu maszynowym do wydobywania marginalizacji z ogólnych wykresów.

Zasoby online

Oto kilka linków do zasobów online dotyczących ogólnej dekompozycji drzewa/hiperdrzewa.

Treewidthlib : Benchmark dla algorytmów dla Treewidth i powiązanych problemów z wykresami
Implementacja C++ użyta w artykule „A complete Anytime Algorithm for Treewidth, Vibhav Gogate and Rina Dechter, UAI 2004”. Link prowadzi do strony domowej autora, gdzie dystrybuowane są zarówno źródła LINUX, jak i pliki wykonywalne Windows.
Implementacja Hypertree Decomposition , wykorzystująca kilka heurystyk.
Narzędzie paska narzędzi ma implementację niektórych heurystyk dekompozycji drzewa
Biblioteka TreeD: zawiera kod źródłowy niektórych metod dekompozycji

Dechter, Rina (2003). Przetwarzanie ograniczeń . Morgana Kaufmanna. ISBN 1-55860-890-7
Downey, Rod ; Stypendyści, Michael (1997). Złożoność parametryczna . Skoczek. ISBN 0-387-94883-X
Gottlob, Georg ; Leone, Nicola ; Scarcello, Francesco (2001). „Rozkłady hiperdrzewa: ankieta” . MFC 2001 . s. 37–57. ^{[ martwy link ]}
Gottlob, Georg; Leone, Nicola; Scarcello, Francesco (2000). „Porównanie strukturalnych metod rozkładu CSP” . Sztuczna inteligencja . 124 (2): 243–282. doi : 10.1016/S0004-3702(00)00078-3 .