Begränsning sammansatt graf

Den sammansatta begränsningsgrafen är en nodvägd oriktad graf som är associerad med ett givet kombinatoriskt optimeringsproblem utgjort som ett viktat problem med begränsningstillfredsställelse . Utvecklad och introducerad av Satish Kumar Thittamaranahalli (TK Satish Kumar), är idén med den sammansatta begränsningsgrafen ett stort steg mot att förena olika tillvägagångssätt för att utnyttja "struktur" i problem med viktade begränsningstillfredsställelse.

Ett viktat constraint satisfaction problem (WCSP) är en generalisering av ett constraint satisfaction problem där restriktionerna inte längre är "hårda" utan utvidgas för att specificera icke-negativa kostnader förknippade med tuplarna . Målet är då att hitta en tilldelning av värden till alla variabler från sina respektive domäner så att den totala kostnaden minimeras. Viktade problem med tillfredsställelse av begränsningar hittar otaliga tillämpningar inom artificiell intelligens och datavetenskap . De kallas också på olika sätt för markovslumpfält (i statistik och signalbehandling ) och energiminimeringsproblem ( i fysik ).

Medan problem med viktad begränsningstillfredsställelse är NP-svåra att lösa i allmänhet, kan flera underklasser lösas i polynomtid när deras viktade begränsningar uppvisar specifika typer av numerisk struktur. Trakterbara underklasser kan också identifieras genom att analysera hur begränsningar placeras över variablerna. Specifikt kan ett viktat problem med tillfredsställelse av begränsningar lösas i exponentiell tid endast i trädbredden av dess graf med variabel interaktion (begränsningsnätverk). En stor nackdel med begränsningsnätverket är emellertid att det inte tillhandahåller ett beräkningsramverk för att utnyttja den numeriska strukturen för de viktade begränsningarna.

Till skillnad från begränsningsnätverket tillhandahåller den sammansatta begränsningsgrafen ett sammanhållande ramverk för att representera både den grafiska strukturen för variabelinteraktionerna såväl som den numeriska strukturen för de viktade begränsningarna. Den kan konstrueras med hjälp av en enkel polynom-tid-procedur; och ett givet problem med viktad begränsningstillfredsställelse kan reduceras till problemet med att beräkna det minsta viktade vertextäcket för dess tillhörande begränsningssammansatta graf. De "hybrid" beräkningsegenskaperna hos den sammansatta begränsningsgrafen återspeglas i följande två viktiga resultat:

(Resultat 1) Den sammansatta begränsningsgrafen för ett givet viktat problem med begränsningstillfredsställelse har samma trädbredd som dess associerade begränsningsnätverk.

(Resultat 2) Många underklasser av problem med viktad begränsningstillfredsställelse som kan hanteras på grund av den numeriska strukturen av deras viktade begränsningar har associerade begränsningssammansatta grafer som är tvådelade till sin natur.

Resultat 1 visar att den sammansatta grafen för restriktioner kan användas för att fånga den grafiska strukturen för de variabla interaktionerna (eftersom ett minsta viktat vertextäcke för vilken graf som helst kan beräknas i exponentiell tid endast i den grafens trädbredd). Resultat 2 visar att den sammansatta begränsningsgrafen också kan användas för att fånga den numeriska strukturen för de viktade begränsningarna (eftersom ett minsta viktat vertextäcke kan beräknas i polynomtid för tvådelade grafer).

Empiriskt, när man löser en WCSP, har det visat sig att det är mer fördelaktigt att tillämpa meddelandeöverföringsalgoritmer och heltalslinjär programmering på WCSP:s sammansatta begränsningsgraf än på WCSP direkt.