Constraintvervullingsproblemen

Een constraintvervullingsprobleem, of CSP, beschrijft een verzameling keuzes en de regels die ze verbinden. De toestand heeft een gefactoriseerde representatie: je kunt afzonderlijke variabelen en hun waarden bekijken en vervolgens algemene methoden voor het verwijderen van waarden en het zoeken opnieuw gebruiken.

Variabelen, domeinen en constraints

Een variabele benoemt iets wat gekozen moet worden. Het domein bevat de toegestane waarden. Een constraint geeft aan welke combinaties samen mogen voorkomen. Laat voor workshops A en B elke waarde een tijdvak uit $\{1,2,3\}$ zijn. De regel “A komt vóór B” heeft variabelenbereik $\{A,B\}$ en constraintrelatie $\{(1,2),(1,3),(2,3)\}$. De schrijfwijze $A<B$ drukt dezelfde relatie beknopt uit.

Het variabelenbereik noemt de betrokken variabelen; de constraintrelatie geeft de toegestane waardetupels. Als je die verwart, kan een model ontstaan waarin “rood” een variabele wordt. Bij het kleuren van een kaart zijn regio's variabelen en kleuren waarden.

Wat telt als oplossing?

Een waardetoekenning geeft waarden aan variabelen. Drie controles beschrijven de status ervan:

• De waardetoekenning is gedeeltelijk als sommige variabelen geen waarde hebben.
• De waardetoekenning is volledig als elke variabele een waarde heeft.
• De waardetoekenning is consistent als die geen constraint tussen de variabelen met een waarde schendt.

Een oplossing moet volledig en consistent zijn. Met alleen $A=2$ is de waardetoekenning consistent maar gedeeltelijk. Uitbreiding met $B=1$ maakt haar volledig en inconsistent. De keuze $B=3$ geeft een oplossing voor dit voorbeeld met twee variabelen. Een consistente gedeeltelijke waardetoekenning kan toch onmogelijk volledig worden gemaakt: bij variabelen zonder waarde kunnen de passende keuzes opraken.

Lees een constraintgraaf

Teken voor een binair CSP één knoop per variabele en één verbinding voor elk paar met een constraint. Op een vereenvoudigde kaart van Australië zijn de variabelen WA, NT, SA, Q, NSW, V en T, elk met domein {rood, groen, blauw}. De aangrenzende paren zijn WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW en NSW–V. Elke verbinding vereist verschillende kleuren.

Een oplossing is WA rood, NT groen, SA blauw, Q rood, NSW groen, V rood en T rood. Controleer elke verbinding, ook SA–V. T heeft geen verbinding, dus is de kleur onafhankelijk van het vasteland. Er zijn 6 kleuringen van het vasteland en 3 keuzes voor T, samen 18 oplossingen. Een constraint met meerdere variabelen vereist een hypergraafrepresentatie; een extra constraintknoop kan worden verbonden met elke variabele in het variabelenbereik.

Domeinen en zoekruimte

Een eindig discreet domein is een vaste lijst, zoals drie kleuren. Een oneindig discreet domein kan elke niet-negatieve gehele begintijd bevatten. Een continu domein kan tijden met reële waarden bevatten. De laatste twee vereisen representaties en methoden die bij die domeinen passen; lineair programmeren behandelt continue lineaire constraints.

Voor $n$ variabelen met elk $d$ waarden zijn er $d^n$ volledige waardetoekenningen. De kaart heeft $3^7=2187$ kandidaten voordat constraints er uitsluiten. Eindige CSP's omvatten NP-complete problemen, dus is er geen algemene oplossingsmethode in polynomiale tijd bekend. Hun interne structuur maakt het toch mogelijk waarden uit te sluiten: de oplosser kan een keuze uitsluiten zonder elke volledige waardetoekenning met die keuze op te sommen. Alleen de uiteindelijke waarden bepalen of het antwoord geldig is; het pad waarlangs ze zijn gevonden, is niet van belang.

Constraints verschillen in het aantal variabelen dat ze verbinden en in de vraag of ze eisen of voorkeuren aangeven. Als je die structuur herkent, kun je een getrouw model schrijven en bruikbare propagatiemethoden kiezen.

Deel in naar variabelenbereik

Een unaire constraint beperkt één variabele. Als workshop E tijdvak 1 niet kan gebruiken, pas je $E\mathrm{\ne }1$ toe door het domein vóór het zoeken te verkleinen van $\{1,2,3\}$ tot $\{2,3\}$. Een binaire constraint legt een verband tussen twee variabelen, zoals $A<B$ of $A\mathrm{\ne }D$. Een binair CSP bevat alleen unaire en binaire constraints.

Een constraint van hogere orde heeft betrekking op minstens drie variabelen. Als de taakduren X, Y en Z samen 10 uur moeten vullen, schrijf je $X+Y+Z=10$. Met elke duur in $\{1,2,3,4,5\}$ voldoet de tupel $(2,3,4)$ niet, terwijl $(2,3,5)$ wel voldoet. Bij de controle van een regel van hogere orde moeten de waarden samen voldoen.

Behoud nuttige globale constraints

Een globale constraint geeft een benoemde regel over een groep met een variabel aantal leden. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ vereist voor elk paar verschillende waarden. De oplossingsverzameling is gelijk aan die van de $k(k-1)\mathrm{/}2$ paarsgewijze ongelijkheden. Voor negen Sudokucellen zijn dat 36 binaire constraints.

De globale vorm laat een oplosser ook over de groep redeneren. Drie variabelen die beperkt zijn tot twee verschillende waarden kunnen niet allemaal verschillen, ook al heeft elk afzonderlijk paar een verenigbare waardetoekenning. Gelijke oplossingsverzamelingen garanderen niet dat evenveel waarden kunnen worden verwijderd.

Een capaciteitsregel kan ook globaal zijn. Hier betekent $\mathrm{Atmost}(10,P_1,P_2,P_3)$ hetzelfde als $P_1+P_2+P_3\le 10$: het totale aantal mensen dat aan de drie taken is toegewezen, mag niet groter zijn dan tien. De argumenten stellen aantallen voor die worden opgeteld, dus staat deze regel bijvoorbeeld $(3,4,3)$ toe.

Zet een eindige constraint om naar binaire vorm

Introduceer een hulpvariabele U waarvan de waarden de toegestane drietallen voor $X+Y+Z=10$ zijn. Eén mogelijke waarde is $(2,3,5)$. Voeg drie binaire constraints toe: de eerste component van U is gelijk aan X, de tweede aan Y en de derde aan Z. Als je die waarde voor U kiest, vereist dat dus $X=2$, $Y=3$ en $Z=5$.

Elk oorspronkelijk geldig drietal komt overeen met een waarde van U en elke consistente waardetoekenning met U levert een geldig oorspronkelijk drietal op. Met deze constructie kunnen binaire methoden een eindige constraint van hogere orde behandelen. De prijs is het mogelijk grote tupeldomein; daarom behouden oplossers vaak de oorspronkelijke globale regel of regel van hogere orde.

Eisen en voorkeuren

Met zachte constraints wordt de taak een optimalisatieprobleem met constraints, of COP: voldoe aan alle harde regels en minimaliseer de totale kosten van voorkeuren. Voor optimalisatie kun je vertakken en begrenzen en lokaal zoeken gebruiken.

Test het model met een waardetoekenning waarvan je weet dat die geldig is en een waarvan je weet dat die ongeldig is. Een verzonnen ongelijkheid tussen workshops zonder onderling verband sluit geldige roosters uit; een ontbrekende constraint voor een gezamenlijke trainer laat onmogelijke roosters toe. Ook voorkeuren vereisen aandacht: als je “middag heeft de voorkeur” verandert in “middag is verplicht”, kan elk haalbaar rooster verdwijnen.

Een model moet de beslissingen zo rechtstreeks beschrijven dat de regels gemakkelijk zijn uit te drukken. Bepaal eerst wat gekozen moet worden, ken vervolgens domeinen toe en vertaal elke eis naar een constraint over de variabelen waarop die werkelijk betrekking heeft.

Maak een workshoprooster

Vijf workshops van elk één tijdvak delen drie tijdvakken: 1 ochtend, 2 middaguur en 3 middag. Laat A Python voor beginners zijn, B Python voor gevorderden, C Statistiek, D Databases en E Ethiek. Elke workshop is een variabele met begindomein $\{1,2,3\}$.

Gezamenlijke deelnemers vereisen $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$ en $D\mathrm{\ne }E$. De beginnersworkshop moet voorafgaan aan de gevorderdenworkshop, dus $A<B$. De trainer van Ethiek komt op het middaguur aan, dus $E\mathrm{\ne }1$. Dit geeft zeven binaire verbindingen en één unaire regel; C heeft vier aangrenzende variabelen.

De waardetoekenning $A=2,B=3,C=1,D=3,E=2$ voldoet aan elke regel: elk paar met gezamenlijke deelnemers verschilt, de beginnersworkshop gaat vooraf aan de gevorderdenworkshop en Ethiek staat niet in tijdvak 1. Het is de enige geldige waardetoekenning onder de $3^5=243$ kandidaten. Workshops B en D mogen allebei tijdvak 3 gebruiken omdat geen regel vereist dat ze verschillen.

Als je in plaats daarvan één variabele per tijdvak kiest, wordt elke waarde een deelverzameling van workshops, met maximaal $2^5=32$ mogelijke deelverzamelingen per tijdvak. Regels zouden dan die verzamelingen moeten bekijken en ervoor moeten zorgen dat elke workshop eenmaal voorkomt. Met workshops als variabelen blijven de constraints eenvoudiger.

Druk taakduur en gedeelde hulpbronnen uit

Gebruik bij werkplaatsplanning voor elke taak een variabele voor de begintijd. Voorbereiden duurt 20 minuten, Analyseren 40 en Rapporteren 30. Begintijden zijn niet-negatieve gehele aantallen minuten. De volgorde en de uiterste tijd van 120 minuten geven

De vroegste begintijden zijn 0, 20 en 60. Als je vanaf de uiterste tijd terugwerkt, krijg je de laatste begintijden 30, 50 en 90. De intervallen zijn dus $S_P\in [0,30]$, $S_A\in [20,50]$ en $S_R\in [60,90]$.

Twee taken die een machine delen, hebben een disjunctieve constraint nodig: $S_X+d_X\le S_Y$ of $S_Y+d_Y\le S_X$. Beide taken kunnen als eerste komen, maar ze mogen niet overlappen. Een eenvoudige voorrangsconstraint zou één bepaalde volgorde afdwingen en de andere mogelijkheid uitsluiten.

Modelleer toewijzingen en puzzels

Maak voor drie rapporten die aan drie beoordelaars worden toegewezen elk rapport een variabele met beoordelaars als waarden. Gebruik Alldiff als elke beoordelaar één rapport behandelt. Een belangenconflict verwijdert een beoordelaar uit het domein van het betreffende rapport.

Laat voor het n-damesprobleem $Q_i$ de rij zijn van de dame in kolom $i$. Eén dame per kolom is in het model ingebouwd. Vereis voor elk paar $Q_i\mathrm{\ne }{Q}_j$ en $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$ om aanvallen over rijen en diagonalen te voorkomen. Voor acht dames verkleint dit de ruimte van mogelijke oplossingen van de keuze van 8 velden uit 64, $\mathrm{4.426.165.368}$ plaatsingen, tot $8^8=\mathrm{16.777.216}$ waardetoekenningen. Er zijn 92 oplossingen.

Voor Sudoku hebben de 81 celvariabelen domein 1–9. Gegeven cijfers leggen unaire constraints op en de 9 rijen, 9 kolommen en 9 blokken leggen elk Alldiff op.

Kies de grofste tijdseenheden waarmee je nog elke toegestane begintijd kunt weergeven. Sessies die op het hele uur beginnen hebben keuzes per uur nodig; domeinen per minuut zouden het werk vergroten zonder een nuttig rooster toe te voegen. Sluit af door voorkeuren van harde regels te scheiden en een klein geval met een bekend antwoord te controleren.

Backtracking bouwt een gedeeltelijke waardetoekenning op met diepte-eerst zoeken. De methode kiest één variabele, probeert een waarde en gaat door tot ze een oplossing vindt of een keuze ongedaan moet maken. Het zoeken behoudt de bruikbare eerdere keuzes als een latere keuze mislukt.

Vertak op waarden, één variabele tegelijk

Eerst A en dan B een waarde geven levert dezelfde uiteindelijke waardetoekenning op als eerst B en dan A. Door deze commutativiteit kan een CSP-oplosser op elk niveau één variabele kiezen en op haar waarden vertakken. Als je elke variabelevolgorde zou toestaan, zou je $n!d^n$ bladeren krijgen voor slechts $d^n$ verschillende volledige waardetoekenningen. Voor vijf variabelen met drie waarden zijn dat 29.160 bladeren in plaats van 243.

De volgende variabele kan afhangen van de huidige domeinen. Het gaat erom dat je in een knoop één volgende variabele kiest; het zoeken heeft geen afzonderlijke takken nodig voor alle mogelijke volgorden van waardetoekenning.

Volg de recursieve stappen

1. Als de waardetoekenning volledig en consistent is, geef die dan terug.
2. Kies een variabele zonder waarde.
3. Probeer elke domeinwaarde die consistent is met de huidige waardetoekenning.
4. Roep de methode recursief aan nadat je een waarde hebt toegevoegd. Als de recursieve aanroep mislukt, maak die waardetoekenning dan ongedaan en probeer de volgende waarde.
5. Als geen waarde werkt, meld de mislukking dan aan de aanroeper.

Gewone backtracking test een constraint zodra alle variabelen in het variabelenbereik een waarde hebben. Bij $A=1$ en B zonder waarde heeft $A<B$ geen volledig paar om te verwerpen. Als je dan $B=1$ probeert, mislukt dat onmiddellijk. Wachten tot elke variabele een waarde heeft, zou deze eenvoudige afwijzing uitstellen.

Volg een doodlopend zoekpad

Gebruik de workshopregels: $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Neem de variabelen in de volgorde A, B, C, D, E en probeer de waarden 1, 2, 3.

• Kies $A=1$. Verwerp $B=1$ en kies $B=2$.
• Verwerp $C=1$ vanwege A en $C=2$ vanwege B; kies $C=3$.
• Verwerp $D=1$ vanwege A; kies $D=2$.
• E heeft geen toegestane waarde: 1 is verboden, 2 botst met D en 3 botst met C.

De mislukking bij E brengt de zoekmethode terug naar D. De volgende waarde daarvan, 3, botst met C. C heeft geen latere waarde, dus keert de zoekmethode terug naar B. De poging $B=3$ levert uiteindelijk nog een doodlopend zoekpad op onder $A=1$. Daarna probeert de zoekmethode $A=2$ en bereikt ze $A=2,B=3,C=1,D=3,E=2$. In deze volgorde test gewone backtracking in totaal 32 mogelijke waarden, inclusief afgewezen waarden.

Wat de methode garandeert

Constraints controleren en het model opslaan hebben ook kosten. De beschrijving van lineair geheugengebruik betreft het zoekpad, terwijl propagatie ook domeinen en gegevens voor het ongedaan maken kan opslaan.

Chronologische backtracking keert terug naar de meest recente keuze. Snellere varianten verbeteren vier afzonderlijke beslissingen: de volgende variabele, de volgorde van haar waarden, de gevolgen die na een keuze worden afgeleid en de eerdere keuze waarnaar na een mislukking wordt teruggekeerd. Deze verbeteringen verminderen het werk in de praktijk zonder te veranderen wat als oplossing telt.

Een goede ordening kan een mislukking dicht bij de top van een zoekboom zichtbaar maken of bruikbare keuzes bewaren voor later. Variabeleordening en waardeordening dienen verschillende doelen, dus verschilt de richting die het beste lijkt.

Kies de meest beperkte variabele

De heuristiek van de minste resterende waarden (MRV) kiest de variabele zonder waarde met de minste waarden die op dat moment zijn toegestaan. Ze heet ook de heuristiek van de meest beperkte variabele of de vroeg-falenheuristiek. Een bijna uitgeput domein zal waarschijnlijk snel een tegenspraak aan het licht brengen. Als een domein leeg is, mislukt de tak onmiddellijk.

Tel de huidige waarden nadat waarden zijn verwijderd, niet de oorspronkelijke domeingrootten. Zonder opgeslagen domeinen moet een oplosser bepalen welke oorspronkelijke waarden nog consistent zijn met de waardetoekenning voordat MRV wordt toegepast.

De graadheuristiek maakt bij MRV een keuze tussen gelijke kandidaten door de variabele te kiezen met de meeste constraints op andere variabelen zonder waarde. Zo'n keuze beïnvloedt meer resterende beslissingen. Aangrenzende variabelen die al een waarde hebben, tellen niet mee voor deze resterende graad. Aan het begin op de kaart van Australië staan de gelijke domeinen met drie kleuren op gelijke hoogte en geven de vijf aangrenzende regio's SA de hoogste graad.

Houd opties open bij de keuze van een waarde

De minst beperkende waarde (LCV) probeert de waarde die de minste waarden verwijdert uit de domeinen van aangrenzende variabelen zonder waarde. Het beoordelen van mogelijke waarden kost extra rekenwerk, maar kan een kostbare mislukte tak voorkomen.

Met WA rood en NT groen kan SA alleen blauw zijn, terwijl Q rood of blauw kan zijn. Als je Q blauw kiest, wordt het domein van SA leeg. Als je Q rood kiest, verdwijnt rood uit het domein van NSW en blijft blauw voor SA behouden. LCV probeert daarom Q rood.

Elke variabele moet uiteindelijk een waarde krijgen, waardoor het nuttig is een kwetsbare variabele vroeg te testen. Voor een eerste oplossing is slechts één waarde nodig, wat pleit voor een waarde die ruimte laat voor andere beslissingen.

Combineer ordening met voorwaartse controle

Pas in het workshoprooster eerst $E\mathrm{\ne }1$ toe. E heeft twee waarden; A, B, C en D hebben er elk drie. MRV kiest E. Probeer $E=2$ en voorwaartse controle verwijdert 2 uit de domeinen van C en D.

C en D staan nu gelijk met domeinen $\{1,3\}$. C heeft drie aangrenzende variabelen zonder waarde, A, B en D; D heeft er twee, A en C. De graadheuristiek kiest C. Kies $C=1$, waarna $D_D=\{3\}$ en $D_A=D_B=\{2,3\}$ overblijven. MRV kiest $D=3$, wat $A=2$ afdwingt; de voorrangsregel geeft dan $B=3$. Met vijf waardetoekenningen wordt de oplossing gevonden zonder terug te keren. Een vaste variabelevolgorde met voorwaartse controle heeft 12 waardetoekenningen nodig en bereikt twee doodlopende zoekpaden.

Ordening behoudt de volledigheid omdat ze de volgorde van keuzes verandert zonder toegestane takken uit te sluiten. Het zoeken blijft in het slechtste geval exponentieel. Als je elke oplossing opsomt of onoplosbaarheid bewijst, moeten uiteindelijk alle relevante waarden worden onderzocht, zodat het voordeel van LCV om vroeg succes te hebben afneemt. Het belangrijkste nut is om eerder een eerste oplossing te vinden.

Een doodlopend zoekpad heeft vaak een kleinere oorzaak dan de hele huidige waardetoekenning. Terugspringen gebruikt die oorzaak om te bepalen waarheen wordt teruggekeerd en constraints leren onthoudt een mislukking zodat die niet opnieuw hoeft te worden ontdekt.

Vind de keuzes die de mislukking veroorzaakten

Neem op de kaart van Australië de volgorde van waardetoekenning Q, NSW, V, T, SA. Laat Q rood zijn, NSW groen, V blauw en T rood. SA grenst aan Q, NSW en V, dus zijn alle drie de kleuren verboden. De conflictverzameling van SA is $\{Q,NSW,V\}$: eerdere variabelen waarvan de keuzes de waarden van SA uitsluiten.

Chronologische backtracking zou proberen T te veranderen. Tasmanië heeft geen verbinding met SA, dus kan het veranderen van de kleur geen optie voor SA herstellen. Terugspringen keert terug naar V, het lid van de conflictverzameling dat het laatst een waarde kreeg, en slaat T over.

Een conflictverzameling bevat variabelen; een verboden combinatie legt specifieke waardetoekenningen vast. Dat onderscheid is belangrijk: een andere kleur voor V kan de mislukking verhelpen, ook al blijft V een buur van SA.

Voer een conflict mee door eerdere mislukkingen

Eenvoudig terugspringen gebruikt de directe conflictverzameling van de huidige mislukking. Conflictgestuurd terugspringen voert informatie mee door meerdere mislukte niveaus. Als een mislukte variabele X terugspringt naar Y, neemt Y de conflictverzameling van X over zonder Y. Als Y later alle waarden heeft uitgeput, wijst de gecombineerde verzameling een oorzaak verder terug in de waardetoekenning aan.

Gebruik bijvoorbeeld de volgorde WA, NSW, T, NT, Q, V, SA en begin met WA rood, NSW rood, T rood. WA en NSW grenzen niet aan elkaar, dus is deze gedeeltelijke waardetoekenning consistent. Hun keuzes verwijderen rood uit de domeinen van NT, Q en SA. Die drie regio's vormen een driehoek, die niet met alleen groen en blauw kan worden gekleurd.

Geen enkele keuze voor T verandert die driehoek. Conflictinformatie kan via de mislukte pogingen teruggaan en WA en NSW aanwijzen als de onderliggende oorzaak. De zoekmethode keert terug naar NSW, de latere van die twee beslissingen, in plaats van tijd te besteden aan het opnieuw kleuren van T.

Leer de mislukte combinatie

Een oplosser kan $\{WA=\text{rood},NSW=\text{rood}\}$ vastleggen als verboden combinatie. Telkens als beide keuzes opnieuw voorkomen, volgt dezelfde tegenspraak in de driehoek, zodat de tak onmiddellijk kan worden afgewezen. Het zou onjuist zijn om WA rood op zichzelf te verbieden: WA kan rood zijn in geldige oplossingen met een andere kleur voor NSW.

Leren voegt een constraint of een opgeslagen verboden combinatie toe. De geleerde voorwaarde moet volgen uit de oorspronkelijke constraints; een mislukking die alleen wordt veroorzaakt doordat een tijdslimiet is bereikt, biedt geen dergelijke logische rechtvaardiging. Een bruikbare verboden combinatie bevat genoeg waardetoekenningen om de onmogelijkheid te verklaren, zonder keuzes op te nemen die er niets mee te maken hebben.

Combineer vooruitkijken en terugkijken

Voorwaartse controle en boogconsistentie verwijderen waarden zonder ondersteuning voordat een mislukking diep in de boom optreedt. Terugspringen onderzoekt een mislukking nadat die is opgetreden. Eenvoudig direct terugspringen sluit geen mogelijkheden uit boven op wat voorwaartse controle al ontdekt, maar conflictgestuurde methoden kunnen verklaringen van diepere mislukkingen combineren. Leren bewaart die verklaringen voor latere takken.

Voorwaartse controle onderzoekt wat een nieuwe waardetoekenning direct uitsluit voor aangrenzende variabelen zonder waarde. Ze verwijdert onverenigbare waarden voordat de zoekmethode die variabelen bereikt, waardoor sommige doodlopende zoekpaden enkele niveaus eerder zichtbaar worden.

Verwijder waarden na een waardetoekenning

Bekijk na de keuze $X=x$ elke variabele Y zonder waarde die een constraint met X deelt. Verwijder elke waarde in $D_Y$ die met de keuze conflicteert. Een leeg domein betekent dat de huidige tak niet tot een volledige waardetoekenning kan leiden, dus keer je direct terug.

Bij $X\mathrm{\ne }Y$ verwijdert de waardetoekenning $X=2$ de waarde 2 uit het domein van Y. Bij $X<Y$ verwijdert $X=2$ elke waarde van Y die hoogstens 2 is. De relatie zelf bepaalt wat wordt verwijderd; voorwaartse controle beperkt zich niet tot het verwijderen van gelijke waarden.

Het verwijderen van waarden verandert de domeinen van de huidige tak. Houd in een herstellogboek elke verwijdering bij die door de keuze is veroorzaakt. Als die keuze ongedaan wordt gemaakt, herstel je de daardoor verwijderde waarden en behoud je de beperkingen die bij eerdere keuzes horen. Kopieën van domeinen op elk niveau bieden een andere implementatie.

Volg de workshopdomeinen

Gebruik tijdvakken 1–3 en de regels $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Pas de unaire regel toe om $D_E=\{2,3\}$ te krijgen en gebruik daarna de vaste volgorde A, B, C, D, E.

1. Na $A=1$ blijft voor B, C en D telkens $\{2,3\}$ over.
2. Na $B=2$ blijft voor C alleen $\{3\}$ over.
3. Na $C=3$ blijft voor D en E elk alleen $\{2\}$ over.
4. $D=2$ verwijdert 2 uit het domein van E, waardoor dat leeg raakt. Keer terug.

Als de domeinen zijn hersteld en $B=3$ wordt geprobeerd, moet C gelijk zijn aan 2. Voor zowel D als E blijft dan alleen 3 over, dus maakt de waardetoekenning aan D het domein van E opnieuw leeg. De zoekmethode moet A veranderen. Met $A=2$ kan ze $B=3,C=1,D=3,E=2$ bereiken. In dit verloop worden 12 waarden geprobeerd, tegenover 32 mogelijke waarden bij gewone backtracking in dezelfde volgorde.

Herken de grens van controle in één stap

Na stap 3 hebben D en E allebei alleen de waarde 2 en moeten ze verschillen. Voorwaartse controle heeft die constraint nog steeds niet gecontroleerd: noch D noch E heeft net een waarde gekregen. Ze ontdekt de mislukking pas als D een waarde krijgt.

Dit is de belangrijkste beperking van voorwaartse controle. Ze toetst de variabele met een waarde aan de aangrenzende variabelen zonder waarde, zonder de gevolgen van een kleiner domein van een aangrenzende variabele verder te verspreiden. Boogconsistentie kan die gevolgen tussen variabelen zonder waarde wel volgen.

Gebruik de bijgehouden domeinen

MRV kan nu direct het kleinste resterende domein kiezen. Een domein met één waarde wordt vaak als volgende gekozen; een leeg domein wijst op een mislukking zonder dat nog een waardetoekenning nodig is. Domeinen actueel houden helpt zowel bij inferentie als bij ordening.

Voor maximaal $n-1$ aangrenzende variabelen en maximaal $d$ waarden per aangrenzende variabele gebruikt een ronde voorwaartse controle ongeveer $O(nd)$ binaire controles, aangenomen dat een relatietest constante tijd kost. Ze verwijdert alleen waarden die onverenigbaar zijn met de huidige waardetoekenning, dus blijft backtracking volledig. Als je vergeet een verwijderde waarde te herstellen, kan een latere tak een geldige oplossing verliezen; waarden verwijderen uit het domein van een niet-betrokken variabele kan hetzelfde gevolg hebben.

Een waarde heeft in elk aangrenzend domein een verenigbare partner nodig. Boogconsistentie maakt die ondersteuningseis expliciet en volgt de gevolgen van domeinwijzigingen door een binair CSP.

Ondersteuning heeft een richting

Knoopconsistentie verwijdert eerst waarden die door unaire regels zijn verboden. Voor een binaire constraint is de gerichte boog $X\to Y$ consistent als elke waarde in X minstens één verenigbare waarde in Y heeft. Die waarde in Y is een ondersteunende waarde. Bij het herzien van de boog worden waarden zonder ondersteuning uit de beginknoop X verwijderd.

Bij $A<B$ met voor beide domeinen $\{1,2,3\}$ verwijdert het herzien van $A\to B$ de waarde 3 uit A. Het herzien van $B\to A$ verwijdert 1 uit B. De resulterende domeinen zijn $D_A=\{1,2\}$ en $D_B=\{2,3\}$. Een overgebleven waarde kan voor elke aangrenzende variabele een andere ondersteunende waarde gebruiken; die ondersteunende waarden hoeven samen geen oplossing te vormen.

Voer AC-3 uit

AC-3 gebruikt een wachtrij van gerichte bogen:

1. Zet aanvankelijk elke boog in de wachtrij.
2. Neem $X\to Y$ uit de wachtrij en herzie X met behulp van het domein van Y.
3. Als het domein van X leeg wordt, stop dan en meld dat de methode is mislukt.
4. Als het domein van X krimpt, voeg dan $Z\to X$ toe voor elke andere aangrenzende variabele Z van X, met uitzondering van Y.
5. Ga door tot de wachtrij leeg is.

Een verwijdering uit X kan een ondersteunende waarde voor Z wegnemen, dus moet de wachtrij bogen bevatten die terugwijzen naar het gewijzigde domein. De boog vanuit Y hoeft niet direct opnieuw te worden gecontroleerd: de verwijderde waarden van X ondersteunden geen enkele waarde in Y, omdat ze om te beginnen met geen daarvan verenigbaar waren. Als alle einddomeinen niet leeg zijn, zijn ze onafhankelijk van de verwerkingsvolgorde; verschillende volgorden kunnen bij een mislukking tot verschillende lege domeinen leiden.

Propageer een workshopbeslissing

Voor de workshopregels $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$ verwijdert de eerste uitvoering van AC-3 de waarde 3 uit A en 1 uit B. Voor C en D blijft $\{1,2,3\}$ over en voor E blijft $\{2,3\}$ over.

Kies nu $C=1$. De boog $A\to C$ verwijdert 1 uit A, zodat $A=2$ overblijft. Als je B ten opzichte van A herziet, wordt $B=3$ afgedwongen. D verschilt van C en A, dus $D=3$. E verschilt van D en kan geen 1 zijn, dus $E=2$. De domeinverkleiningen hebben zich verder verspreid dan de directe buren van de oorspronkelijke beslissing.

Boogconsistentie handhaven (MAC) past deze inferentie na elke zoekbeslissing toe. Als je uitgaat van boogconsistente domeinen en $X=x$ vastlegt, is een wachtrij nodig met inkomende bogen vanuit de aangrenzende variabelen zonder waarde. Verwijderde domeinwaarden moeten worden hersteld als de zoekmethode de tak ongedaan maakt.

Interpreteer het resultaat en de kosten

Een driehoek met domeinen {rood, blauw} en ongelijkheden op alle drie de verbindingen blijft boogconsistent, maar heeft geen oplossing. Elke verbinding heeft afzonderlijk ondersteunende waarden, maar de drie keuzes kunnen niet samengaan.

Met $c$ binaire constraints en maximale domeingrootte $d$ kost AC-3 $O(c{d}^3)$ tijd: een boogherziening controleert maximaal $d^2$ paren en elke boog kan maximaal $d$ ronden nodig hebben als de eindknoop waarden verliest. MAC kost meer per zoekknoop dan voorwaartse controle, vaak in ruil voor een veel kleinere zoekboom.

Afzonderlijke paarsgewijze ondersteunende waarden kunnen een tegenspraak binnen een groep verhullen. Sterkere consistentie en gespecialiseerde globale propagatie onderzoeken combinaties die boogconsistentie mist, terwijl numerieke grenzen grote domeinen kunnen samenvatten in bruikbare intervallen.

Breid waardetoekenningen uit naar een andere variabele

Padconsistentie onderzoekt drietallen. Elke consistente waardetoekenning aan twee variabelen moet kunnen worden uitgebreid naar een derde met een waarde die met beide overeenkomt. In een driehoek die rood of blauw wordt gekleurd, laten X rood en Y blauw geen waarde over voor Z. Padconsistentie verwijdert dat toegestane paar en brengt uiteindelijk de onoplosbaarheid aan het licht. Ze kan tupels uit relaties verwijderen en doet dus meer dan afzonderlijke domeinwaarden verwijderen.

k-consistentie vereist dat elke consistente waardetoekenning aan willekeurige $k-1$ variabelen kan worden uitgebreid naar een willekeurige extra variabele. Voor binaire CSP's komt 1-consistentie overeen met knoopconsistentie, 2-consistentie met boogconsistentie en 3-consistentie met padconsistentie. Sterke k-consistentie omvat elk niveau van 1 tot en met k. Bij sterke n-consistentie voor n variabelen en niet-lege domeinen kan elke consistente gedeeltelijke waardetoekenning zonder terugkeren worden uitgebreid tot een oplossing. Het vaststellen van deze eigenschap heeft in het slechtste geval exponentiële tijd- en geheugenkosten.

Tel waarden in Alldiff

Alldiff vereist verschillende waarden voor alle variabelen in het variabelenbereik. Als een groep van m variabelen slechts n verschillende mogelijke waarden heeft en $m>n$, kan geen waardetoekenning eraan voldoen.

Voor drie cellen met domein $\{4,7\}$ zijn paarsgewijze ongelijkheden boogconsistent: elke 4 heeft ondersteuning van 7 in elke aangrenzende cel en elke 7 heeft ondersteuning van 4. Toch voldoet de groep niet aan de telregel, omdat drie verschillende waarden nodig zijn en er maar twee bestaan.

Als twee cellen allebei domein $\{4,7\}$ hebben, moeten ze samen 4 en 7 gebruiken. Die waarden kunnen uit elke andere cel in dezelfde rij worden verwijderd. Dit redeneren met een naakt paar gebruikt een deelverzameling van het volledige variabelenbereik van Alldiff. Een eenvoudige globale propagatiemethode kan ook herhaaldelijk variabelen met één waarde verwerken, hun waarden elders verwijderen en controleren of er te weinig verschillende waarden overblijven. Sterkere propagatiemethoden herkennen ook beperkte deelverzamelingen.

Scherp numerieke grenzen aan

Grenspropagatie slaat een domein op via het minimum en maximum. Grensconsistentie vereist dat elk eindpunt voor elke relevante constraint een uitbreiding heeft die eraan voldoet; ze controleert niet elke tussenliggende waarde.

Laat voor twee bussen die 100 mensen vervoeren $B_1\in [0,50]$ en $B_2\in [0,70]$ gelden, met $B_1+B_2=100$. De tweede bus vervoert hoogstens 70 mensen, wat $B_1\ge 30$ afdwingt. De eerste vervoert hoogstens 50 mensen, wat $B_2\ge 50$ afdwingt. De aangescherpte intervallen zijn $[30,50]$ en $[50,70]$.

Voor Voorbereiden, Analyseren en Rapporteren, die in die volgorde 20, 40 en 30 minuten duren, geeft een uiterste tijd van 120 minuten de laatste begintijden 30, 50 en 90. Niet-negatieve begintijden geven de vroegste begintijden 0, 20 en 60. Door voorwaarts en achterwaarts te propageren krijg je deze intervallen voordat een begintijd wordt gekozen.

Kies een bruikbare sterkte

Elke Sudokucel heeft 20 verschillende aangrenzende cellen: 8 in de rij, 8 in de kolom en 4 extra cellen in het blok. Over 81 cellen geeft dat $81\times 20\mathrm{/}2=810$ verschillende ongelijke paren. Globale constraints behouden dezelfde oplossingen als die paren, maar kunnen naakte paren en een tekort aan waarden eerder zichtbaar maken. Sterkere inferentie kost meer per ronde; praktische oplossers wegen die kosten af tegen het zoekwerk dat ze besparen en combineren vaak boogconsistentie met gespecialiseerde globale propagatie en grenspropagatie.

Lokaal zoeken begint met een waarde voor elke variabele, ook als sommige constraints worden geschonden. De minimaleconflictenheuristiek herstelt deze volledige waardetoekenning door één variabele in een geschonden constraint een waarde met zo weinig mogelijk conflicten te geven.

Kies een herstelstap

1. Maak een volledige waardetoekenning, willekeurig of gulzig.
2. Als geen constraint wordt geschonden, geef de oplossing dan terug.
3. Kies willekeurig een variabele die bij een geschonden constraint betrokken is.
4. Beoordeel elke domeinwaarde van die variabele ten opzichte van de andere variabelen, die vast blijven.
5. Kies een waarde met de minste conflicten, kies willekeurig bij gelijke stand en herhaal tot een oplossing is gevonden of een staplimiet is bereikt.

Een variabele in een geschonden constraint is betrokken bij minstens één geschonden constraint. Het is niet noodzakelijk de variabele met het grootste aantal schendingen. Willekeurig kiezen tussen zulke variabelen en tussen gelijke waarden helpt een vaste herhaalde reeks te voorkomen.

Herstel een bord met 4 dames

Gebruik één dame per kolom, met rijvariabelen $Q_1,Q_2,Q_3,Q_4$. Een paar conflicteert als de rijen gelijk zijn of als het verschil tussen de rijen gelijk is aan het verschil tussen de kolommen. Begin met $(2,4,2,3)$. Kolommen 1 en 3 delen rij 2; de dames in kolommen 3 en 4 vallen elkaar diagonaal aan. De variabelen in geschonden constraints zijn Q1, Q3 en Q4.

Kies Q3 en beoordeel de rijen terwijl Q1, Q2 en Q4 vast blijven:

Rij 1 levert $(2,4,1,3)$ op, een oplossing. Als in plaats daarvan Q1 was gekozen, waren de aantallen voor rijen 1–4 gelijk aan 0, 1, 2 en 2. Verplaatsing naar rij 1 geeft $(1,4,2,3)$, waarbij het diagonale conflict Q3–Q4 overblijft. Een lokaal beste herstelstap kan dus leiden tot een herstelproces dat nog niet klaar is.

Tel de constraints waarbij de gekozen variabele betrokken is. Alle schendingen op elk resulterend bord tellen geeft dezelfde ordening, omdat niet-betrokken constraints bij elke mogelijke waarde een constante bijdrage leveren. Het kost alleen meer werk. Gebruik één consistente definitie van een conflict wanneer je mogelijkheden vergelijkt.

Herstel een bestaand rooster

Als een trainer niet meer beschikbaar is, vormt het huidige rooster al een volledige waardetoekenning. De minimaleconflictenheuristiek kan daar beginnen en sessies verplaatsen tot aan de nieuwe en bestaande constraints wordt voldaan. Een kleine wijziging vereist vaak weinig herstelstappen, hoewel één stap elders nieuwe conflicten kan veroorzaken. Als behoud van het oude plan belangrijk is, koppel dan expliciete kosten aan het veranderen van een waardetoekenning; alleen het aantal schendingen minimaliseren beperkt de verstoring niet tot een minimum.

Bij experimenten met een goede beginwaardetoekenning waren zelfs voor een miljoen dames relatief weinig herstelstappen nodig. Op grotere borden kost elke stap nog steeds meer. De minimaleconflictenheuristiek is ook gebruikt voor de planning van Hubble-waarnemingen. Naar verluidt daalde de tijd om een week waarnemingen te plannen van ongeveer drie weken tot ongeveer 10 minuten.

Interpreteer het zoekgedrag

Veel families van willekeurige CSP's veranderen van overwegend oplosbaar naar overwegend onoplosbaar naarmate de verhouding tussen constraints en variabelen stijgt. Dicht bij die overgang is bepalen hoe keuzes elkaar beïnvloeden vaak het moeilijkst. Problemen met weinig beperkende constraints kunnen veel gemakkelijk bereikbare oplossingen hebben. Sterk beperkte onvervulbare problemen kunnen door volledige oplossers die propagatie gebruiken snel worden afgewezen.

Het bereiken van een staplimiet voor de minimaleconflictenheuristiek betekent dat in die uitvoering geen oplossing is gevonden. Het probleem kan nog steeds oplosbaar zijn. De praktische kracht van de methode komt voort uit efficiënte herstelstappen, waaronder stappen met een gelijke score, ook al vormen oplossingen een heel klein deel van alle mogelijke waardetoekenningen.

Een zoekmethode die oplossingen herstelt kan stoppen met verbeteren terwijl er nog conflicten zijn. Om verder te gaan heeft de oplosser een manier nodig om door toestanden met gelijke scores te bewegen of te veranderen welke stappen de moeite waard lijken. Ook het vereiste resultaat telt: een snelle haalbare aanpassing en een bewijs van onoplosbaarheid vereisen verschillende methoden.

Beweeg over een plateau

Een lokaal minimum heeft schendingen, maar geen stap die één variabele verandert en het aantal schendingen verlaagt. Een plateau is een samenhangend gebied van waardetoekenningen met dezelfde score. Stappen die alleen omlaag gaan kunnen vastlopen; een zijwaartse stap verandert de toestand zonder de score te verlagen.

Bij 4 dames heeft $(1,4,2,3)$ één conflict tussen Q3 en Q4. Als de andere dames vast blijven, zijn de aantallen van Q3 voor rijen 1–4 gelijk aan 1, 1, 3 en 2; die van Q4 zijn 2, 2, 1 en 2. Geen van beide variabelen heeft een verbeterende stap.

Q3 naar rij 1 verplaatsen geeft $(1,4,1,3)$, nog steeds met één conflict: nu delen Q1 en Q3 een rij. In deze nieuwe toestand zijn de aantallen van Q1 gelijk aan 1, 0, 3 en 1. Q1 naar rij 2 verplaatsen levert $(2,4,1,3)$ op en neemt het conflict weg. De zijwaartse stap veranderde welke verbeterende stappen beschikbaar waren.

Houd het zoeken gaande

Een taboelijst is een kortetermijngeheugen. Ze ontmoedigt onmiddellijke terugkeer naar een toestand die net is verlaten. Een herstart onderzoekt een ander gebied, terwijl gesimuleerd afkoelen binnen de huidige uitvoering een gebied met meer conflicten kan doorkruisen.

Geef bij constraintweging elk gewicht aanvankelijk de waarde 1 en beoordeel een toestand met de som van de gewichten van de geschonden constraints. Kies een wijziging die deze gewogen score verlaagt en verhoog daarna de gewichten van constraints die geschonden blijven. Herhaalde mislukkingen worden duurder, waardoor het zoeklandschap van vorm verandert. Een gewogen score van nul betekent nog steeds dat aan elke harde constraint met een positief gewicht is voldaan.

Kies het bewijs dat je nodig hebt

Lokaal zoeken is onvolledig: het kan een bestaande oplossing missen en een eindige mislukte uitvoering laat onbeslist of het probleem onoplosbaar is. Backtracking met propagatie op eindige domeinen is volledig: uiteindelijk vindt de methode een oplossing of onderzoekt ze alle mogelijke uitbreidingen.

Gebruik lokaal zoeken als een groot probleem met weinig beperkende constraints één haalbare waardetoekenning of een snelle aanpassing nodig heeft. Backtracking met MRV en MAC is een sterke keuze voor sterk beperkte puzzels en wanneer de taak een uitspraak over onoplosbaarheid vereist. De looptijd hangt nog steeds af van het concrete probleem; deze methodekeuzes zijn gebaseerd op hun garanties.

Het workshoprooster heeft de unieke oplossing $A=2,B=3,C=1,D=3,E=2$. Toevoeging van $C\mathrm{\ne }1$ sluit die uit. De minimaleconflictenheuristiek kan aanpassingen blijven proberen tot de limiet, maar alleen een volledige zoekmethode die de resterende gevallen uitput, stelt vast dat de organisator een eis moet veranderen, bijvoorbeeld door een extra tijdvak toe te voegen.

Een constraintgraaf kan kleinere problemen binnen een groot probleem zichtbaar maken. Onafhankelijke componenten kunnen afzonderlijk worden opgelost en voor acyclische componenten bestaat een bijzonder efficiënt algoritme met een achterwaartse doorloop om waarden te verwijderen en een voorwaartse doorloop om waarden toe te kennen.

Splits niet-verbonden componenten

Een samenhangende component is onafhankelijk als geen constraint haar variabelen met een andere component verbindt. Los elke component op en combineer daarna één oplossing van elke component. Als een component onvervulbaar is, is het volledige CSP onvervulbaar. Op de kaart van Australië staat Tasmanië los van het vasteland.

Met n variabelen verdeeld in onafhankelijke groepen van grootte c kost het vinden van één volledige waardetoekenning werk in de orde van $O((n\mathrm{/}c)d^c)$ in plaats van $O(d^n)$. Voor 60 variabelen met elk twee mogelijke waarden, verdeeld in drie groepen van 20, bekijken afzonderlijke uitputtende zoekprocessen maximaal $3\times 2^{20}=\mathrm{3.145.728}$ waardetoekenningen in plaats van ongeveer $\mathrm{1,15}\times {10}^{18}$. Om elke gecombineerde oplossing op te sommen, zouden de combinaties nog steeds moeten worden opgesomd; de besparing betreft het oplossen van de deelproblemen.

Orden een boom vanaf de wortel

Een binair CSP heeft een boomstructuur als de constraintgraaf acyclisch is. Een samenhangende boom heeft één pad tussen elk paar variabelen; een bos bevat afzonderlijke bomen. Pas eerst unaire beperkingen toe. Kies een willekeurige wortel en orden variabelen zo dat elke ouderknoop vóór zijn kindknopen komt.

Gerichte boogconsistentie vereist in deze volgorde dat elke eerdere variabele ondersteuning heeft in elke latere aangrenzende variabele. In een boom zijn die latere aangrenzende variabelen de kindknopen. De richting van ondersteuning loopt van ouderknoop naar kindknoop, ook al verwerkt het algoritme kindknopen vóór ouderknopen.

Verwijder waarden achterwaarts en ken waarden voorwaarts toe

1. Lees de volgorde achterwaarts, zonder de wortel. Herzie voor elke kindknoop de boog van de ouderknoop naar die kindknoop. Verwijder waarden zonder ondersteuning uit het domein van de ouderknoop.
2. Als een domein leeg raakt, meld dan dat er geen oplossing is.
3. Lees de volgorde voorwaarts. Kies een willekeurige overgebleven waarde voor de wortel en geef daarna elke kindknoop een waarde die verenigbaar is met de toegekende waarde van de ouderknoop.

De nakomelingen van de kindknoop zijn al verwerkt wanneer de ouderknoop wordt herzien. Een overgebleven waarde van de ouderknoop heeft dus ondersteuning in elke kindknoop en elke waarde van een kindknoop heeft al ondersteuning verder naar beneden. Verschillende kindtakken zijn niet door verbindingen met elkaar verbonden, zodat die ondersteunende waarden onafhankelijk kunnen worden gekozen. Daarom hoeft de voorwaartse doorloop niet terug te keren.

Volg de workshopboom

Leg $C=1$ vast in het workshoprooster en verwijder 1 uit de domeinen van de andere workshops. De resterende graaf is het pad B–A–D–E, met domeinen $\{2,3\}$ en constraints $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Kies wortel A en volgorde A, B, D, E. De achterwaartse doorloop herziet $D\to E$ en daarna $A\to D$, zonder wijzigingen. Ten slotte verwijdert $A\to B$ de waarde 3 uit A omdat B geen grotere waarde heeft. Voorwaarts waarden toekennen geeft $A=2,B=3,D=3,E=2$. Als je $C=1$ terugplaatst, krijg je het volledige rooster.

Voor n variabelen met maximale domeingrootte d herziet de achterwaartse doorloop $n-1$ bogen met elk maximaal $O(d^2)$ kosten, wat $O(n{d}^2)$ tijd oplevert. De garantie hangt af van de afwezigheid van cycli. Een cyclus kan afzonderlijke kindtakken verbinden en de onafhankelijkheid tenietdoen die deze lokale keuzes veilig maakte.

Een graaf met enkele cycli kan toch voldoende op een boom lijken om efficiënt te worden opgelost. Conditioneren op een cyclusdoorbrekende knopenverzameling kent eerst waarden toe aan geselecteerde variabelen; boomdecompositie groepeert variabelen in overlappende delen. Beide geven de resterende afstemming een boomstructuur.

Conditioneer op een cyclusdoorbrekende knopenverzameling

Een cyclusdoorbrekende knopenverzameling is een verzameling variabelen waarvan de verwijdering een boom of bos overlaat. Controleer elke resterende cyclus, niet alleen de duidelijkst zichtbare. Voor de kaart van Australië laat het verwijderen van SA het pad WA–NT–Q–NSW–V plus de geïsoleerde knoop T over. Voor de workshopgraaf laat het verwijderen van C het pad B–A–D–E over.

Voor elke waardetoekenning aan de cyclusdoorbrekende knopenverzameling die aan de constraints binnen die verzameling voldoet:

1. Verwijder onverenigbare waarden uit de resterende domeinen.
2. Los elke resterende boom op door achterwaarts waarden te verwijderen en voorwaarts waarden toe te kennen.
3. Als alle bomen een oplossing hebben, combineer hun waardetoekenningen dan met de waarden van de knopenverzameling. Probeer anders een andere waardetoekenning aan die verzameling.

In het workshopprobleem laat $C=1$ een oplosbare boom over. Bij $C=2$ moeten A en B uit $\{1,3\}$ komen en dwingt $A<B$ de waarden $A=1,B=3$ af. D moet zowel van A als van C verschillen, wat $D=3$ geeft. E kan geen 1 zijn en moet van C en D verschillen, waardoor geen waarde overblijft. Bij $C=3$ moeten A en B gelijk zijn aan 1 en 2; D moet dan 2 zijn, waardoor opnieuw geen waarde voor E overblijft.

Bij een cyclusdoorbrekende knopenverzameling van grootte c zijn er maximaal $d^c$ waardetoekenningen, elk gevolgd door een boomprobleem met kosten $O((n-c)d^2)$. Het totaal is $O(d^c(n-c)d^2)$. Een kleine c maakt dit bruikbaar; de kosten blijven exponentieel in c. Het vinden van een kleinste cyclusdoorbrekende knopenverzameling is NP-moeilijk, maar ook een geldige verzameling die niet de kleinste is, geeft een correcte procedure.

Verbind overlappende zakken

Een boomdecompositie rangschikt verzamelingen variabelen, zakken genoemd, in een boom. Die moet aan drie voorwaarden voldoen:

• Elke variabele komt in een zak voor.
• Het variabelenbereik van elke constraint past binnen minstens één zak.
• De zakken die een bepaalde variabele bevatten, vormen een samenhangend deel van de zakkenboom.

De derde regel is de lopende-intersectie-eigenschap. Als X aan beide uiteinden van een pad van zakken voorkomt, moet X op het hele pad voorkomen. Anders kunnen ver uit elkaar liggende zakken inconsistente waarden voor X kiezen zonder een tussenliggende controle op overeenstemming.

De lokaal geldige waardetoekenningen van elke zak worden waarden van een megavariabele. Aangrenzende zakken moeten overeenkomen op gedeelde variabelen. De resulterende boom stemt de lokale oplossingen op elkaar af. Voor een driehoek X–Y–Z–X plus verbinding Z–W dekken de zakken $\{X,Y,Z\}$ en $\{Z,W\}$ elke verbinding en komen ze overeen op Z.

De boombreedte van de decompositie is de grootste zakgrootte min 1. De boombreedte van een graaf is het minimum over geldige decomposities. Voor breedte w is de gebruikelijke CSP-grens $O(n{d}^{w+1})$. Een vaste begrensde breedte houdt de exponent onder controle.

Verwijder waardesymmetrie

Als kleurnamen geen bijzondere betekenis hebben, blijft de geldigheid behouden als je rood, groen en blauw verwisselt. De zes oplossingen voor het Australische vasteland zijn zes hernoemingen van één patroon. Door de volgorde NT vóór SA vóór WA vast te leggen in de kleurvolgorde rood, groen, blauw, behoud je één vertegenwoordiger. Zo'n symmetriedoorbrekende constraint is alleen geldig als de hernoeming de oorspronkelijke regels behoudt. Een regel die vereist dat een bepaalde regio rood is, maakt die kleur bijzonder en verandert welke verwisselingen symmetrieën blijven.