Místní konzistence

v omezení spokojenosti, místní konzistence podmínky jsou vlastnosti problémy s uspokojením omezení související s konzistence podmnožin proměnných nebo omezení. Mohou být použity ke zmenšení prostoru hledání a snazšímu řešení problému. Využívají se různé druhy místních podmínek konzistence, včetně konzistence uzlů, konzistence oblouku, a konzistence cesty.

Každou podmínku místní konzistence lze vynutit transformací, která změní problém, aniž by se změnila jeho řešení. Taková transformace se nazývá šíření omezení. Propagace omezení funguje snížením domén proměnných, posílením omezení nebo vytvořením nových. To vede ke zmenšení prostoru pro vyhledávání, což usnadňuje řešení problému pomocí některých algoritmů. Šíření omezení lze také použít jako kontrolu neuspokojivosti, obecně neúplnou, ale v některých konkrétních případech úplnou.

Podmínky místní konzistence lze seskupit do různých tříd. Původní podmínky místní konzistence vyžadují, aby bylo možné každé konzistentní přiřazení konzistentně rozšířit na jinou proměnnou. Směrová konzistence vyžaduje pouze splnění této podmínky, když je druhá proměnná podle zadaného pořadí vyšší než ty v přiřazení. Relační konzistence zahrnuje rozšíření více než jedné proměnné, ale toto rozšíření je vyžadováno pouze pro splnění daného omezení nebo sady omezení.

Předpoklady

V tomto článku a problém spokojenosti s omezením je definována jako sada proměnných, sada domén a sada omezení. Proměnné a domény jsou spojeny: doména proměnné obsahuje všechny hodnoty, které proměnná může nabývat. Omezení se skládá ze sledu proměnných, které se nazývají jeho obor, a sady jejich hodnocení, což jsou hodnocení uspokojující omezení.

Předpokládá se, že problémy s uspokojením omezení uvedené v tomto článku jsou ve zvláštní formě. Problém je v normalizovaná forma, resp pravidelná forma, pokud je každá sekvence proměnných rozsahem maximálně jednoho omezení nebo přesně jednoho omezení. Předpoklad pravidelnosti provedený pouze pro binární omezení vede k standardizovaný formulář. Tyto podmínky lze vždy vynutit kombinací všech omezení přes posloupnost proměnných do jedné a / nebo přidáním omezení, které je splněno všemi hodnotami posloupnosti proměnných.

Na obrázcích použitých v tomto článku nedostatek vazeb mezi dvěma proměnnými naznačuje, že mezi těmito dvěma proměnnými neexistuje žádné omezení nebo omezení splněné všemi hodnotami.^{[je zapotřebí objasnění ]}

Všechny „standardní“ podmínky místní konzistence vyžadují, aby bylo možné všechna konzistentní částečná hodnocení rozšířit na jinou proměnnou tak, aby bylo výsledné přiřazení konzistentní. Částečné vyhodnocení je konzistentní, pokud splňuje všechna omezení, jejichž rozsah je podmnožinou přiřazených proměnných.^{[je zapotřebí objasnění ]}

Konzistence uzlu

Konzistence uzlů vyžaduje, aby každé unární omezení proměnné bylo splněno všemi hodnotami v doméně proměnné a naopak. Tuto podmínku lze triviálně vynutit snížením domény každé proměnné na hodnoty, které splňují všechna unární omezení dané proměnné. Výsledkem je, že unární omezení lze zanedbávat a předpokládat, že budou začleněna do domén.

Například vzhledem k proměnné ${ displaystyle V}$ s doménou ${ displaystyle left {1,2,3,4 right }}$ a omezení ${ displaystyle V leq 3}$ , konzistence uzlu by omezila doménu na ${ displaystyle left {1,2,3 right }}$ a omezení by pak mohlo být zahozeno. Tento krok předběžného zpracování zjednodušuje pozdější fáze.

Konzistence oblouku

x2 je oblouk konzistentní s x3, ale ne s x1, protože hodnota x2 = 1 neodpovídá žádné hodnotě pro x1.

Proměnná problému s omezením uspokojení je obloukově konzistentní s jinou, pokud každá z jejích přípustných hodnot odpovídá určité přípustné hodnotě druhé proměnné. Formálně proměnná ${ displaystyle x_ {i}}$ je oblouk konzistentní s jinou proměnnou ${ displaystyle x_ {j}}$ pokud pro každou hodnotu ${ displaystyle a}$ v doméně ${ displaystyle x_ {i}}$ existuje hodnota ${ displaystyle b}$ v doméně ${ displaystyle x_ {j}}$ takhle ${ displaystyle (a, b)}$ splňuje binární omezení mezi ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ . Problémem je oblouk konzistentní, pokud je každá proměnná oblouk konzistentní se všemi ostatními.

Zvažte například omezení ${ displaystyle x$ kde proměnné se pohybují přes doménu 1 až 3. Protože ${ displaystyle x}$ nikdy nemůže být 3, není oblouk od 3 do hodnoty v ${ displaystyle y}$ takže je bezpečné jej odstranit. Rovněž, ${ displaystyle y}$ nikdy nemůže být 1, takže neexistuje žádný oblouk, proto jej lze odstranit.

Konzistenci oblouku lze také definovat ve vztahu ke konkrétnímu binárnímu omezení: binární omezení je konzistentní s obloukem, pokud každá hodnota jedné proměnné má hodnotu druhé proměnné tak, aby vyhovovala omezení. Tato definice konzistence oblouku je podobná výše uvedené, ale je dána specifickým omezením. Tento rozdíl je obzvláště relevantní pro nenormalizované problémy, kde by výše uvedená definice brala v úvahu všechna omezení mezi dvěma proměnnými, zatímco tato bere v úvahu pouze konkrétní.

Konzistence oblouku vynucená odstraněním 1 jako hodnoty pro x2. Výsledkem je, že x3 již není konzistentní s obloukem s x2, protože x3 = 2 neodpovídá hodnotě pro x2.

Pokud proměnná není oblouk konzistentní s jinou, lze ji provést odstraněním některých hodnot z její domény. Toto je forma šíření omezení, která vynucuje konzistenci oblouku: odstraní z domény proměnné každou hodnotu, která neodpovídá hodnotě jiné proměnné. Tato transformace udržuje řešení problémů, protože odstraněné hodnoty stejně nejsou v žádném řešení.

Díky šíření omezení může být celý problémový oblouk konzistentní opakováním tohoto odstranění pro všechny páry proměnných. Tento proces možná bude muset uvažovat o dané dvojici proměnných více než jednou. Odebrání hodnot z domény proměnné může způsobit, že ostatní proměnné již nebudou s ní v souladu. Například pokud ${ displaystyle x_ {3}}$ je oblouk v souladu s ${ displaystyle x_ {2}}$ ale algoritmus zmenšuje doménu ${ displaystyle x_ {2}}$ , konzistence oblouku ${ displaystyle x_ {3}}$ s ${ displaystyle x_ {2}}$ již neplatí a musí být znovu vynuceno.

Zjednodušující algoritmus by cykloval přes páry proměnných, vynucoval konzistenci oblouku a opakoval by cyklus, dokud by se během celého cyklu nezměnily žádné domény. The Algoritmus AC-3 vylepšuje tento algoritmus tím, že ignoruje omezení, která nebyla od poslední analýzy změněna. Zejména to funguje na množině omezení, která zpočátku obsahuje všechna; v každém kroku to vyžaduje omezení a vynucuje konzistenci oblouku; pokud tato operace mohla způsobit porušení konzistence oblouku nad jiným omezením, umístí ji zpět do sady omezení k analýze. Tímto způsobem, jakmile je u omezení vynucena konzistence oblouku, toto omezení se znovu nepovažuje, pokud se nezmění doména jedné z jeho proměnných.

Konzistence cesty

x1 a x2 nejsou konzistentní s cestou x3. Lze je zajistit konzistentní cestou odstraněním modrých hodnot z R12.

Konzistence cesty je vlastnost podobná konzistenci oblouku, ale uvažuje dvojice proměnných místo pouze jedné. Dvojice proměnných je konzistentní s cestou s třetí proměnnou, pokud lze každé konzistentní vyhodnocení páru rozšířit na druhou proměnnou tak, že všechny binární omezení jsou splněna. Formálně, ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ jsou cesty v souladu s ${ displaystyle x_ {k}}$ pokud pro každou dvojici hodnot ${ displaystyle (a, b)}$ který splňuje binární omezení mezi ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ , existuje hodnota ${ displaystyle c}$ v doméně ${ displaystyle x_ {k}}$ takhle ${ displaystyle (a, c)}$ a ${ displaystyle (b, c)}$ uspokojit omezení mezi ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {k}}$ a mezi ${ displaystyle x_ {j}}$ a ${ displaystyle x_ {k}}$ , resp.

Forma šíření omezení, která vynucuje konzistenci cest, funguje odstraněním uspokojivého přiřazení z omezení. Opravdu lze konzistenci cesty vynutit odstraněním všech hodnocení, která nelze rozšířit na jinou proměnnou, z binárního omezení. Pokud jde o konzistenci oblouku, toto odstranění bude možná muset binární omezení zvážit více než jednou. Pokud jde o konzistenci oblouku, výsledný problém má stejná řešení jako ten původní, protože odstraněné hodnoty nejsou v žádném řešení.

Dvě proměnné, které nejsou v omezení, lze považovat za související virtuální omezení, které umožňuje jakoukoli možnou dvojici hodnot, představovanou modrými okraji na tomto obrázku.

Vynucení konzistence cesty x1 a x2 pomocí x3 odstraní okraj nahoře. Hodnoty x1 a x2 již nejsou volné, ale souvisí s novým skutečným omezením.

Forma šíření omezení, která vynucuje konzistenci cest, může zavést nová omezení. Když dvě proměnné nesouvisí s binárním omezením, jsou ve skutečnosti spojeny s omezením umožňujícím jakoukoli dvojici hodnot. Některé páry hodnot však mohou být odstraněny šířením omezení. Výsledné omezení již není splněno všemi páry hodnot. Proto již není virtuální, triviální omezení.

Název „konzistence cesty“ pochází z původní definice, která zahrnovala spíše dvojici proměnných a cestu mezi nimi, než dvojici a jedinou proměnnou. Zatímco dvě definice se liší pro jednu dvojici proměnných, jsou ekvivalentní, když se odkazuje na celý problém.

Zobecnění

Konzistenci oblouku a cesty lze zobecnit na nebinární omezení pomocí n-tice proměnných místo jedné nebo dvojice. Tuple of ${ displaystyle i-1}$ proměnné je ${ displaystyle i}$ -konzistentní s jinou proměnnou, pokud je každé konzistentní hodnocení ${ displaystyle i-1}$ proměnné lze při zachování konzistence rozšířit o hodnotu druhé proměnné. Tato definice se zjevným způsobem vztahuje na celé problémy. Silný ${ displaystyle i}$ -konzistence je ${ displaystyle j}$ -konzistence pro všechny ${ displaystyle j leq i}$ .

Zvláštní případ konzistence 2 se shoduje s konzistencí oblouku (všechny problémy se v tomto článku považují za konzistentní s uzly). Na druhou stranu, 3-konzistence se shoduje s konzistencí cesty, pouze pokud jsou všechna omezení binární, protože konzistence cesty nezahrnuje ternární omezení, zatímco 3-konzistence ano.

Další způsob zobecnění konzistence oblouku je konzistence hyperoblouku nebo zobecněná konzistence oblouku, který vyžaduje rozšiřitelnost jedné proměnné, aby vyhověl omezení. Jmenovitě je proměnná hyperoblouk konzistentní s omezením, pokud lze každou hodnotu proměnné rozšířit na ostatní proměnné omezení takovým způsobem, že je omezení splněno.

Důslednost a uspokojivost

Tato instance je konzistentní s obloukem a neobsahuje žádnou prázdnou doménu, ale nemá žádné řešení. Modré čáry označují přiřazení vynucená volbou x1 = 1.

Propagace omezení (vynucení formy místní konzistence) může způsobit prázdnou doménu nebo neuspokojivý omezení. V tomto případě problém nemá řešení. Konverzace není obecně platná: nekonzistentní instance může být konzistentní s obloukem nebo konzistentní s cestou, aniž by měla prázdnou doménu nebo nevyhovující omezení.

Místní konzistence je ve skutečnosti pouze relativní ke konzistenci skupin proměnných. Například konzistence oblouku zaručuje, že každé konzistentní vyhodnocení proměnné lze konzistentně rozšířit na jinou proměnnou. Když je však jedna hodnota proměnné rozšířena na dvě další proměnné, neexistuje žádná záruka, že tyto dvě hodnoty jsou navzájem konzistentní. Například, ${ displaystyle x_ {1} = 1}$ může být v souladu s ${ displaystyle x_ {2} = 1}$ a s ${ displaystyle x_ {3} = 1}$ , ale tato dvě hodnocení nemusí být navzájem v souladu.

Šíření omezení však lze v některých případech použít k prokázání uspokojivosti. Sada binárních omezení, která jsou konzistentní s obloukem a nemá prázdnou doménu, může být nekonzistentní, pouze pokud síť omezení obsahuje cykly. Ve skutečnosti, pokud jsou omezení binární a tvoří acyklický graf, lze hodnoty vždy šířit napříč omezeními: pro každou hodnotu proměnné mají všechny proměnné v omezení s hodnotou vyhovující tomuto omezení. Výsledkem je, že řešení lze najít iterativním výběrem nepřiřazené proměnné a rekurzivním šířením napříč omezeními. Tento algoritmus se nikdy nepokouší přiřadit hodnotu proměnné, která je již přiřazena, protože by to znamenalo existenci cyklů v síti omezení.

Podobná podmínka platí pro konzistenci cesty. Zvláštní případy, ve kterých lze dosáhnout uspokojivosti vynucením konzistence oblouku a konzistence cesty, jsou následující.

vynucení konzistence oblouku stanoví uspokojivost problémů vytvořených z binárních omezení bez č cykly (A strom binárních omezení);
vynucení konzistence cesty zajišťuje uspokojivost pro binární omezení (možná s cykly) s binárními doménami;
prosazování silné ${ displaystyle n}$ konzistence stanoví uspokojivost problémů obsahujících ${ displaystyle n}$ proměnné.

Speciální případy

Některé definice nebo výsledky relativní konzistence platí pouze ve zvláštních případech.

Když se domény skládají z celá čísla, lze definovat vázanou konzistenci. Tato forma konzistence je založena na konzistenci extrémních hodnot domén, tj. Minimální a maximální hodnoty, které může proměnná nabývat.

Když jsou omezení algebraický nebo Booleovský, konzistence oblouku je ekvivalentní přidání nového omezení nebo syntaktické úpravy starého, a to lze provést vhodným složením omezení.

Specializovaná omezení

Některé druhy omezení se běžně používají. Například se často používá omezení, že některé proměnné se liší. Efektivní specializované algoritmy pro vynucení konzistence oblouku u takových omezení existují.

Omezení, které vynucuje, aby se různé proměnné lišily, je obvykle zapsáno ${ displaystyle mathop { rm {alldifferent}} (x_ {1}, ldots, x_ {n})}$ nebo alldifferent ([X1, ..., Xn]). Toto omezení je ekvivalentní nerovnosti všech párů různých proměnných, tj. ${ displaystyle x_ {i} not = x_ {j}}$ pro každého ${ displaystyle i not = j}$ . Když je doména proměnné snížena na jednu hodnotu, lze tuto hodnotu odebrat ze všech ostatních domén šířením omezení při vynucování konzistence oblouku. Použití specializovaného omezení umožňuje využívat vlastnosti, které neplatí pro jednotlivé binární soubory nerovnosti.

První vlastností je, že celkový počet prvků v doménách všech proměnných musí být alespoň počet proměnných. Přesněji po vynucení konzistence oblouku nesmí počet nepřiřazených proměnných překročit počet hodnot ve sjednocení jejich domén. Jinak nelze omezení splnit. Tuto podmínku lze snadno zkontrolovat na základě omezení v úplně jiný forma, ale neodpovídá obloukové konzistenci sítě nerovností. Druhá vlastnost singlu úplně jiný omezení spočívá v tom, že konzistenci hyperoblouku lze účinně kontrolovat pomocí a bipartitní shoda algoritmus. Zejména je graf sestaven s proměnnými a hodnotami jako dvěma sadami uzlů a je na něm spuštěn specializovaný bipartitní algoritmus porovnávání grafů, který kontroluje existenci takového porovnávání.

Jiný druh omezení, který se běžně používá, je kumulativní jeden. Byl zaveden pro problémy plánování a umístění. Jako příklad, kumulativní ([S1, ..., Sm], [D1, ..., Dm], [R1, ..., Rm], L) lze použít k formalizaci stavu, ve kterém jsou m aktivity, každá s časem zahájení si, doba trvání di a použít částku ri zdroje. Omezení uvádí, že celkové dostupné množství zdrojů je L. Specializované techniky šíření omezení pro kumulativní omezení existují; používají se různé techniky podle toho, které variabilní domény jsou již redukovány na jednu hodnotu.

Třetí specializované omezení, které se používá v logické programování omezení je živel jeden. V logickém programování omezení jsou seznamy povoleny jako hodnoty proměnných. Omezení prvek (I, L, X) je spokojen, pokud L je seznam a X je Já-tý prvek tohoto seznamu. Pro tato omezení existují pravidla šíření speciálních omezení. Jako příklad, pokud L a Já jsou redukovány na doménu s jednou hodnotou, což je jedinečná hodnota pro X lze určit. Obecněji řečeno, nemožné hodnoty X lze odvodit z domény ${ displaystyle I}$ a naopak.

Směrová konzistence

Směrová konzistence je variantou oblouku, cesty a ${ displaystyle i}$ -konzistence přizpůsobená pro použití algoritmem, který přiřazuje hodnoty proměnným podle daného pořadí proměnných. Jsou podobné jejich nesměrovým protějškům, ale vyžadují pouze to, aby bylo možné konzistentní přiřazení některých proměnných konzistentně rozšířit na jinou proměnnou, která je podle pořadí větší než oni.

Směrový oblouk a konzistence cesty

Instance, která je směrově oblouková konzistentní podle pořadí x1 x2 x3, ale není konzistentní oblouku (mezi x1 a x3 není žádné omezení; odpovídající okraje jsou vynechány). Každá hodnota proměnné s nižším indexem odpovídá hodnotám proměnných s vyšším indexem. Otazníky označují body, kde konverzace neplatí.

Pokud algoritmus vyhodnocuje proměnné v pořadí ${ displaystyle x_ {1}, ldots, x_ {n}}$ , konzistence je užitečná pouze tehdy, když zaručuje, že hodnoty proměnných s nižším indexem jsou všechny konzistentní s hodnotami těch s vyšším indexem.

Při výběru hodnoty pro proměnnou mohou být zanedbány hodnoty, které jsou nekonzistentní se všemi hodnotami nepřiřazené proměnné. Ve skutečnosti, i když jsou tyto hodnoty všechny konzistentní s aktuálním částečným hodnocením, algoritmus později nedokáže najít konzistentní hodnotu pro nepřiřazenou proměnnou. Na druhou stranu vynucování konzistence s proměnnými, které jsou již vyhodnocovány, není nutné: pokud algoritmus zvolí hodnotu, která je nekonzistentní s aktuálním částečným hodnocením, je nekonzistence detekována.

Za předpokladu, že pořadí vyhodnocení proměnných je ${ displaystyle x_ {1}, ldots, x_ {n}}$ , problém uspokojení omezení je směrově obloukový konzistentní, pokud je každá proměnná ${ displaystyle x_ {i}}$ je oblouk konzistentní s jakoukoli jinou proměnnou ${ displaystyle x_ {j}}$ takhle ${ displaystyle i$ . Konzistence směrové cesty je podobná, ale dvě proměnné ${ displaystyle x_ {i}, x_ {j}}$ musí být cesta v souladu s ${ displaystyle x_ {z}}$ jen když ${ displaystyle i, j$ . Silná konzistence směrové cesty znamená jak konzistenci směrové cesty, tak konzistenci směrového oblouku. Podobné definice lze uvést i pro ostatní formy konzistence.

Šíření omezení pro konzistenci oblouku a cesty

Šíření omezení vynucující konzistenci směrového oblouku iteruje přes proměnné od posledního po první, přičemž v každém kroku vynucuje konzistenci oblouku každé proměnné nižšího indexu. Pokud je pořadí proměnných ${ displaystyle x_ {1}, ldots, x_ {n}}$ , tento algoritmus iteruje přes proměnné z ${ displaystyle x_ {n}}$ na ${ displaystyle x_ {1}}$ ; pro proměnnou ${ displaystyle x_ {j}}$ , vynucuje konzistenci oblouku každé proměnné indexu nižší než ${ displaystyle j}$ s ${ displaystyle x_ {j}}$ .


Instance, která není konzistentní se směrovým obloukem: ${ displaystyle x_ {1} = 2}$ neodpovídá žádné hodnotě ${ displaystyle x_ {2}}$ a ${ displaystyle x_ {2} = 3}$ neodpovídá žádné hodnotě ${ displaystyle x_ {3}}$ . Mezi nimi není žádné omezení ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {3}}$ (odpovídající hrany jsou vynechány).	Vynucování konzistence směrového oblouku začíná na ${ displaystyle x_ {3}}$ a dělá ${ displaystyle x_ {2}}$ oblouk v souladu s tím odstraněním hodnoty ${ displaystyle x_ {2} = 3}$ .	Pokračuje prosazování konzistence směrového oblouku ${ displaystyle x_ {2}}$ . Od té doby ${ displaystyle x_ {2} = 3}$ již byl odstraněn, oba ${ displaystyle x_ {1} = 2}$ a ${ displaystyle x_ {1} = 3}$ jsou odstraněny.

Konzistenci směrových cest a silnou konzistenci směrových cest lze vynutit pomocí algoritmů podobných algoritmu konzistence oblouku. Zpracovávají proměnné z ${ displaystyle x_ {n}}$ na ${ displaystyle x_ {1}}$ ; pro každou proměnnou ${ displaystyle x_ {z}}$ dvě proměnné ${ displaystyle x_ {i}, x_ {j}}$ s ${ displaystyle i, j$ jsou brány v úvahu a jejich konzistence s ${ displaystyle x_ {z}}$ je vynuceno. Pokud problém neobsahuje žádná omezení, není nutná žádná operace ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {z}}$ nebo žádné omezení mezi ${ displaystyle x_ {j}}$ a ${ displaystyle x_ {z}}$ . I když mezi nimi není žádné omezení ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ , předpokládá se triviální. Pokud šíření omezení snižuje jeho sadu uspokojivých přiřazení, efektivně vytvoří nové netriviální omezení. Propagace omezení vynucující silnou konzistenci směrové cesty je podobná, ale také vynucuje konzistenci oblouku.

Směrová konzistence a uspokojivost

Směrová konzistence zaručuje, že dílčí řešení splňující omezení lze konzistentně rozšířit na další proměnnou s vyšším indexem. Nezaručuje však, že rozšíření různých proměnných jsou navzájem konzistentní. Například částečné řešení může být důsledně rozšířeno na variabilní ${ displaystyle x_ {i}}$ nebo do proměnné ${ displaystyle x_ {j}}$ , ale přesto tato dvě rozšíření nejsou navzájem konzistentní.

Existují dva případy, kdy k tomu nedojde, a směrová konzistence zaručuje uspokojivost, pokud žádná doména není prázdná a žádné omezení není uspokojivé.

Prvním případem je problém binárního omezení s uspořádáním proměnných, které tvoří uspořádaný graf omezení s šířka 1. Takové uspořádání existuje tehdy a jen tehdy, je-li grafem omezení strom. Je-li tomu tak, šířka grafu ohraničuje maximální počet dolních (podle pořadí) uzlů, ke kterým je uzel připojen. Konzistence směrového oblouku zaručuje, že každé konzistentní přiřazení proměnné lze rozšířit na vyšší uzly a šířka 1 zaručuje, že uzel není spojen s více než jedním nižším uzlem. Výsledkem je, že jakmile je přiřazena dolní proměnná, její hodnotu lze konzistentně rozšířit na každou vyšší proměnnou, ke které je připojena. Toto rozšíření nemůže později vést k nekonzistenci. Ve skutečnosti k této vyšší proměnné není připojena žádná další nižší proměnná, protože graf má šířku 1.

Výsledkem je, že pokud má problém omezení šířku 1 s ohledem na uspořádání jeho proměnných (což znamená, že jeho odpovídající graf je strom) a problém je směrově obloukový konzistentní s ohledem na stejné uspořádání, řešení (pokud existuje) lze najít iterativním přiřazením proměnných podle pořadí.

Druhým případem, ve kterém směrová konzistence zaručuje uspokojivost, pokud žádná doména není prázdná a žádné omezení není uspokojivé, je problém s binárními omezeními, jehož graf má indukovaná šířka 2, pomocí silné konzistence směrové cesty. Tato forma konzistence skutečně zaručuje, že každé přiřazení proměnné nebo dvojice proměnných lze rozšířit na vyšší proměnnou a šířka 2 zaručuje, že tato proměnná není spojena s jinou dvojicí nižších proměnných.

Důvodem, proč se místo šířky uvažuje o indukované šířce, je to, že vynucování konzistence směrové cesty může přidat omezení. Ve skutečnosti, pokud dvě proměnné nejsou ve stejném omezení, ale jsou v omezení s vyšší proměnnou, některé páry jejich hodnot mohou narušit konzistenci cesty. Odebráním takových párů se vytvoří nové omezení. Výsledkem může být, že šíření omezení může způsobit problém, jehož graf má více hran než ten původní. Všechny tyto hrany jsou však nutně v indukovaném grafu, protože jsou všechny mezi dvěma rodiči stejného uzlu. Šířka 2 zaručuje, že každé konzistentní částečné vyhodnocení lze rozšířit na řešení, ale tato šířka je relativní k vygenerovanému grafu. Ve výsledku je pro silnou konzistenci směrové cesty zaručena existence řešení nutná indukovaná šířka 2.

Směrová i-konzistence

Modré čáry označují, že mezi x3 a x4 neexistuje žádné omezení, takže je povolena každá dvojice hodnot. Na těchto obrázcích nedostatek hran mezi dvěma proměnnými implicitně naznačuje nedostatek omezení. Tento problém má šířku 2.

Směrový ${ displaystyle i}$ -konzistence je zárukou, že každé konzistentní přiřazení ${ displaystyle i-1}$ proměnné lze konzistentně rozšířit na jinou proměnnou, která je v pořadí vyšší. Silný směr ${ displaystyle i}$ -konzistence je definována podobným způsobem, ale všechny skupiny nejvíce ${ displaystyle i-1}$ jsou uvažovány proměnné. Pokud je problém silně směrový ${ displaystyle i}$ -konzistentní a má šířku menší než ${ displaystyle i}$ a nemá žádnou prázdnou doménu nebo neuspokojivé omezení, má řešení.

Každý problém může být silně směrován ${ displaystyle i}$ -konzistentní, ale tato operace může zvýšit šířku odpovídajících grafů. Postup šíření omezení, který vynucuje směrovou konzistenci, je podobný postupu použitému pro konzistenci směrového oblouku a konzistenci cesty. Proměnné se berou v úvahu postupně od poslední po první podle pořadí. Pro proměnnou ${ displaystyle x_ {k}}$ , algoritmus bere v úvahu každou skupinu ${ displaystyle i-1}$ proměnné, které mají index nižší než ${ displaystyle k}$ a jsou v omezení s ${ displaystyle x_ {k}}$ . Konzistence těchto proměnných s ${ displaystyle x_ {k}}$ je zkontrolováno a možná vynuceno odstraněním uspokojivých přiřazení z omezení mezi všemi těmito ${ displaystyle i}$ proměnné (pokud existují, nebo vytvoření nové jinak).

Vynucení konzistence na x5 odstraní červenou čáru, čímž vytvoří nové netriviální omezení mezi x3 a x4. Výsledkem je, že x4 má x3 jako nového rodiče, kromě x1 a x2. Tato změna zvětší šířku na 3.

Tento postup generuje silně směrový ${ displaystyle i}$ -konzistentní instance. Může však také přidat do instance nová omezení. Výsledkem je, že i když je šířka původního problému ${ displaystyle i}$ , šířka výsledné instance může být větší. Pokud tomu tak je, směrová silná konzistence neznamená uspokojivost, i když žádná doména není prázdná a žádné omezení není uspokojivé.

Šíření omezení však přidává omezení pouze do proměnných, které jsou nižší než ty, které aktuálně zvažuje. Výsledkem je, že se po proměně algoritmu s touto proměnnou nezmění ani nepřidá žádné omezení nad proměnnou. Místo uvažování o opraveném ${ displaystyle i}$ , lze jej upravit na počet rodičů každé uvažované proměnné (rodiči proměnné jsou proměnné indexu nižší než proměnná, které jsou v proměnné v omezení). To odpovídá zvážení všech rodičů dané proměnné v každém kroku. Jinými slovy, pro každou proměnnou ${ displaystyle x_ {i}}$ od posledního k prvnímu jsou všichni jeho rodiče zahrnuti do nového omezení, které omezuje jejich hodnoty na ty, které jsou v souladu s ${ displaystyle x_ {i}}$ . Vzhledem k tomu, že tento algoritmus lze považovat za modifikaci předchozího s hodnotou ${ displaystyle i}$ který se změní na počet rodičů každého uzlu, nazývá se adaptivní konzistence.

Tento algoritmus vynucuje silnou směrovost ${ displaystyle i}$ -konzistentnost s ${ displaystyle i}$ rovná indukované šířce problému. Výsledná instance je uspokojivá, právě když není žádná doména nebo omezení prázdné. Pokud tomu tak je, lze řešení snadno najít iterativním nastavením nepřiřazené proměnné na libovolnou hodnotu a šířením tohoto částečného vyhodnocení do dalších proměnných. Tento algoritmus není vždy polynomiální čas, protože počet omezení zavedených vynucením silné směrové konzistence může způsobit exponenciální zvětšení velikosti. Problém je však řešitelný v polynomiální čas pokud prosazování silné směrové konzistence není superpolynomiálně zvětšit instanci. Výsledkem je, že pokud instance vyvolala šířku ohraničenou konstantou, lze ji vyřešit v polynomiálním čase.

Odstranění lopaty

Eliminace lopaty je algoritmus uspokojivosti. Lze jej definovat jako přeformulování adaptivní konzistence. Jeho definice používá kbelíky, které jsou kontejnery pro omezení, přičemž každá proměnná má přidružený kbelík. Omezení vždy patří do kbelíku jeho nejvyšší proměnné.

Algoritmus eliminace lopaty postupně postupuje od nejvyšší k nejnižší proměnné. V každém kroku jsou omezení v segmentech této proměnné ${ displaystyle x_ {i}}$ jsou považovány. Podle definice tato omezení zahrnují pouze proměnné, které jsou nižší než ${ displaystyle x_ {i}}$ . Algoritmus upravuje omezení mezi těmito nižšími proměnnými (pokud existuje, jinak vytvoří novou). Zejména prosazuje, aby jejich hodnoty mohly být rozšiřitelné ${ displaystyle x_ {i}}$ v souladu s omezeními v kbelíku ${ displaystyle x_ {i}}$ . Toto nové omezení, pokud existuje, je poté umístěno do příslušného kbelíku. Protože toto omezení zahrnuje pouze proměnné, které jsou nižší než ${ displaystyle x_ {i}}$ , je přidán do kbelíku proměnné, která je nižší než ${ displaystyle x_ {i}}$ .

Tento algoritmus je ekvivalentní prosazování adaptivní konzistence. Protože oba vynucují konzistenci proměnné se všemi svými rodiči a protože po zvážení proměnné není přidáno žádné nové omezení, výsledkem je instance, kterou lze vyřešit bez ustoupit.

Protože graf instance, kterou produkují, je podgrafem indukovaného grafu, je-li indukovaná šířka omezena konstantou, generovaná instance má velikost polynomu ve velikosti původní instance. Výsledkem je, že pokud je indukovaná šířka instance omezena konstantou, její řešení lze provést v polynomiálním čase dvěma algoritmy.

Relační konzistence

Zatímco předchozí definice konzistence jsou o konzistenci úkolů, relační konzistence zahrnuje uspokojení pouze daného omezení nebo sady omezení. Přesněji řečeno, relační konzistence znamená, že každé konzistentní částečné přiřazení lze rozšířit takovým způsobem, aby bylo splněno dané omezení nebo sada omezení. Formálně omezení ${ displaystyle C}$ na proměnné ${ displaystyle X}$ je relační oblouk konzistentní s jednou z jeho proměnných ${ displaystyle x}$ pokud každý konzistentní úkol ${ displaystyle X zpětné lomítko {x }}$ lze rozšířit na ${ displaystyle x}$ takovým způsobem ${ displaystyle C}$ je spokojen. Rozdíl mezi „běžným“ ${ displaystyle i}$ konzistence a konzistence relačního oblouku spočívá v tom, že druhý vyžaduje pouze rozšířené přiřazení k uspokojení daného omezení, zatímco druhý vyžaduje splnění všech příslušných omezení.

(Pravidelné) i-konzistence: pokud je hodnocení konzistentní, může být rozšířeno na jinou proměnnou takovým způsobem, že jsou splněna všechna relevantní omezení.

Konzistence relačního oblouku: pokud je vyhodnocení proměnných omezení, ale jedna je konzistentní, lze ji vždy rozšířit na tuto proměnnou takovým způsobem omezení je spokojen. Azurové hrany představují omezení, která nemusí rozšíření splňovat.

Tuto definici lze rozšířit na více než jedno omezení a více než jednu proměnnou. Zejména konzistence relační cesty je podobná konzistenci relačního oblouku, ale místo jedné se používají dvě omezení. Dvě omezení jsou relační cesta konzistentní s proměnnou, pokud je každé konzistentní přiřazení všem jejich proměnným, ale uvažované lze rozšířit takovým způsobem, že jsou splněna dvě omezení.

Pro více než dvě omezení, relační ${ displaystyle m}$ -konzistence je definována. Relační ${ displaystyle m}$ -konzistence zahrnuje soubor ${ displaystyle m}$ omezení a proměnná, která je v rozsahu všech těchto omezení. Zejména tyto ${ displaystyle m}$ omezení jsou relační ${ displaystyle m}$ -konzistentní s proměnnou, pokud lze každé konzistentní přiřazení ke všem ostatním proměnným, které jsou v jejich oborech, rozšířit na proměnnou takovým způsobem, že jsou splněna tato omezení. Problém je ${ displaystyle m}$ - relační konzistentní, pokud každá sada ${ displaystyle m}$ omezení je relační ${ displaystyle m}$ -konzistentní s každou proměnnou, která je ve všech jejich oborech. Silný relační ${ displaystyle m}$ konzistence je definována výše: je to vlastnost být relační ${ displaystyle k}$ -konzistentní pro každého ${ displaystyle k$ .

Relační konzistenci lze také definovat pro více proměnných, namísto jedné. Sada ${ displaystyle m}$ omezení je relační ${ displaystyle (i, m)}$ -konzistentní, pokud každé konzistentní přiřazení k podmnožině ${ displaystyle i}$ jejich proměnných lze rozšířit na vyhodnocení na všechny proměnné, které splňují všechna omezení. Tato definice přesně nerozšiřuje výše uvedené, protože proměnné, na které mají být hodnocení rozšiřitelná, nemusí být nutně ve všech oborech zahrnutých omezení.

Je-li zadáno pořadí proměnných, lze relační konzistenci omezit na případy, kdy by hodnocení mělo být rozšiřitelné tak, aby sledovalo ostatní proměnné v pořadí. Tato upravená podmínka se nazývá směrovou relační konzistencí.

Relační konzistence a uspokojivost

Problém uspokojení omezení může být relačně konzistentní, nemá prázdnou doménu nebo nevyhovující omezení a přesto může být nevyhovující. Existují však případy, kdy to není možné.

První případ je silně relační ${ displaystyle m}$ -konzistentní problém, když domény obsahují maximálně ${ displaystyle m}$ elementy. V tomto případě je třeba důsledně vyhodnotit ${ displaystyle k}$ proměnné lze vždy rozšířit na jednu jinou proměnnou. Li ${ displaystyle x_ {1} = a_ {1}, ldots, x_ {k} = a_ {k}}$ je takové hodnocení a ${ displaystyle x_ {k + 1}}$ je proměnná, existují pouze ${ displaystyle m}$ možné hodnoty, které proměnná může nabývat. Pokud všechny takové hodnoty nejsou v souladu s hodnocením, existují ${ displaystyle m}$ (nemusí být nutně jedinečná) omezení, která jsou porušena hodnocením a jednou z jeho možných hodnot. As a result, the evaluation cannot be extended to satisfy all these ${ displaystyle m}$ -or-less constraints, violating the condition of strong relational ${ displaystyle m}$ -consistency.

The second case is related to a measure of the constraints, rather than the domains. A constraint is ${ displaystyle m}$ -tight if every evaluation to all its variables but one can be extended to satisfy the constraint either by all possible values of the other variable or by at most ${ displaystyle m}$ of its values. Problem having ${ displaystyle m}$ -tight constraints are satisfiable if and only if they are strongly relationally ${ displaystyle m + 1}$ -consistent.

A row convex matrix: the 1's in each row are contiguous (no 0 in between them).

The third case is that of binary constraints that can be represented by row-convex matrices. A binary constraint can be represented by a bidimensional matrix ${ displaystyle M}$ , kde ${displaystyle M_{ij}}$ is 0 or 1 depending on whether the ${ displaystyle i}$ -th value of the domain of ${ displaystyle x_ {i}}$ a ${ displaystyle j}$ -th value of the domain of ${ displaystyle x_ {j}}$ satisfy the constraint. A row of this matrix is convex if the 1's it contains are consecutive (formally, if two elements are 1, all elements in between are 1 as well). A matrix is row convex if all its rows are convex.

Each matrix represents the constraint between X_i a X_k+1. Li A₁...A_k are values for X₁...X_k, the rows of A₁...A_k in each matrix tell the allowed values for X_k+1. Row-convex-ness and strong relational path consistency imply the existence of a consistent value A_k+1 pro X_k+1.

The condition that makes strong relational path consistency equivalent to satisfiability is that of constraint satisfaction problems for which there exists an order of the variables that makes all constraint to be represented by row convex matrices. This result is based on the fact that a set of convex rows having a common element pairwise also have a globally common element. Considering an evaluation over ${ displaystyle k}$ variables, the allowed values for the ${ displaystyle k + 1}$ -th one are given by selecting some rows from some constraints. In particular, for every variable among the ${ displaystyle k}$ ones, the row relative to its value in the matrix representing the constraint relating it with the ${ displaystyle k + 1}$ one represents the allowed values of the latter. Since these row are convex, and they have a common element pairwise because of path consistency, they also have a shared common element, which represents a value of the last variable that is consistent with the other ones.

Uses of local consistency

All forms of local consistency can be enforced by constraint propagation, which may reduce the domains of variables and the sets of assignments satisfying a constraint and may introduce new constraints. Whenever constraint propagation produces an empty domain or an unsatisfiable constraint, the original problem is unsatisfiable. Therefore, all forms of local consistency can be used as approximations of satisfiability. More precisely, they can be used as incomplete unsatisfiability algorithms, as they can prove that a problem is unsatisfiable, but are in general unable to prove that a problem is satisfiable. Such approximated algorithms can be used by search algorithms (ustoupit, zpětný skok, místní vyhledávání, etc.) as heuristics for telling whether a partial solution can be extended to satisfy all constraints without further analyzing it.

Even if constraint propagation does not produce an empty domain or an unsatisfiable constraint, it may nevertheless reduce the domains or strengthen the constraints. If this is the case, the hledat prostor of the problem is reduced, thus reducing the amount of search needed to solve the problem.

Local consistency proves satisfiability in some restricted cases (see Complexity of constraint satisfaction#Restrictions ). This is the case for some special kind of problems and/or for some kinds of local consistency. For example, enforcing arc consistency on binary acyclic problems allows for telling whether the problem is satisfiable. Enforcing strong directional ${ displaystyle i}$ -consistency allows telling the satisfiability of problems that have induced width ${ displaystyle i-1}$ according to the same order. Adaptive directional consistency allows telling the satisfiability of an arbitrary problem.

Viz také

externí odkazy

Propagace omezení - Dissertation by Guido Tack giving a good survey of theory and implementation issues

Reference

Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3
Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0
Marriott, Kim; Peter J. Stuckey (1998). Programování s omezeními: Úvod. MIT Stiskněte. ISBN 0-262-13341-5