Riešenie problémov s ohraničeniami
Marián MACH1
Abstrakt. Ohraničenia sú všadeprítomné a nie je možné sa im vyhnúť, neustále je potrebné
zohľadňovať rôzne obmedzujúce požiadavky. Na druhej strane reprezentácia problémov pomocou
explicitného popisu ohraničení je veľmi prirodzenou a názornou. Predkladaný text sa sústreďuje na
úlohy pracujúce s konečnými doménami, ktoré majú kombinatorickú povahu. Je ich možné riešiť
pomocou pomerne značného počtu prístupov, pochádzajúcich z rôznych oblastí. Pozornosť je
sústredená na metódy spĺňania ohraničení, evolučné algoritmy a metódy, umožňujúce využiť
špecifické znalosti o riešených úlohách.
1 Úvod
Či sa jedná o plánovací problém, rozvrhovanie, prideľovanie zdrojov, návrhové úlohy alebo
iné problémy, neustále je potrebné zohľadňovať rôzne požiadavky ako napr. dostupnosť
zdrojov, časové závislosti, charakteristiky použitých elementov, ap. Ak si uvedomíme koľko
úloh technickej praxe možno formulovať ako úlohy s ohraničeniami, tak je zrejmý dôvod,
prečo metódy riešenia úloh s ohraničeniami majú takú dôležitosť.
Problémy s ohraničeniami je vo všeobecnosti možné rozdeliť do dvoch základných tried
– úlohy pracujúce s konečnými alebo nekonečnými doménami. Predkladaný text sa
sústreďuje na prvú skupinu. Problémy z tejto skupiny majú kombinatorickú povahu, čo je
zdrojom pomerne značných požiadaviek kladených na metódy používané pre riešenie týchto
problémov – značná časť týchto problémov totiž patrí do kategórie NP-úplných problémov.
Úlohy s ohraničeniami je možné riešiť pomocou pomerne značného počtu prístupov
pochádzajúcich z rôznych oblastí, väčšinou z oblasti operačného výskumu a umelej
inteligencie. Predkladaný text sa zameriava na tri triedy prístupov – deterministické
algoritmické riešenie, stochastické riešenie a riešenie založené na doménových znalostiach,
pričom v rámci každého z nich venuje pozornosť iba jednému typu metód – konzistenčným
algoritmom, evolučným algoritmom a znalostným modelom. Tieto prístupy prezentujú
pomerne rozmanitú vzorku metód, pretože zahŕňajú:
1

ako metódy garantujúce nájdenie riešenia (ak toto existuje), tak aj metódy, ktoré toto
negarantujú

ako metódy pracujúce iba s jedným riešením, tak aj metódy s paralelným spôsobom
práce

ako metódy špecializované na riešenie problémov s ohraničeniami, tak aj metódy
použiteľné aj pre riešenie iných typov úloh

ako metódy abstrahujúce od špecifických detailov konkrétnych úloh, tak aj metódy
stavajúce práve na týchto detailoch.
KKUI, FEI, Technická univerzita, Letná 9, 042 00 Košice, E-mail: [email protected]
2 Problémy s ohraničeniami
Ako ilustračného reprezentanta kombinatorického problému s ohraničeniami nad konečnými
doménami použijeme známy hlavolam Sudoku, ktorého jedna inštancia je zobrazená na
Obrázku 1. Hlavolam pozostáva z mriežky vytvorenej deviatimi riadkami, deviatimi stĺpcami
a deviatimi 3x3 štvorcami. Spolu obsahuje 81 pozícií (pozícia 11 reprezentuje ľavú hornú
a 99 zase pravú dolnú pozíciu – prvá cifra značí riadok a druhá zase stĺpec), pričom niektoré
pozície sú obsadené zatiaľ čo iné sú voľné. Cieľom je na každú voľnú pozíciu priradiť jednu
číslicu z {1, 2, 3, 4, 5, 6, 7, 8, 9} tak, aby v žiadnom riadku, stĺpci ani štvorci neboli dve
rovnaké číslice.
8 2
5 3 9
5
3
1
8 9 5
7
9
4
6
7
1
8
9 5
7
2
6
5
4
Obrázok 1. Ilustračný problém s ohraničeniami nad konečnými doménami.
Z formálneho hľadiska je problém s ohraničeniami vo všeobecnosti definovaný pomocou
troch množín:

množina premenných V = {V1, V2, ..., Vn}

množina domén D = {D1, D2, ..., Dn}

množina ohraničení C = {C1, ..., Cn, C1,2, ..., Cn-1,n, ..., C1,2,...,n}.
Premenné reprezentujú tie udalosti, stavy atď., hodnoty ktorých sú relevantné pre
riešenie konkrétneho problému. V príklade na Obrázku 1 je najprirodzenejšou reprezentáciou
taká, keď každá pozícia mriežky je reprezentovaná samostatnou premennou. Výsledkom bude
súbor 81 premenných, kde V11 reprezentuje pozíciu 11 a V99 zase pozíciu 99.
Každá doména Di  D zodpovedá premennej Vi  V a vlastne definuje možné hodnoty,
ktoré premenná Vi môže nadobúdať. V našom prípade sú použité konečné domény
enumeračného typu. Všetky domény sú rovnaké – množina deviatich číslic 1 až 9.
Nad premennými z množiny V je definovaná množina ohraničení. Indexy jednotlivých
ohraničení označujú árnosť týchto ohraničení a premenné, nad ktorými tieto ohraničenia sú
definované. Tak napr. ohraničenie Ci,j je binárnym ohraničením nad premennými Vi a Vj.
Definované ohraničenia stanovujú prípustnosť hodnôt premenných v rámci nejakého
kontextu. Týmto kontextom sú hodnoty iných premenných (počet týchto premenných závisí
od árnosti ohraničení). Napríklad, ak nejaké ohraničenie je definované nad podmnožinou
premenných, potom toto ohraničenie pre každú premennú z tejto podmnožiny stanovuje
prípustnosť priradenia hodnoty z jej domény v kontexte tvorenom hodnotami ostatných
premenných danej podmnožiny. Jedinou výnimkou sú unárne ohraničenia, pri ktorých nie je
potrebné brať do úvahy hodnoty iných premenných.
Pre skupinu n premenných je teda možné definovať unárne, binárne, ... až n-árne
ohraničenia. Celkový počet ohraničení, ktoré je možné definovať pre n premenných je
n
n
  i 
i 1
(1)
 
pričom i označuje árnosť ohraničení. Je teda zrejmé, že je možné definovať až n unárnych
ohraničení a jedno n-árne ohraničenie. Maximálny počet binárnych ohraničení je daný
vzťahom (n2 – n)/2. Okrem n-árneho ohraničenia všetky ostatné sú definované iba nad
nejakou podmnožinou premenných (premenné z tejto podmnožiny sa označujú ako relevantné
voči príslušnému ohraničeniu). V našom prípade teda je možných až 81 unárnych ohraničení,
3240 binárnych, 85320 ternárnych ohraničení, atď.
Všetky ohraničenia sú definované nad podmnožinami premenných originálnej množiny
a obmedzujú kombinácie hodnôt, ktoré premenné daných podmnožín môžu nadobudnúť.
Extrémnymi prípadmi sú ohraničenia, ktoré nepripúšťajú žiadne alebo naopak pripúšťajú
všetky možné kombinácie hodnôt premenných, nad ktorými sú tieto ohraničenia definované.
V prvom prípade nie je možné nájsť také riešenie, pre ktoré by takéto extrémne ohraničenie
bolo splnené. V druhom prípade je také ohraničenie v množine ohraničení zaradené iba
formálne a možno ho z tejto množiny vypustiť.
Pre reprezentáciu nejakého ohraničenia je možné použiť vymenovanie jednotlivých
kombinácií hodnôt (či už povolených alebo zakázaných) alebo ohraničenie možno zadať
nejakým predpisom, ktorý pre každú kombináciu hodnôt premenných umožňuje rozhodnúť, či
daná kombinácia porušuje dané ohraničenie alebo nie. To, ktorý tvar je využitý, závisí od
konkrétnej úlohy a spôsobu práce s ohraničeniami. Náš demonštračný príklad priamo zo
svojej definície ponúka 27 rôznych 9-árnych ohraničení (jedno pre každý z deviatich riadkov,
stĺpcov a štvorcov). Aj keď je možné takéto ohraničenie reprezentovať vymenovaním
prípustných kombinácií hodnôt relevantných premenných, bolo by to nepraktické pre počet
týchto kombinácií (najmenší počet by bol pre ôsmy stĺpec – 24 prípustných možností,
najväčší pre tretí riadok – 40320 prípustných možností).
V praktických úlohách sa vyskytujú ohraničenia rôznych árností. Pretože však unárne
ohraničenia je možné zohľadniť príslušnou redukciou domén jednotlivých premenných (resp.
naopak je ich možné rozšíriť na binárne ohraničenia) a ohraničenia vyšších árností môžu byť
redukované na binárne ohraničenia (aj keď niekedy za cenu zavedenia nových pomocných
premenných) [1] [39], väčšina prác sa zaoberá práve binárnymi problémami s ohraničeniami –
problémami, v ktorých všetky ohraničenia sú definované najviac nad dvoma premennými.
Použitý ilustračný problém používa špeciálny typ ohraničení – „alldiff“ ohraničenia
(všetky premenné v rámci takéhoto ohraničenia musia mať navzájom rôzne hodnoty). Pri
tomto type sa 9-árne ohraničenie dá nahradiť 84 ternárnymi alebo 36 binárnymi
ohraničeniami rovnakého typu (po jednom pre každý výber troch alebo dvoch premenných
z daných deviatich relevantných premenných).
Pri reprezentácii predpisom je možné ohraničenie použiť iba na testovanie, či nejaká
kombinácia hodnôt premenných je z hľadiska daného ohraničenia prípustná alebo nie.
Príkladom môže byť ternárne ohraničenie: „tri premenné z toho istého riadku (resp. stĺpca či
štvorca) musia mať navzájom rôzne hodnoty“. Takýmto ohraničením môže byť napr. C12,13,22.
Reprezentácia vymenovaním umožňuje nielen iba testovať ale aj použiť ohraničenie
generatívnym spôsobom – priamo získať kombinácie hodnôt relevantných premenných, ktoré
sú validné z pohľadu daného ohraničenia. Príkladom môže byť binárne ohraničenie C21,31 pri
vymenovaní majúce tvar množiny {(1,2),(1,3), ..., (9,7), (9,8)} so 72 dvojicami.
Okrem ohraničení na rôznosť hodnôt kombinácií premenných problém ohraničuje priamo
niektoré premenné. Toto reprezentujú unárne ohraničenia dané vymenovaním prípustných
hodnôt napr. C13={8}.
Keď úloha pre niektoré premenné resp. kombinácie premenných nedefinuje ohraničenia
priamo, je možné takéto ohraničenia formálne zaviesť. Aby takéto ohraničenie nemenilo
definíciu úlohy, povoľuje všetky možné kombinácie hodnôt relevantných premenných. Tak je
možné zaviesť napr. C31,42={(1,1), ..., (9,9)} s 81 dvojicami hodnôt, C11={1, ..., 9} s deviatimi
hodnotami a C31,32,42 so 729 trojicami hodnôt.
Keďže je potrebné splniť všetky ohraničenia (teda aj unárne), je možné znížiť
komplexnosť problému redukciou domén jednotlivých premenných. Po tejto redukcii
premennej Vi bude zodpovedať redukovaná doména, ktorá vznikne z pôvodnej domény
vypustením všetkých prvkov nespĺňajúcich unárne ohraničenie viažúce sa na premennú Vi.
Táto redukcia sa môže rozšíriť aj na definície ohraničení. Ak binárne ohraničenie
povoľuje nejakú takú kombináciu hodnôt, ktorá obsahuje hodnotu, porušujúcu unárne
ohraničenie viažúce sa k príslušnej premennej, potom je možné toto binárne ohraničenie
„sprísniť“ a danú kombináciu hodnôt nepovoliť. Takýmto spôsobom dochádza k zvyšovaniu
prísnosti ohraničení (danej pomerom počtu kombinácií hodnôt povolených daným
ohraničením voči všetkým možným kombináciám hodnôt).
Napríklad keďže unárne ohraničenie C13 obsahuje iba jednu hodnotu 8 zatiaľ čo binárne
ohraničenie C12,13 obsahuje 72 dvojíc, je možné C12,13 sprísniť iba na osem prípustných dvojíc
C12,13 = {(1,8), (2, 8), ..., (7,8), (9,8)}. Podobne je možné sprísniť na osem dvojíc aj C 12,22.
A následne ternárne ohraničenie C12,13,22 možno na základe C12,13 a C12,22 sprísniť na sedem
prípustných trojíc (ak by bolo reprezentované vymenovaním a nie predpisom).
Obidva uvedené prípady (vymenovanie a predpis) ilustrujú explicitný tvar ohraničenia.
Ohraničenie však môže byť vyjadrené aj implicitným spôsobom – samotné ohraničenie nie je
priamo uvedené ale je reprezentované iba prostredníctvom iných ohraničení, z ktorých môže
byť indukované. Príkladom je C41,32. Keďže zahŕňa dve pozície v rozličných stĺpcoch,
riadkoch aj štvorcoch, nijako neohraničuje hodnoty na daných dvoch pozíciách. Avšak napr.
ohraničenia C22, C22,32, C15, C14,15 indukujú neprípustnosť dvojíc (7,...) a (...,5) pre C41,32 ktoré
tým pádom by malo povoľovať iba 64 dvojíc. Takúto indukciu je možné (aspoň čiastočne)
urobiť pri reprezentácii problému, ale zvyčajne sa to nerobí a prenecháva sa to príslušným
metódam pre riešenie úloh s ohraničeniami.
Ilustračný príklad bude teda reprezentovaný tak, že unárne ohraničenia budú dané podľa
Obrázku 2, binárne ohraničenia budú reprezentované vymenovaním povolených dvojíc,
pričom budú sprísnené v závislosti od obsahu unárnych ohraničení, a ternárne a viacárne
ohraničenia budú dané predpisom.
Domény premenných vlastne definujú priestor. Je to vlastne priestor všetkých
potenciálnych riešení (kandidátov riešení) – všetkých možných kombinácií hodnôt z domén
premenných. Ak každá z domén bude reprezentovaná ako jedna súradnica tohto priestoru,
potom každý bod tohto priestoru bude reprezentovať jednu kombináciu hodnôt premenných.
Tento priestor takto vznikne ako kartézsky súčin domén premenných – ako množina všetkých
kombinácií hodnôt jednotlivých premenných.
3 Algoritmické spĺňanie ohraničení
Táto trieda metód bola v minulosti označovaná rôznymi názvami napr. konzistentné
značkovanie (consistent labeling) či spĺňajúce priradenia (satisficing assignment). Napokon
sa pre ňu vžilo označenie spĺňanie ohraničení (constraint satisfaction).
Jednou z prvých aplikačných domén sa stala interaktívna grafika, kde prvým systémom
bol Sutherlandov Sketchpad [35] začiatkom šesťdesiatych rokov. Jeho pokračovateľom je
Borningov ThingLab [5]. Tieto systémy dovoľovali používateľovi kresliť a manipulovať
s geometrickými obrázkami, podliehajúcimi ohraničeniam, po displeji počítača.
Prvé práce spojené s oblasťou algoritmov momentálne zahŕňaných pod týmto spoločným
názvom siahajú do polovice sedemdesiatych rokov. Popudom k rozvoju v tejto oblasti sa stali
algoritmy používané pre interpretáciu trojrozmerných scén na základe dvojrozmerných
obrazov (bolo potrebné zohľadňovať ohraničenia pri interpretácii čiarových obrazov – napr.
trojrozmerná interpretácia nejakej čiary ako hrany musí byť rovnaká na oboch jej koncoch).
Vtedajší študent MIT AI Lab (Laboratória pre umelú inteligenciu na Massachussetskom
technologickom inštitúte) David Waltz si uvedomoval kombinatorickú explóziu znižujúcu
použiteľnosť vtedy známych interpretačných metód a preto pre jej zmenšenie vytvoril
filtračný algoritmus na odstránenie nekonzistentných interpretácií [38].
Ďalší ranný vývoj v tejto oblasti je spojený s takými menami ako Eugene C. Freuder,
John Gaschnig, Robert M. Haralick, Alan K. Mackworth a Ugo Montanari [23] [13] [17].
Došlo k abstrahovaniu vlastností algoritmov, k ich oddeleniu od aplikácií a k formovaniu
oblasti do takého tvaru, v akom je známa dnes. Popisy základných algoritmov pre spĺňanie
ohraničení je možné nájsť napr. v prehľadových publikáciách [22] a [10]. Z on-line
dostupných rozsiahlejších publikácií sú k dispozícii [36] (v angličtine) a [25] (v slovenčine).
Jednou z tried algoritmov sú konzistenčné algoritmy (consistency enforcing algorithms).
Podstatou týchto algoritmov je orezanie priestoru kandidátov riešení na nejaký jeho
podpriestor. Ak úloha má jedno alebo viac riešení, tak tento výsledný podpriestor v ideálnom
prípade bude obsahovať iba také body, ktorých každá súradnica je súčasťou aspoň jedného
riešenia (ak úloha má iba jedno riešenie, tak tento podpriestor bude obsahovať iba jeden bod).
Ak však úloha nemá riešenie ktoré by splnilo všetky definované ohraničenia, tak priestor
kandidátov je možné redukovať na prázdny podpriestor.
Samotná redukcia je založená na filtrácii. Pri filtrácii sa vyhľadávajú také hodnoty
z domén premenných, ktoré nie sú súčasťou žiadneho riešenia. V doménach premenných sú
ponechávané iba hodnoty, ktoré sú konzistentné s definovanými ohraničeniami.
V procese filtrácie môže dochádzať nielen k redukcii domén ale aj k redukcii ohraničení,
keď ohraničenie je sprísňované – nejaká kombinácia hodnôt premenných (ktoré sú relevantné
pre dané ohraničenie) je označená ako neprípustná. Obidva tieto typy redukcie sú navzájom
previazané. Zakázanie nejakej kombinácie hodnôt môže viesť k zbytočnosti niektorých
hodnôt v doménach premenných alebo naopak zakázanie nejakej hodnoty v doméne nejakej
premennej implikuje neprípustnosť všetkých kombinácií hodnôt v ktorých daná hodnota
vystupuje.
Podobne môže dochádzať k redukcii medzi ohraničeniami rôznych árností. Zakázanie
nejakej kombinácie i premenných (sprísnenie i-árneho ohraničenia) môže mať za následok
sprísnenie (i+j)-árneho ohraničenia (vypustenie všetkých kombinácií obsahujúcich ako svoju
súčasť danú kombináciu i premenných). Alebo sprísnenie (i+j)-árneho ohraničenia môže
podnietiť vypustenie všetkých tých kombinácií z i-árneho ohraničenia, ktoré už nie sú
konzistentné s ohraničením s vyššou árnosťou.
Uvedená filtrácia môže mať reťazový charakter. Vypustenie nejakej hodnoty z domény
nejakej premennej môže prostredníctvom sprísnenia nejakého ohraničenia spôsobiť redukciu
domény inej premennej. Podobne sprísnenie jedného ohraničenia môže prostredníctvom
redukcie domény nejakej premennej mať za následok sprísnenie iného ohraničenia
definovaného nad danou premennou. Toto reťazenie môže nastať podobným spôsobom aj
medzi ohraničeniami rôznych árností. Takýto reťazový proces filtrácie sa označuje ako
šírenie ohraničení (constraint propagation).
Výhodou konzistenčných algoritmov je, že ak robia „fair“ šírenie ohraničení (t.j. každé
ohraničenie, ktorého premenné sa zmenili, je znovu aktivované), tak takéto šírenie vedie
k jedinečnému stavu siete ohraničení – a teda nezáleží na poradí, v ktorom sú jednotlivé
ohraničenia uvažované [15].
Konzistenčné algoritmy pracujú s pojmom konzistencie. Jedna z používaných podôb
tohto pojmu je (i,j)-konzistencia, kde v úlohe hodnôt i a j môžu vystupovať prirodzené čísla
z intervalu <1, n-1>, pričom ich súčet je menší alebo rovný n. Voľne by sa dalo povedať, že
sa jedná vlastne o konzistenciu podmnožín premenných z množiny všetkých premenných
V a hodnota i vlastne udáva kardinalitu týchto podmnožín. Úlohou konzistenčných
algoritmov je túto konzistenciu zabezpečiť. Konzistenčné algoritmy vlastne zabezpečia, že
nejaká subsieť siete ohraničení je konzistentná voči svojmu okoliu. Pritom pod týmto okolím
sa chápu nejaké premenné, ktoré sa nevyskytujú v danej subsieti – teda takýchto okolí pre
nejakú subsieť môže existovať vo všeobecnosti viac.
Formálne je možné povedať, že sieť ohraničení je (i,j)-konzistentná, ak platí:
Nech ľubovoľným i premenným sú priradené také hodnoty z ich domén, aby všetky
ohraničenia definované nad touto i-ticou premenných boli splnené. Pre ľubovoľných
ďalších j premenných je možné vybrať také hodnoty z ich domén, že všetky
ohraničenia definované nad vzniknutou (i+j)-ticou premenných sú splnené.
Ohraničenie definované nad i premennými je (i,j)-konzistentné, ak jeho explicitné
vyjadrenie nepripúšťa žiadnu takú kombináciu i hodnôt, ktorá nie je prípustná indukovanou
podobou daného ohraničenia (v príklade na Obrázku 1 napr. explicitná podoba C11,12
obsahuje 72 prípustných dvojíc, avšak indukovaná podoba tohto ohraničenia obsahuje
prípustných dvojíc menej – napr. vďaka ohraničeniam C11,13 a C12,13 nie sú prípustné dvojice,
obsahujúce hodnotu 8). Inak povedané, každá kombinácia hodnôt povolená explicitnou
podobou ohraničenia sa dá konzistentne rozšíriť o hodnoty ďalších j premenných.
Takto definovaná (i,j)-konzistencia teda vlastne znamená, že sieť ohraničení je práve
vtedy (i,j)-konzistentná, ak neexistuje žiadne také ohraničenie definované nad skupinou
i premenných, ktoré by nebolo (i,j)-konzistentné. Sieť ohraničení je prísne (i,j)-konzistentná,
ak je súčasne (k,j)-konzistentná pre všetky hodnoty k, pre ktoré je splnená nerovnosť 1 ≤ k ≤ i
(prísna konzistencia nejakého stupňa znamená konzistenciu daného stupňa ako aj všetkých
nižších stupňov).
Použitie konzistenčných algoritmov je potom možné chápať ako transformáciu siete
ohraničení na ekvivalentnú ale explicitnejšiu sieť, pričom existujúce ohraničenia sú použité
pre odvodenie ďalších a ich pridanie do siete. Zabezpečenie (i,j)-konzistencie potom má
podobu sprísňovania i-árnych ohraničení tak, aby boli konzistentné až s (i+j)-árnymi
ohraničeniami. Ak nejaké ohraničenie nie je explicitne dané, tak je ho možné dodefinovať –
bude jednoducho reprezentovať ohraničenie, pripúšťajúce všetky kombinácie hodnôt z domén
príslušných premenných.
Pojem (1,1)-konzistencie znamená, že v doméne ľubovoľnej premennej Vi sa nachádzajú
iba také hodnoty, ktoré ak spĺňajú ohraničenie Ci, tak sú zároveň konzistentné s doménou
ľubovoľnej inej premennej Vj, j ≠ i. To znamená, že pre každé hi  Di existuje taká hodnota hj
 Dj, že dvojica (hi,hj) neporušuje ohraničenia definované nad premennými Vi a Vj (napr. Ci,j
a Cj). Takýto typ konzistencie v sieti ohraničení zahŕňa vždy dva uzly reprezentujúce dve
premenné a preto sa nazýva hranovou konzistenciou a označuje sa AC (arc consistency).
Použitý ilustračný príklad na Obrázku 1 nie je hranovo konzistentný. Dôvodom je napr.
to, že C31 nie je konzistentné s C31,38, C31,51 a C31,61 – obsahuje totiž aj hodnoty 1, 7 a 9,
pričom však tieto hodnoty nemôžu byť konzistentne rozšírené o hodnoty premenných V38, V51
alebo V61 bez porušenia príslušného binárneho ohraničenia.
Podobne (2,1)-konzistencia znamená, že ak z domén ľubovoľných dvoch rôznych
premenných Vi a Vj je možné vybrať takú dvojicu hodnôt, ktorá neporušuje žiadne
ohraničenie, tak táto dvojica je konzistentná s doménou ľubovoľnej inej premennej V k,
pričom k ≠ i a k ≠ j. To znamená, že pre každú dvojicu (hi,hj) (hi  Di a hj  Dj) neporušujúcu
žiadne z trojice ohraničení Ci,j, Ci a Cj existuje nejaká hodnota hk  Dk taká, že trojica
(hi,hj,hk) neporušuje žiadne z ohraničení Ci,j,k, Ci,k, Cj,k a Ck.
Táto konzistencia vlastne zaručuje, že ľubovoľná kombinácia dvoch hodnôt z domén
dvoch rôznych premenných, povolená priamym ohraničením definovaným nad týmito dvoma
premennými, je súčasne povolená všetkými možnými cestami dĺžky 2 medzi týmito dvoma
premennými. Preto sa nazýva konzistenciou po ceste a označuje PC (path consistency).
Použitý ilustračný príklad nie je konzistentný po ceste. Dôvodom je napr. to, že C12,22 nie
je konzistentné s C12,22,13 a C12,13 – obsahuje totiž aj dvojicu (8,5), pričom však táto nemôže
byť konzistentne rozšírená o hodnotu premennej V13 bez porušenia príslušného ternárneho
ohraničenia.
Podobne (1,2)-konzistencia znamená, že v doméne ľubovoľnej premennej Vi sa
nachádzajú iba také hodnoty, ktoré ak spĺňajú ohraničenie Ci, tak sú zároveň konzistentné
s doménami ľubovoľných iných dvoch premenných Vj, j ≠ i a Vk, k ≠ i a k ≠ j. To znamená,
že pre každé hi  Di neporušujúce ohraničenie Ci existujú také hodnoty hj  Dj a hk  Dk, že
trojica (hi,hj,hk) neporušuje žiadne z ohraničení Ci,j,k, Ci,j, Ci,k, Cj,k, Cj a Ck.
Táto konzistencia vlastne zaručuje, že ľubovoľná hodnota z domény premennej umožní
indukovať také ohraničenie nad dvojicou ďalších dvoch premenných, ktoré je povolené
priamym ohraničením definovaným nad týmito dvoma premennými. Preto sa nazýva
konzistenciou inverznou po ceste a označuje PIC (path inverse consistency).
Použitý ilustračný príklad nie je inverzne konzistentný po ceste. Dôvodom je napr. to, že
C11 nie je konzistentné s C11,13 a C11,12,13 – obsahuje totiž aj hodnotu 8, pričom však táto
hodnota nemôžu byť konzistentne rozšírené o hodnoty premenných V12 a V13 bez porušenia
príslušného ternárneho ohraničenia.
Analogickým spôsobom je možné definovať konzistencie vyšších stupňov. Keďže (i,j)konzistencia znamená, že i-tice hodnôt je možné konzistentne rozšíriť o ďalších j hodnôt,
dosahovanie takejto konzistencie vlastne znamená nutnosť úpravy (sprísňovania) i-árnych
ohraničení. Dôležité je uvedomiť si, že definícia konzistencie vyššieho stupňa nevyžaduje
konzistenciu stupňa nižšieho a naopak. Platnosť resp. neplatnosť (i,j)-konzistencie vo
všeobecnosti nič nehovorí o platnosti alebo neplatnosti (k,l)-konzistencie pre i ≠ k alebo j ≠ l.
A teda (i,j)-konzistencia neovplyvňuje priamo domény premenných v prípade i > 1. Preto po
dosiahnutí vyššieho stupňa konzistencie musí nasledovať zabezpečenie aj nižších stupňov,
aby sa sprísnenie ohraničení vyššej árnosti rozšírilo aj na ohraničenia nižších árností a cez
unárne ohraničenia ovplyvnilo domény premenných.
Z praktických dôvodov sa konzistencie vyšších stupňov nepoužívajú kvôli vysokým
výpočtovým nárokom na ich zabezpečenie (majú exponenciálnu zložitosť). My sa budeme
venovať iba tým najjednoduchším, ktoré ovplyvňujú priamo unárne ohraničenia premenných
a tým vlastne aj priamo ich domény. Cenou za dosiahnutie iba nízkeho stupňa konzistencie je
nie vždy dostatočný stupeň redukcie ohraničení. Vo všeobecnosti totiž garanciu, že
v doménach premenných ostanú iba hodnoty participujúce aspoň na jednom z riešení, môže
poskytnúť iba. prísna (i,j)-konzistencia v prípade, že i + j = n.
Pretože existujú rôzne typy konzistencie, musia existovať aj rôzne navzájom odlišné
algoritmy, ktoré umožňujú tieto konzistencie dosahovať. Vo všeobecnosti, od toho aký typ
konzistencie daný algoritmus zabezpečuje, závisí aj zložitosť (a tým aj praktická
použiteľnosť) tohto algoritmu.
Pre zabezpečenie hranovej konzistencie je potrebné porovnávať navzájom domény dvojíc
premenných. Ak jedna doména obsahuje takú hodnotu, pre ktorú nie je možné vybrať
z domény druhej premennej žiadnu hodnotu bez toho, aby binárne ohraničenie definované nad
týmito dvoma premennými bolo porušené, tak je nutné danú hodnotu z domény prvej
premennej vypustiť.
Naviac je potrebné zohľadniť fakt, že aj keď v určitom momente je nejaká premenná V i
hranovo konzistentná voči premennej Vj, toto sa môže neskôr zmeniť po redukcii domény Dj
prislúchajúcej premennej Vj – a teda vlastne redukcia domény premennej Vj zapríčiňuje
nutnosť návratu ku kontrole premennej Vi.
Algoritmus pre zabezpečenie hranovej konzistencie môže mať viacero podôb s rôznou
zložitosťou a priestorovými nárokmi, danými jednak spôsobom implementácie a jednak
mierou redundantných testov. V literatúre je možné nájsť celý rad rôznych implementácií:
AC1 opakovane revidujúcu premenné ak nastala nejaká zmena v unárnych ohraničeniach,
AC2 realizujúcu iba jednu úplnú iteráciu cez všetky premenné [23] (je ekvivalentný
Waltzovmu filtračnému algoritmu [38]), AC3 používajúcu dynamickú frontu uzlov
čakajúcich na kontrolu [23], AC4 založenú na pojme podpory hodnôt premenných hodnotami
iných premenných [27], AC5 v generickom tvare umožňujúcu špecializáciu okrem iného aj na
AC3 a AC4 [37], AC6 narábajúcu s nutnou podporou hodnôt premenných [3], AC6+ [4]
a AC7 [14] založené na symetrii ohraničení a AC8 dekomponujúcu problém do série menších
problémov [20].
Principiálny algoritmus AC pre zabezpečenie hranovej konzistencie môže mať podobu
podľa Programu 1 (fragment reálneho kódu v jazyku Common Lisp).
(defun vyhovuju-2-hodnoty-ohraniceniu (prem1 hodn1 prem2 hodn2)
(member (cons hodn1 hodn2)
(binarne-ohranicenie prem1 prem2) :test #'equal))
(defun vyhovuje-hodnota-premennej (premenna1 hodnota1 premenna2)
(some #'(lambda (hodnota2)
(vyhovuju-2-hodnoty-ohraniceniu
premenna1 hodnota1 premenna2 hodnota2))
(unarne-ohranicenie premenna2)))
(defun vyhovuje-hodnota-premennym (premenna hodnota)
(every #'(lambda (premenna2)
(vyhovuje-hodnota-premennej premenna hodnota premenna2))
(zavisle-premenne premenna)))
(defun AC (&optional (zoznam *zoznam-premennych*))
(unless (null zoznam)
(let ((premenna (first zoznam)) zmena)
(dolist (hodnota (unarne-ohranicenie premenna))
(unless (vyhovuje-hodnota-premennym premenna hodnota)
(redukcia-unarneho-ohranicenia premenna hodnota)
(setf zmena t)))
(if (not zmena)
(AC (rest zoznam))
(AC (union (rest zoznam) (zavisle-premenne premenna)))))))
Program 1. Fragment implementácie AC algoritmu.
Algoritmus pracuje so zoznamom premenných, ktorých unárne ohraničenia je potrebné
skontrolovať (a prípadne sprísniť). Tento zoznam na začiatku obsahuje zoznam všetkých
premenných. Postupne sa z neho odoberajú premenné a kontroluje sa ich konzistencia. Ak sa
zmení unárne ohraničenie niektorej premennej, do tohto zoznamu sú pridané (ak už z neho
boli odstránené) všetky tie premenné, ktoré na danej premennej závisia prostredníctvom
binárnych ohraničení. Algoritmus končí až sa zoznam vyprázdni.
Kontrola hodnoty unárneho ohraničenia nejakej premennej Vi sa deje voči všetkým
premenným, ktoré sú závislé na Vi prostredníctvom binárnych ohraničení (iba premenné
viazané binárnym ohraničením s Vi môžu byť ovplyvnené zmenou Ci). Akonáhle sa zistí
nekonzistencia hodnoty voči niektorej z týchto premenných, kontrola končí neúspechom,
pričom kontrola danej hodnoty voči zostávajúcim závislým premenným sa vynechá.
Pri kontrole hodnoty unárneho ohraničenia nejakej premennej Vi voči inej premennej Vj
sa kontroluje iba dovtedy, pokiaľ sa nezistí konzistencia. Akonáhle sa zistí, kontrola končí
úspechom a kontrola danej hodnoty z Ci voči ostatným hodnotám z Cj sa vynechá.
Dve hodnoty (jedna z Ci a druhá z Cj) sú konzistentné vtedy, ak sa daná kombinácia
nachádza v zozname povolených dvojíc binárneho ohraničenia Ci,j.
Aj PIC algoritmus môže mať viacero podôb s rôznou zložitosťou a priestorovými
nárokmi. V literatúre je možné nájsť napr. PIC1 pamätajúci si iba vypúšťané hodnoty ale
s veľkou časovou zložitosťou a PIC2 s optimálnou časovou zložitosťou [7]. Principiálna
podoba algoritmu PIC je veľmi podobná uvedenému AC algoritmu. Rozdiel je iba v tom, že
funkcia vyhovuje-hodnota-premennym v tomto prípade kontroluje danú hodnotu voči nie
jednej ale dvom premenným, pričom daná hodnota musí vyhovovať nielen každej
z kontrolovaných premenných osobitne (teda je potrebné dvojnásobné volanie funkcie
vyhovuje-hodnota-premennej) ale aj obom súčasne a teda pribudnú dve nové funkcie
vyhovuje-hodnota-dvom-premennym (musí byť nájdená aspoň jedna kombinácia hodnôt
tých dvoch premenných podporujúca kontrolovanú hodnotu) a vyhovuju-3-hodnotyohraniceniu (kontrola voči relevantnému 3-árnemu ohraničeniu).
Existujú algoritmy, ktoré umožňujú dosiahnuť väčšiu redukciu ohraničení ako ponúka
nejaký stupeň konzistencie, avšak menšiu ako ponúka vyšší stupeň konzistencie (je to vlastne
spájanie algoritmov do kooperačných schém) [2]. Príkladom je redukovaná konzistencia po
ceste RPC (reduced path consistency) alebo alternatívy k-RPC a max-RPC [9]. RPC
algoritmus pracuje v móde ako AC (porovnáva dvojice hodnôt premenných) a len v situácii,
keď hodnota premennej Vi je konzistentná iba s jednou hodnotou z unárneho ohraničenia inej
premennej Vj, dochádza k prepnutiu do módu PC a daná dvojica hodnôt je kontrolovaná, či
môže byť konzistentne rozšírená o nejakú hodnotu tretej ľubovoľnej premennej Vk. Ak nejaká
premenná toto rozšírenie neumožňuje, na rozdiel od PC algoritmu (ktorý by sprísnil
zodpovedajúce binárne ohraničenie Ci,j) dochádza k redukcii unárneho ohraničenia Ci
vypustením pôvodne kontrolovanej hodnoty.
Na rozdiel od RPC, variant k-RPC sa prepína do módu PC keď hodnota premennej Vi je
konzistentná iba s k alebo menej hodnotami z unárneho ohraničenia inej premennej Vj (musí
byť možnosť konzistentného rozšírenia na tri hodnoty aspoň pre jednu z hodnôt premennej
Vj). Alternatíva max-RPC sa prepína do módu PC pre všetky hodnoty unárneho ohraničenia
premennej Vj, s ktorými je konzistentná skúmaná hodnota premennej Vi.
Algoritmus by sa podobal algoritmu AC. Rozdiel by bol v tom, že v tomto prípade
funkcia vyhovuje-hodnota-premennej by nekontrolovala iba či testovaná hodnota je
podporovaná nejakou hodnotou druhej premennej, ale by aj určovala koľkými hodnotami je
podporovaná. Pri počte rôznom od 1 by sa okamžite rozhodlo o úspechu alebo neúspechu.
V prípade podpory iba jednou premennou by bola volaná nová funkcia vyhovuju-dvehodnoty-premennym (dvojica hodnôt musí byť konzistentná s každou premennou zo
zoznamu všetkých ďalších premenných), následne ďalšia nová funkcia vyhovuju-dve-
(dvojica hodnôt musí byť konzistentná aspoň s jednou hodnotou tretej
premennej) a už spomínaná vyhovuju-3-hodnoty-ohraniceniu.
hodnoty-premennej
Okrem spomínaných algoritmov je možné použiť aj tzv. singletonový konzistenčný
algoritmus, ktorý pracuje systémom pokus-omyl [8]. Validitu každej hodnoty v unárnom
ohraničení premennej kontroluje tak, že dané unárne ohraničenie zúži na práve túto hodnotu
a aplikuje nejaký redukčný algoritmus. Ak dôjde v procese redukcií k vyprázdneniu nejakého
ohraničenia (signalizujúcemu neexistenciu riešenia), kontrolovanú hodnotu vypúšťa, inak ju
ponecháva. V závislosti na tom, aký algoritmus je použitý na redukciu, je možné získať napr.
SAC (singleton arc consistency), SPIC (singleton path inverse consistency) či SRPC
(singleton restricted path consistency), atď.
Principiálna podoba tohto algoritmu má tvar podľa Programu 2 (opäť fragment reálneho
kódu v jazyku Common Lisp).
(defun singleton-test-hodnoty (prem hodnota redukcny-algoritmus)
(let ((validita-hodnoty t))
(ulozenie-stavu :unarne-ohranicenia)
(nastavenie-unarneho-ohranicenia prem hodnota)
(funcall redukcny-algoritmus)
(when (vyprazdnenie-ohranicenia)
(setf validita-hodnoty nil))
(obnovenie-stavu :unarne-ohranicenia)
validita-hodnoty))
(defun singleton (algoritmus)
(do ((zmena t)) ((not zmena))
(setf zmena nil)
(dolist (premenna *zoznam-premennych*)
(dolist (hodnota (unarne-ohranicenie premenna))
(unless (singleton-test-hodnoty premenna hodnota algoritmus)
(redukcia-unarneho-ohranicenia premenna hodnota)
(setf zmena t))))))
(defun SAC () (singleton #'AC))
(defun SPIC () (singleton #'PIC))
(defun SRPC () (singleton #'RPC))
Program 2. Fragment implementácie všeobecného singletonového algoritmu a jeho využitie pre implementáciu
algoritmov SAC, SPIC a SRPC.
Je potrebné však povedať, že singletonový algoritmus realizuje mnohonásobné
opakovanie redukčného algoritmu (pre každú potenciálnu hodnotu každej premennej), čo sa
výrazne prejaví na výpočtovej náročnosti. Preto je vhodné pred jeho začiatkom znížiť počet
hodnôt premenných, na ktoré bude musieť byť aplikovaný (napr. použitím AC).
Ukážme si ako je možné použiť popísané algoritmy pre riešenie ukážkového príkladu
podľa Obrázku 1. Ten istý prípad je znázornený aj na Obrázku 2, pričom na jednotlivých
pozíciách mriežky sú zobrazené unárne ohraničenia jednotlivých premenných (na obsadenej
pozícii existuje iba jedna možnosť, na neobsadenej zatiaľ prichádzajú do úvahy všetky
možnosti).
1
4
7
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
3
6
9
7
9
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
1 2 3
4 5 6
7 8 9
8 2
5 3 9
1
4
7
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
3
6
9
4
1
4
7
1
4
7
2
5
8
2
5
8
3
6
9
3
6
9
1
4
7
1
4
7
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
3
6
9
3
6
9
1 2 3
4 5 6
7 8 9
3
1
4
7
1
4
7
1
4
7
1
4
7
1 2 3 1
4 5 6 4
7 8 9 7
6
2
5
8
2
5
8
2
5
8
2
5
8
2
5
8
1
4
7
1
4
7
1
4
7
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
3
6
9
3
6
9
3
6
9
5
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
5
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
1
4
7
1
4
7
1
4
7
1 2 3 1
4 5 6 4
7 8 9 7
1
4
7
1 2 3 1 2 3
4 5 6 4 5 6
7 8 9 7 8 9
1 2 3
4 5 6
7 8 9
1 2 3 1 2 3
4 5 6 4 5 6
7 8 9 7 8 9
1 2 3 1
4 5 6 4
7 8 9 7
6
7
1
1
8 9 5
3
6
9
3
1 2 3
6
4 5 6
9
7 8 9
3
1 2 3
6
4 5 6
9
7 8 9
3 1 2 3 1 2 3
6 4 5 6 4 5 6
9 7 8 9 7 8 9
3
1 2 3
6
4 5 6
9
7 8 9
2
1
4
7
1
4
7
1
4
7
2
5
8
2
5
8
2
5
8
2
5
8
2
5
8
3
6
9
3
6
9
3
6
9
3
6
9
3
6
9
8
9 5
7
4
2 3
5 6
8 9
Obrázok 2. Ilustračný problém s unárnymi ohraničeniami premenných.
Ak sa v takejto situácii použije AC algoritmus, tak napr. pre C17 prebehne redukcia.
Postupne budú vypustené hodnoty: 1 pre chýbajúcu podporu v C38, 2 kvôli C14, 4 pre C97, 5
pre C16, 6 pre C18, 7 pre C28, 8 pre C13 a 9 pre C57. Takýmto spôsobom bola C16 zredukovaná
na jednu hodnotu a následne bolo možné hodnotu 3 vypustiť z ohraničení všetkých
premenných reprezentujúcim ten istý riadok, stĺpec a štvorec ako prislúcha C16. Výsledkom
bolo orezanie unárnych ohraničení podľa Obrázku 3.
V situácii podľa Obrázku 3 už použitie AC neprináša ďalšiu redukciu ohraničení. Ak sa
použije napr. RPC, tak redukcia unárnych ohraničení môže pokračovať. Pri skúmaní hodnoty
8 z C77 voči C27 sa zistila podpora iba hodnotou 2. Keďže podpora bola iba jednou hodnotou,
prepol sa mód a začalo sa skúmať, či kombinácia 8 z C77 a 2 z C27 je konzistentná voči
unárnemu ohraničeniu každej zo zvyšných premenných. Keďže z C87 nebolo možné danú
kombináciu hodnôt validne doplniť žiadnou hodnotou, tak hodnota 8 bola vypustená z C77.
Ďalšími redukciami sú napr. vypustenie 2 z C67 (rovnaký dôvod ako bol pre vypustenie 8
z C77), 6 z C67 (v konflikte s aktuálnym C77), atď. Postupnou redukciou sa dospeje do situácie
na Obrázku 4.
1
4
1
8 2
5 3 9
7
1 2
4
6
2
4
9
2
6
7
2
4 5 6
8
7
9
1
3
2
6 4
9 7
2
5 3 6
7
1
1
8 9 5
1
6 4
8
8
1 2 3 1 2
6 4
3
6
1
4
3
6
8
2
5
8
2
4
7
1
6 4
6 4
9 7
6
7 8 9
9
2
4
2
4
9
2
6
9
4
1 2 3 1 2
6 4 5
4
4
2
3
4
6 4
6 4
9 7 8
7 8
7
2
6 4 5
8
1 2 3 1 2 3
5
8
8 9
1 2 3 1 2 3
8
1
4
7
1
4
2
4
6
4
2 3
6
2 3
1
1
1 2
2
4 5 6 4
6 4
6
6 4
7
7
7
7
1
1
1
3
6
6
6
7
7 8
7
8
1
1
3 1
3
2
2 3
4
4
4
8
8 9
9
8
8
1 2
1
1
3
2 3 1 2 3
6
6
6
7
9 7 8
7
9
8
8
9 5
7
2
6
5
4
Obrázok 3. Ilustračný problém s unárnymi ohraničeniami premenných po aplikovaní algoritmu AC.
Ak by sa však v Obrázku 3 namiesto RPC použilo PIC, tak napr. pri skúmaní C37 sa
každá hodnota z tohto ohraničenia bude kontrolovať voči dvojiciam premenných aby sa
overilo, či je s unárnymi ohraničeniami týchto premenných konzistentná. Hodnota 2 bude
vypustená, pretože pri porovnaní voči C27 a C87 nebolo možné vybrať takú kombináciu
rôznych hodnôt tak, aby obe boli rôzne od hodnoty 2. Z analogického dôvodu bolo potrebné
vypustiť aj hodnotu 8 z C37.
Pokračovať v redukcii unárnych ohraničení v situácii ilustrovanej Obrázkom 4 možno
napr. prostredníctvom algoritmu max-RPC. Pri kontrole validity hodnoty 4 z C49 voči C39 je
síce táto hodnota podporovaná dvomi hodnotami z C39, avšak ani v jednom prípade nie je
možné rozšírenie o tretiu hodnotu buď z C19 alebo C29 (v závislosti na použitej hodnote z C39).
Toto vedie k vypusteniu hodnoty 4 z C49. Z rovnakého dôvodu dôjde k vypusteniu hodnoty 4
aj z ohraničenia C59.
Redukcia ohraničení by mala inú podobu, ak by v situácii na Obrázku 4 bol použitý
algoritmus SAC. Napríklad je možné začať skúmať hodnotu 2 v C27. Ak by sa C27
zredukovalo iba na túto hodnotu, tak pre zabezpečenie hranovej konzistencie je nutné
redukovať C29 na hodnotu 4 (teraz hodnota 2 nemá oporu v C27) a C39 na hodnotu 9 (hodnota
2 nemá oporu v C27 a hodnota 4 zase v C29). Následkom úprav C29 a C39 bude C19 redukovaná
na prázdnu množinu – a to je signál, že pôvodný predpoklad (redukcia C27 na hodnotu 2) bol
chybný a teda hodnota 2 je odstránená z C27. Opakovaným použitím SAC sa získa situácia
podľa Obrázku 5.
1
4
1
8 2
5 3 9
1
4
7
1
4
5 3 6
7
5 1
3
1
7
8 9 5
9
7
8
4
2
6 9 5
6
7
5
4
7
1 2
4
6
2
4
9
2
6
7
2
4 5 6
8
1
2
6 4
9 7
2
4
7
1
6 4
1 2 3 1 2
6 4 5
1
1
4 5 6 4
6 4
9 7
4
3
6
2
4
9
1
4
6
9
2
4
7
3 1
4
8 9
1
9 7 8
7
4
6
4
2 3
6
2 3
1 2
6 4
6
1
7 8
1
4
8
1
2
6
1
7 8 9 7
6
8
6
8
2
2
1
4
8
7
1 2 3 1 2 3
5
8
8 9
1 2 3 1 2 3 1 2
2
8
8
1 2 3 1 2
6 4
1
9
1
6 4
3
4
6 4
6 4
9 7 8
7 8
7
2
6 4 5
3
4
4
3
3
2
2 3
9
3
6
9
8
8
2 3 1 2 3
8
Obrázok 4. Ilustračný problém s unárnymi ohraničeniami premenných po aplikovaní algoritmov AC a RPC.
1
4
1
8 2
5 3 9
1
4
7
1
4
5 3
8
5
3
1
7
8 9
9
7
4
2
6
6
2
5
4
7
1 2
4
6
2
4
9
2
6
7
2
4 5
8
2
6 4
9 7
2
8
1 2
1 2
6 4
3
8
1
3 1
5
8
2 3
3
4
6 4
6 4
9 7 8
7 8
7
1
4
1
1
4 5 6 4
1
1
7
7 8
1
4
8
3
8 9
2 3
7
1
6 4
9 7
3
6
1 2
6 4
6
1
1
4
7 8 9 7
7
3 1
4
8 9
2
9 7 8
9
6
6
8
6
2
4 5
1 2 3 1 2
6 4 5
1
1
6 4
7
3
3
9
3
6
9
6
7
1
4
9
2
4
2
4
9
2
6
5 3
8
9 5
7
1
4
2
4
3
8
3
8
Obrázok 5. Ilustračný problém s unárnymi ohraničeniami premenných po aplikovaní algoritmov AC, RPC a
SAC.
Ak sa v situácii podľa Obrázku 5 použije SPIC, tak možno napr. redukovať C15 na
hodnotu 4. Následné skúmanie hodnoty 4 v C25 spôsobí jej vypustenie (nebude možné ju
konzistentne rozšíriť o ďalšie dve hodnoty ak jedna z nich bude braná z C15). Podobný osud
postihne aj hodnotu 4 v C55 a C65. Ak potom sa bude uvažovať ľubovoľná hodnota
z aktuálneho C25, tak sa nebude dať doplniť žiadnou kombináciou hodnôt z C55 a C65 – a teda
C25 sa vyprázdni. Znamená to, že prvotné zúženie C15 na hodnotu 4 nie je možné a táto
hodnota je vypustená z C15. Z úplne rovnakého dôvodu je nutné vypustiť z C15 aj hodnotu 1.
Pre porovnanie výkonnosti jednotlivých algoritmov boli použité problémy z [16].
V ponuke bolo 100 úloh v štyroch kategóriách obtiažnosti. Ako doplnok bolo použitých aj 10
úloh z [21], zaraďovaných medzi najťažšie doposiaľ objavené inštancie daného hlavolamu.
Na základe priemerného stupňa orezania unárnych ohraničení (a tým pádom aj domén
premenných) boli jednotlivé algoritmy zoradené takto: AC < RPC = PIC < max-RPC < SAC
< SRPC = SPIC < Smax-RPC. V tomto prípade teda AC dosiahol najmenší stupeň redukcie
a Smax-RPC zase najväčší. Na daných úlohách RPC mal rovnakú výkonnosť ako PIC (a teda
aj SRPC ako SPIC). Toto zodpovedá zoradeniu algoritmov napr. podľa [9]. Rozdiel bol iba
v tom, že PIC dosahuje minimálne také orezanie ako RPC (teda môže aj väčšie, nielen
rovnaké ako to bolo v našom prípade).
Na súbore 100 úloh z [16] dokázali jednotlivé algoritmy riešiť problém nasledovne: AC
úplne vyriešil 23 úloh, RPC a PIC vyriešili po 46 úloh, max-RPC 56 úloh, SAC bol úspešný
v 97 prípadoch a SRPC, SPIC a Smax-RPC mali sto percentnú úspešnosť. Pri použití [21] boli
všetky uvedené algoritmy neúspešné – hoci bol dosiahnutý určitý stupeň redukcie, ich
schopnosti redukovať ohraničenia nestačili ani na jednu z úloh. Prvým úspešným algoritmom
bol až DSAC (double singleton arc consistency), algoritmus analogický k SAC ibaže
redukujúci binárne ohraničenia. Tento už vyriešil všetkých desať úloh (a taktiež všetkých sto
z predchádzajúceho súboru).
4 Stochastické prehľadávanie v akcii
Existuje pomerne veľký počet algoritmov založených na stochastických princípoch, ktoré je
možné použiť pre riešenie úloh s ohraničeniami. Ako príklad použijeme evolučné algoritmy
(evolutionary algorithms). Tieto algoritmy tvoria širokú skupinu prístupov a smerov, ktorých
jednotiacim prvkom je využívanie princípov prirodzeného výberu a génovej dedičnosti (od
snahy presne kopírovať tieto mechanizmy cez využívanie ich zjednodušených podôb až po
iba vzdialenú inšpiráciu týmito princípmi).
Hlavnými impulzmi (aj keď to neboli prvé impulzy v tejto oblasti) pre rozvoj týchto
algoritmov sa na prelome šesťdesiatych a sedemdesiatych rokov stali práce I. Rechenberga
[30] a H.P. Schwefela [32] v oblasti riešenia optimalizačných úloh z oblasti hydrodynamiky,
práce L.J. Fogela, A.J. Owensa a M.J. Walsha [12] v oblasti riešenia predikčných úloh a práce
J.H. Hollanda [18] z oblasti skúmania fenoménu adaptácie v prírode a jeho prenosu do
umelých systémov. Tieto práce sa stali hybným momentom pre vznik troch samostatných
smerov, ktoré sa spočiatku vyvíjali izolovane, neskôr však dochádza medzi nimi ku kontaktu
a vzájomnému prelínaniu ideí. Následkom toho je vznik algoritmov spájajúcich prvky typické
pre rôzne smery. Popisy základných prvkov týchto algoritmov je možné nájsť on-line napr.
v prehľadovej publikácii [24].
Nedávny rozvoj evolučných algoritmov je spájaný ako s rozvojom teórie tak aj
s aplikovaním týchto algoritmov na najrozličnejšie problémy. Špeciálne s ich využívaním pre
riešenie úloh s ohraničeniami je spájané meno Zbigniewa Michalewicza [26] (oblasť
numerickej optimalizácie) a Agostona E. Eibena [11] (oblasť kombinatorickej optimalizácie).
Pre riešenie kombinatorických problémov s ohraničeniami je možné použiť takú podobu
evolučného algoritmu, ktorá je vlastne jednou z populačných verzií algoritmu lokálneho
prehľadávania LS (local search). Domény premenných vlastne definujú priestor
prehľadávania. Je to priestor všetkých potenciálnych riešení – všetkých možných kombinácií
hodnôt z domén premenných. LS generuje a skúma rozličné kombinácie priradení hodnôt
z domén premenných týmto premenným. Každá takáto kombinácia je považovaná za
kandidáta riešenia a cieľom je nájsť takého kandidáta, ktorý je skutočným riešením – teda
priradenia premenných neporušujú žiadne z existujúcich ohraničení.
Nepopulačný LS pracuje vždy iba s jedným kandidátom. V inicializačnej fáze je
vygenerovaný počiatočný kandidát, ktorý sa stáva aktuálnym kandidátom. Ďalšie
prehľadávanie prebieha iteračným spôsobom. V každej iterácii je vyberaný nový kandidát,
pričom výber sa deje z lokálneho okolia aktuálneho kandidáta. Vybraný nový kandidát sa
následne stáva aktuálnym kandidátom a algoritmus prechádza na ďalšiu iteráciu. Pri
populačnej verzii je aktuálny kandidát nahradený populáciou (množinou) kandidátov
a v každej iterácii je vyberaná populácia nových kandidátov.
Principiálny EA algoritmus môže mať nasledovnú podobu uvedenú v Programe 3
(fragment reálneho kódu v jazyku Common Lisp).
(defun EA ()
(let ((populacia (vyhodnotenie (inicializacia-kandidatov))))
(dotimes (i *max-gen* nil)
(setf populacia
(vyhodnotenie (generovanie-kandidatov populacia)))
(when (some #'najdene-riesenie-p populacia)
(return-from EA populacia)))))
(defun generovanie-kandidatov (populacia)
(let ((nova-populacia nil))
(dotimes (i *velkost-populacie*)
(push (vyber-z-okolia (zuzenie-populacie populacia))
nova-populacia))
nova-populacia))
Program 3. Fragment implementácie EA algoritmu.
Na začiatku vo funkcii EA je populácia kandidátov inicializovaná tak, že požadovaný
počet kandidátov je vygenerovaný náhodným spôsobom a títo kandidáti sú následne
ohodnotení. Každému kandidátovi je priradená vhodnosť – číslo udávajúce ako dobre tenktorý kandidát spĺňa existujúce ohraničenia. V následných iteráciách sú vytvárané nové
a nové populácie kandidátov. Ak niektorá novovytvorená populácia obsahuje skutočné
riešenie, tak sa iteračné hľadanie ukončí. Ak skutočné riešenie nie je objavené, tak po
vykonaní predpísaného počtu iterácií je neúspech hľadania signalizovaný symbolom nil.
Generovanie novej populácie začína vytvorením prázdnej populácie, do ktorej sa
postupne pridávajú noví kandidáti. Vytvorenie každého nového kandidáta sa deje rovnakým
spôsobom: najprv sa z aktuálnej populácie vyberie podmnožina kandidátov a následne sa
z okolia týchto vybratých kandidátov vyberá nový kandidát.
Reprezentácia kandidátov, spôsob určovania vhodnosti kandidátov, zúženie populácie na
nejakú jej podmnožinu, definícia okolia kandidátov a operátory pre výber kandidátov z tohto
okolia ako aj riadiace parametre a ich nastavenie sú špecifické pre konkrétnu inštanciu
evolučného algoritmu. Popísaný algoritmus vlastne reprezentuje algoritmický rámec, ktorý
možno ďalej špecializovať vhodnou voľbou uvedených prvkov algoritmu.
Ilustrujme to na dvoch príkladoch. Prvým bude algoritmus založený na usporiadaní
pozícií mriežky. Ak kandidáti budú reflektovať iba tie pozície v mriežke, ktoré je potrebné
ešte doplniť, tak v prípade podľa Obrázku 1 každý kandidát musí zohľadniť 56 voľných
pozícií. Predpokladajme, že každý kandidát bude reprezentovať jedno z možných usporiadaní
týchto voľných pozícií. Príkladom takéhoto kandidáta je poradie pozícií mriežky
87, 17, 27, 37, 39, 19, 29, 26, ..., 21
(2)
kde prvá číslica v každej dvojici označuje riadok a druhá zase stĺpec, pričom celkovo toto
usporiadanie obsahuje 56 rôznych dvojíc.
Určenie vhodnosti takéhoto kandidáta nie je možné priamo, ale najprv je potrebné z jeho
reprezentácie skonštruovať priradenie hodnôt premenným a až následne ohodnotiť toto
priradenie. Postupne sa uvažujú jednotlivé pozície podľa zadaného poradia. Pre každú voľnú
pozíciu sa skúsi priradenie hodnoty 1 na danú pozíciu. Ak to nie je možné (lebo by došlo
k porušeniu niektorého z binárnych ohraničení definovaných nad premennou,
zodpovedajúcou skúmanej pozícii), tak sa skúsi priradenie hodnoty 2, atď. Postupne sa
skúšajú jednotlivé hodnoty 1 až 9 (stále v tom istom poradí). Akonáhle niektorá zo skúšaných
hodnôt môže byť priradená, tak sa toto priradenie vykoná a nasledujúce hodnoty sa už
neskúšajú. Následne sa prechádza na ďalšiu pozíciu v poradí. Ak sa pre skúmanú pozíciu
nenájde ani jedna vhodná hodnota, tak pozícia ostáva neobsadená a opäť sa prechádza na
nasledujúcu pozíciu v poradí. Počet neobsadených pozícií bude použitý ako vhodnosť daného
jedinca. To znamená, že algoritmus vlastne rieši minimalizačný problém, keď hľadané
riešenie je reprezentované kandidátom transformovateľným na priradenie všetkých
premenných bez nutnosti ponechávať niektoré pozície neobsadené.
Tento postup by pri použití pre hore uvedené poradie (2) konštruoval nasledovné
priradenie: hodnotu 2 pre pozíciu 87 pretože hodnota 1 je už na pozícii 47; hodnotu 3 pre
pozíciu 17 pretože 1 je už na 47 aj na 38 a 2 bola v predchádzajúcom kroku priradená pozícii
87; hodnotu 8 na pozíciu 27; hodnotu 5 na 37; 2 na 39 a 4 na 19. Ďalším krokom by malo byť
určenie vhodnej hodnoty pre pozíciu 29, avšak keďže každá z hodnôt by spôsobila porušenie
aspoň jedného ohraničenia, tak táto pozícia musí ostať prázdna. Pokračovalo by sa hodnotou 1
na 26 atď.
Vhodnosť kandidátov, zaradených v populácii, sa použije pri zužovaní populácie na
dvoch kandidátov. Toto sa deje na pravdepodobnostnom základe, pričom kandidát s menším
počtom neobsadených pozícií je vyberaný s väčšou pravdepodobnosťou než kandidát
s viacerými neobsadenými pozíciami. Je to možné realizovať náhodným výberom dvoch
kandidátov z aktuálnej populácie a porovnaním ich vhodností, pričom je vybraný kandidát
s menšou hodnotou.
Z okolia vybraných dvoch kandidátov sa vyberie nový kandidát a zaradí sa do novej
populácie. Pre definovanie okolia sa v evolučných algoritmoch používajú operátory – do
okolia patria všetci tí kandidáti, ktorých je možné vytvoriť pomocou týchto operátorov.
Používajú sa dva typy operátorov – mutácia a kríženie.
Prvý z nich vytvára nových kandidátov zo štruktúry jedného kandidáta, zatiaľ čo druhý
pre tvorbu nových potrebuje dvoch kandidátov na svojom vstupe. Cieľom krížiaceho
operátora je kombinovať štruktúrne prvky dvoch kandidátov do nových kombinácií tak, aby
výsledný nový kandidát obsahoval časti pochádzajúce z oboch vstupných kandidátov. Jednou
z možností je OX kríženie, ktoré chápe usporiadania, vytvárajúce kandidátov, ako cyklické –
po poslednej pozícii v poradí nasleduje prvá pozícia. Nový kandidát sa buduje tak, že
z jedného usporiadania sa vyberá súvislý segment, určený dvomi náhodne generovanými
deliacimi bodmi. Zvyšné miesta v usporiadaní sa doplnia z druhého usporiadania tak, aby sa
čo najviac zachovalo relatívne poradie v tomto druhom usporiadaní.
Pre ilustráciu okrem vyššie uvedeného usporiadania podľa (2) uvažujeme ešte druhé
usporiadanie
11, 12, 15, 17, 19, 21, 25, ..., 98, 99.
(3)
Nech boli náhodne generované deliace body medzi druhým a tretím prvkom usporiadania
ako aj medzi šiestym a siedmym. Zo štruktúry prvého usporiadania (2) sa tak prenáša do
výsledného kandidáta segment: 27, 37, 39, 19. Pred tento segment je potrebné doplniť dve
pozície a zaň zase 50 pozícií z druhého usporiadania (3). Keďže poradie sa chápe cyklicky,
tak druhé usporiadanie možno súčasne zapísať ako
25, ..., 98, 99, 11, 12, 15, 17, 19, 21
(4)
pričom sa začína prvkom za druhým deliacim bodom (t.j. za koncom fragmentu, preneseného
z (2)). Z takto vyjadreného poradia je potrebné vypustiť tie pozície mriežky, ktoré už sú
v novom kandidátovi (boli prenesené z prvého usporiadania), čím sa získa
25, ..., 98, 99, 11, 12, 15, 17, 21.
(5)
Takto upraveným poradím sa cyklicky doplní nový kandidát do výsledného tvaru postupnosti
pozícií
17, 21, 27, 37, 39, 19, 25, ..., 98, 99, 11, 12, 15.
(6)
Cieľom mutačného operátora je dosiahnuť, aby nový kandidát obsahoval nielen prvky
nachádzajúce sa vo vstupnom usporiadaní ale aj prvky, ktoré v ňom pôvodne neboli.
Zámerom je malá zmena pôvodného usporiadania. Jednoduchou možnosťou malej zmeny je
vzájomná výmena dvoch pozícií mriežky v usporiadaní jedinca, pričom tieto dve pozície sa
vyberú náhodne. Takúto výmenu je možné niekoľkokrát zopakovať – a keďže vhodný počet
výmen v rámci jedného usporiadania nie je očividný, je možné voľbu tohto počtu ponechať
opäť na náhodu.
Pri vyberaní nových jedincov je možné používať krížiaci a mutačný operátor
v rozličných kombináciách. Najčastejší spôsob použitia je použitie oboch operátorov na
pravdepodobnostnom základe.
Druhým ilustračným príkladom algoritmu bude algoritmus založený na hodnotách
vložených do mriežky. Ak kandidáti budú reflektovať všetky pozície v mriežke, ktoré v nej
existujú, tak každý kandidát musí zohľadniť 81 pozícií. Predpokladajme, že každý kandidát
bude reprezentovať jedno z možných priradení hodnôt všetkým pozíciám mriežky. Príkladom
takéhoto kandidáta je poradie hodnôt
3, 1, 8, 2, 3, 5, 9, 6, 4, ..., 4, 2, 4
(7)
kde prvá hodnota reprezentuje hodnotu na pozícii 11, druhá na pozícii 12, tretia na 13, ...,
posledná zodpovedá hodnote umiestnenej na pozícii 99. Tieto hodnoty rešpektujú prvotné
priradenie hodnôt (teda pre úlohu podľa Obrázku 1 na treťom mieste musí byť hodnota 8, na
štvrtom 2, na šiestom hodnota 5, atď.), variácie sú možné iba v prípade voľných pozícií.
Určenie vhodnosti takéhoto kandidáta je teraz možné priamo, bez nutnosti vytvárať
dodatočné konštrukcie. Jednoducho sa skontrolujú všetky binárne ohraničenia, či hodnoty na
relevantných pozíciách spĺňajú alebo porušujú dané ohraničenia. Tak pri kontrole jedinca
podľa (7) je zrejmé, že hodnota 3 na pozícii 11 porušuje C11,15 a C11,23 a hodnota 4 na 19
porušuje C19,99. O tom, či hodnota 1 na pozícii 12 porušuje nejaké ohraničenie alebo nie,
rozhodnú hodnoty, ktoré nie sú viditeľné v (7). Počet porušených binárnych ohraničení bude
použitý ako vhodnosť daného jedinca. To znamená, že algoritmus opäť rieši minimalizačný
problém, keď hľadané riešenie je reprezentované kandidátom s nulovým počtom porušených
binárnych ohraničení.
Rovnako ako v predchádzajúcej verzii algoritmu, aj teraz sa vhodnosť kandidátov,
zaradených v populácii, použije pri zužovaní populácie – tentoraz však iba na jedného
kandidáta. Opäť sa toto deje na pravdepodobnostnom základe, pričom kandidát s menším
počtom porušených ohraničení je vyberaný s väčšou pravdepodobnosťou než kandidát
s viacerými porušenými ohraničeniami (v základnej verzii všetky ohraničenia majú rovnakú
váhu, avšak sú možné aj verzie s rôznymi váhami, dokonca s dynamickým určovaním váh
ohraničení). Obdobne k predchádzajúcej verzii algoritmu, je to možné realizovať náhodným
výberom dvoch kandidátov z aktuálnej populácie a porovnaním ich vhodností, pričom je
vybraný kandidát s menšou hodnotou.
Z okolia vybraného kandidáta sa vyberie nový kandidát a zaradí sa do novej populácie.
Pre definovanie okolia sa teraz použije iba jeden operátor – mutácia. Meniť sa pritom môžu
iba tie hodnoty v kandidátovi, ktoré zodpovedajú hodnotám priradeným voľným pozíciám
mriežky. Hodnoty definované úlohou sa nemenia. V úlohe mutačného operátora sa používa
operátor [#, #, #], kde znak na prvej pozícii reprezentuje počet menených hodnôt
v kandidátovi, druhá pozícia zase spôsob výberu hodnôt, ktoré sa majú meniť, a tretia pozícia
vyber hodnôt ktoré nahradia menené hodnoty.
Počet menených hodnôt môže byť vopred pevne daný (napr. [3, #, #]) alebo jeho výber
sa nechá na náhodu. Príkladom môže byť [r(3), #, #] reprezentujúci náhodný výber hodnoty
z {1, 2, 3} s použitím uniformnej distribúcie pravdepodobnosti.
Voľba pozícií kandidáta, ktoré majú byť zmenené, má vo všeobecnosti dva základné
tvary: [#, r, #] a [#, b, #]. Prvý znamená náhodný vyber s rovnakou pravdepodobnosťou pre
všetky pozície kandidáta (random), zatiaľ čo druhý signalizuje použitie nejakej heuristiky
(bias). Jedna z možných heuristík je určiť váhu každej pozície v mutovanom kandidátovi,
pričom váha je daná ako počet binárnych ohraničení, ktoré sú porušené hodnotou na danej
pozícii kandidáta. Keďže pre mutovanie sa vyberú pozície s najväčšou váhou, vždy sa menia
tie hodnoty, ktoré majú najväčší podiel na porušovaní existujúcich ohraničení.
Podobne voľba nových hodnôt, ktoré majú nahradiť menené hodnoty, má vo
všeobecnosti dva základné tvary: [#, #, r] a [#, #, b]. Prvý opäť znamená náhodný výber
s rovnakou pravdepodobnosťou pre všetky hodnoty z príslušnej domény (random), zatiaľ čo
druhý opäť signalizuje použitie nejakej heuristiky (bias). Možnou heuristikou je váženie
hodnôt podľa toho, koľko ohraničení porušujú.
Keďže evolučný algoritmus je algoritmom stochastickým, tak neexistuje záruka nájdenia
riešenia aj keď toto riešenie skutočne existuje (a najmä v podmienkach obmedzeného času).
Pre ľahšie problémy sa zvyčajne nájde riešenie skoro v každom behu, zatiaľ čo pre problémy
obtiažnejšie je riešenie nachádzané menej často. Pri testovaní je preto každý problém riešený
niekoľkokrát pri rôznych počiatočných nastaveniach generátora náhodných čísel.
Výkonnosť algoritmu je často meraná prostredníctvom dvoch charakteristík. Miera
úspešnosti algoritmu je udávaná ako počet úspešných hľadaní voči počtu všetkých hľadaní pri
opakovanom riešení toho istého problému. Efektívnosť algoritmu sa navonok prejavuje ako
rýchlosť nájdenia riešenia. Táto rýchlosť môže byť meraná napr. počtom potrebných iterácií
algoritmu a určuje sa ako priemerná hodnota z viacerých realizácií.
Prezentovaný variant evolučného algoritmu, založeného na usporiadaní pozícií mriežky,
bol pri testovaní použitý s populáciou skladajúcou sa zo sto kandidátov, pričom jedno
hľadanie riešenia bolo obmedzené na 5000 iterácií. Riešenie každého problému bolo
opakované 50 krát. Pri porovnaní výkonnosti pri riešení problémov z [16] boli dosiahnuté
výsledky, ktoré sú prezentované na Obrázku 6.
Horná časť obrázku prezentuje histogram úspešnosti, ktorý je pomerne vyrovnaný. Pri
riešení 24 rôznych mriežok bol algoritmus schopný nájsť riešenie vo viac než 40 pokusoch
z celkového počtu 50 pokusov, pričom v siedmich prípadoch bol úspešný v každom pokuse.
Na druhej strane mal problémy s 26 mriežkami, pri ktorých bol úspešný maximálne v 10
pokusoch, pričom v prípade dvoch mriežok nedokázal nájsť riešenie ani raz. Pri zohľadnení
obtiažnosti jednotlivých mriežok, uvádzaných v použitom zdroji, pri riešení ľahkých úloh
algoritmus dosahoval úspešnosť 100%, pri riešení stredných úloh 75%, pri ťažkých úlohách
43% a pri najťažších (zákerných) úlohách bola jeho úspešnosť iba 18%.
Dolná časť obrázku reprezentuje histogram potrebného priemerného počtu iterácií pre
riešenie jednotlivých úloh (vo výpočte sa v prípade, že v niektorom behu algoritmus
nedokázal vyriešiť úlohu, uvažuje maximálny počet 5000 iterácií). Je zrejmé, že prevažujú
vyššie počty potrebných iterácií nad nižšími, teda častejšie sa objavovali dlhšie doby hľadania
ako kratšie. V prípade 37 mriežok bol potrebný priemerný počet viac než 4000 iterácií, zatiaľ
čo iba v prípade 13 mriežok bolo riešenie nájdené v priemere skôr než za tisíc iterácií.
Pri použití [21] bol algoritmus pri rovnakom nastavení menej úspešný – iba pri polovici
úloh dokázal nájsť aspoň raz riešenie, avšak ani pre jednu úlohu nedokázal nájsť riešenie viac
ako dva razy.
n
25
15
5
0-10
11-20
21-30
31-40
41-50
úspešnosť
0-1
1-2
2-3
3-4
4-5
efektívnosť
(v tis.)
n
30
15
Obrázok 6. Výsledky dosiahnuté evolučným algoritmom založeným na usporiadaní pozícií mriežky.
Prezentovaný variant evolučného algoritmu, založeného na hodnotách vložených do
mriežky, bol pri testovaní tiež použitý s populáciou skladajúcou sa zo sto kandidátov,
obmedzením riešenia na 5000 iterácií a opakovaním riešenia každého problému 50 krát. Pre
testovanie bol použitý [r(8), b, r] operátor, ktorý sa pri pokusoch na ľahkej inštancii
hlavolamu osvedčil najviac. Pri porovnaní výkonnosti pri riešení problémov z [16] boli
dosiahnuté výsledky, ktoré sú prezentované na Obrázku 7.
Histogram úspešnosti je menej vyrovnaný ako v predchádzajúcom prípade a signalizuje
zhoršenie úspešnosti. Iba pri riešení 6 rôznych mriežok bol algoritmus schopný nájsť riešenie
vo viac než 40 pokusoch z celkového počtu 50 pokusov, pričom v štyroch prípadoch bol
úspešný v každom pokuse. Na druhej strane mal problémy až s 41 mriežkami, pri ktorých bol
úspešný maximálne v 10 pokusoch, pričom v prípade jednej mriežky nedokázal nájsť riešenie
ani raz. Pri riešení ľahkých úloh algoritmus dosahoval úspešnosť 100%, pri riešení stredných
úloh 51%, pri ťažkých úlohách 28% a pri najťažších (zákerných) úlohách bola jeho úspešnosť
iba 12%.
Histogram potrebného priemerného počtu iterácií pre riešenie jednotlivých úloh tiež
odráža zhoršenie výkonnosti. Počet mriežok, kde bol potrebný priemerný počet viac než 4000
iterácií, sa zvýšil na 50, zatiaľ čo iba v prípade 8 mriežok bolo riešenie nájdené v priemere
skôr než za dva tisíc iterácií.
Rovnako ako v predchádzajúcom prípade, pri použití [21] bol algoritmus pri rovnakom
nastavení menej úspešný – avšak jeho výkon bol lepší ako výkon verzie algoritmu založeného
na usporiadaní pozícií mriežky. Dokázal nájsť aspoň raz riešenie pre osem mriežok, pričom
pre niektoré z nich dokázal nájsť riešenie tri razy.
n
35
25
15
5
0-10
11-20
21-30
31-40
41-50
úspešnosť
0-1
1-2
2-3
3-4
4-5
efektívnosť
(v tis.)
n
45
30
15
Obrázok 7. Výsledky dosiahnuté evolučným algoritmom založeným na hodnotách vložených do mriežky.
5 Sila znalostného prístupu
Podstatou tohto prístupu k riešeniu úloh je orientácia na konkrétne znalosti o tom-ktorom
riešenom probléme. Keďže takýmto spôsobom je možné zohľadniť špecifiká riešeného
problému a nielen jeho všeobecné charakteristiky, spoločné pre celú skupinu úloh nejakého
typu, tak je možné očakávať vytvorenie vysoko efektívneho postupu pre nájdenie riešenia
tohto problému.
Korene znalostných prístupov siahajú do druhej polovice šesťdesiatych rokov, keď sa
stali základom pre tvorbu systémov označovaných ako expertné [29]. V počiatočnom období
sa ako vedúci princíp používal prenos znalostí (knowledge transfer), ktorý neumožňoval
diferenciáciu. Zmena nastala v osemdesiatych rokoch a bola inicializovaná prácou Allena
Newella [28]. Táto zmena súvisela s prechodom k princípu modelovania znalostí (knowledge
modelling). Postupne začali vznikať znalostné modely rozlišujúce rozličné typy znalostí,
pričom každý z týchto typov bol charakterizovaný nie spôsobom reprezentácie alebo zdrojom
pôvodu, ale úlohou, ktorú hral v uvažovanej doménovej oblasti. Vznik týchto prvých modelov
je spojený s takými menami ako William J. Clancey [6], Balakrishnan Chandrasekaran [19]
a Luc Steels [33].
Jedným z výsledkov neskoršieho vývoja v tejto oblasti sú viacvrstvové znalostné modely.
Príkladom môže byť štvorvrstvový expertízny model z KADS metodológie alebo trojvrstvový
znalostný model podľa jej nasledovníka – metodológie CommonKADS [31]. Tieto modely
reprezentujú prostriedok uľahčujúci ako samotné získavanie znalostí tak aj prenos týchto
znalostí pre riešenie iných úloh.
Vrstvy týchto modelov je možné v podstate rozdeliť do dvoch skupín. Doménová vrstva
obsahuje konkrétne znalosti týkajúce sa riešeného prípadu. Ostatné vrstvy okrem iného
obsahujú napr. inferenčnú úroveň obsahujúcu znalosti o inferenciách a znalostných objektoch
nad ktorými tieto inferencie sú realizované. Inferenčná vrstva tak reprezentuje akúsi šablónu
uvažovania, ktorá nie je závislá na konkrétnom príklade, a teda môže byť znovu použitá aj pre
iné problémy. Doménová vrstva reprezentuje použitie takejto šablóny pre riešenie
konkrétneho problému. Jej úlohou je definovať obsah jednotlivých objektov, použitých na
všeobecnej inferenčnej úrovni – znalostí pre realizáciu jednotlivých inferenčných krokov,
znalostných štruktúr nad ktorými je realizovaná inferencia a podporných znalostí.
Výhodou takéhoto prístupu je, že ak sa návrhárovi podarí identifikovať typ úlohy ktorú je
potrebné riešiť, potom voľba nejakého modelu pre riešenie takéhoto typu úloh mu jasne
špecifikuje, ktoré znalosti z doménovej oblasti je potrebné získať.
Pri použití princípu znalostného modelovania pre riešenie úloh s ohraničeniami rolu
znalostných štruktúr, nad ktorými je realizovaná inferencia, hrajú premenné a ich domény.
Výsledkom nejakého inferenčného kroku môže byť napr. naviazanie premennej na nejakú
hodnotu, uvoľnenie premennej, alebo zmena domény premennej. Iným výsledkom môže byť
samotná premenná alebo hodnota ako výsledok selekcie. Definované ohraničenia zase môžu
vystupovať v úlohe podporných znalostí. Inferenčné kroky môžu byť usporiadané v nejakej
štruktúre podľa zvolenej stratégie riešenia.
Ukážkou môže byť napr. stratégia ER (extend and revise). Inferenčná vrstva znalostného
modelu, zodpovedajúca tejto stratégii, pozostáva z niekoľkých navzájom prepojených aktivít
znázornených na Obrázku 8.
A
N
TEST
VYHODNOTENIE
Neúspech
A
voľné
premenné
TEST
N
redukované
hodnoty
hodnoty pre
premenné
TEST
N
A
REDUKCIA
Úspech
PRIRADENIE
Obrázok 8. Inferenčná vrstva stratégie ER.
Tieto aktivity operujú nad dvomi typmi znalostných štruktúr – premennými a doménami
týchto premenných. Pri manipulácii s hodnotami v doménach sa určuje, ktoré hodnoty budú
skutočne priradené premenným a ktoré budú vyradené z domén ako nepoužiteľné.
Stratégia sa zameriava na postupné budovanie riešenia. Na začiatku je riešenie prázdne,
žiadnej premennej nie je priradená hodnota – všetky premenné sú voľné. Keďže stratégia
neobsahuje žiadne opravné aktivity (nedochádza k uvoľňovaniu premenných ani k zmene ich
hodnôt), premennej je možné priradiť hodnotu iba v prípade, že toto priradenie nemôže byť
v následnej fáze spochybnené.
Inferencie navzájom prepájajú tri rôzne aktivity: vyhodnotenie, priradenie a redukciu.
Tieto aktivity je možné charakterizovať nasledovne:

Vyhodnotenie skúma aktuálny stav viazanosti jednotlivých premenných. Výstupom
je zoznam voľných premenných, ktorým je ešte potrebné priradiť hodnotu. Činnosť je
algoritmická, nevyžadujúca žiadne doménové znalosti.

Priradenie v skutočnosti pozostáva z dvoch krokov. V prvom kroku sa vyberie voľná
premenná a v druhom sa určuje hodnota, ktorú je potrebné priradiť tejto premennej.
Výber voľnej premennej môže byť založený na znalostiach (umožňujúcich priamo
vybrať jednu premennú alebo poskytujúcich poradie v ktorom je vhodné premenné
skúmať) alebo premenné môžu byť jednoducho skúmané v preddefinovanom poradí
(ktoré môže byť aj náhodné). Výber hodnoty musí byť založený na znalostiach,
pretože je možné vybrať iba takú hodnotu, ktorá neporušuje žiadne ohraničenie (a to
ako aktuálne tak ani v budúcnosti). Počet takýchto viazaní premenných môže byť
rôzny – aktivita sa môže realizovať so snahou naviazať iba jednu z voľných
premenných ale aj so snahou naviazať všetky tie voľné premenné, u ktorých to je
v danom štádiu možné. Výstupom je zoznam dvojíc premenná-hodnota.

Redukcia má za cieľ redukovať domény premenných vypúšťaním nevhodných
hodnôt. Pozostáva tak isto z dvoch krokov – výberu domény, ktorá bude redukovaná,
a určení hodnoty, ktorá bude z vybranej domény vypustená. Podobne ako
v predchádzajúcej aktivite, výber domény môže byť založený na znalostiach alebo
nepoužíva žiadne doménové znalosti. Pre určenie hodnoty, ktorá bude vyradená, sú
potrebné doménové znalosti. Snahou môže byť vyradiť jednu alebo čo najviac hodnôt
z jednej alebo čo najviac domén. Výstupom je zoznam dvojíc doména-hodnota.
Okrem týchto troch hlavných aktivít sú použité aj testovacie aktivity. Keďže tieto iba
skúmajú, či zoznamy, vygenerované hlavnými aktivitami, sú prázdne alebo nie, nepotrebujú
žiadnu znalostnú podporu.
Prepojenie aktivít vytvára dva cykly. Základným cyklom je prepojenie vyhodnotenia
a priradenia. Akonáhle nie je možné vykonať žiadne priradenie, v rozšírenom cykle sa
prechádza na redukciu. V prípade úspešnej redukcie sa opäť prechádza na menší cyklus.
V prípade, že nie sú identifikované žiadne voľné premenné, je k dispozícii hotové riešenie.
Ak sú ešte niektoré premenné voľné a súčasne nie je možné vykonať ani jedno priradenia
a ani redukciu, tak nie je možné na základe dostupných znalostí zostaviť riešenie (ktoré môže
alebo nemusí existovať).
Aby bolo možné nejaký znalostný model použiť, je potrebné doň vložiť konkrétne
znalosti. Pre realizáciu uvedeného modelu je potrebné mať aspoň znalosti, kedy je možné
premennej priradiť nejakú hodnotu a kedy je možné nejakú hodnotu vypustiť z nejakej
domény.
Znalosti pre výber voľnej premennej pre priradenie hodnoty a výber domény pre
redukciu je samozrejme možné nahradiť nejakou všeobecne použiteľnou metódou, napr.
náhodným výberom alebo systematickým skúmaním, avšak je zrejmé, že to pravé urýchlenie
riešenia sa získa práve použitím doménovo závislých heuristík.
Pre použitý ilustračný príklad na Obrázku 1 je možné využiť uvedenú inferenčnú časť
modelu a doplniť ju doménovými znalosťami (uvedené znalosti sú iba ilustračné a v žiadnom
prípade si nerobia nárok na úplnosť). Doplnenie znalosťami pre realizáciu priradenia:

P1: ak v nejakom útvare (riadku, stĺpci alebo štvorci) na nejakej pozícii je prípustná
iba jedna hodnota, tak tá hodnota sa umiestni na danú pozíciu bez ohľadu na to, či
táto hodnota je prípustná aj pre inú pozíciu daného útvaru alebo nie;

P2: ak v nejakom útvare (riadku, stĺpci alebo štvorci) je pre nejakú hodnotu prípustná
iba jedna pozícia, tak tá hodnota sa umiestni na danú pozíciu bez ohľadu na to, či pre
danú pozíciu sú prípustné aj ďalšie hodnoty alebo nie;
ako aj znalosťami pre realizáciu redukcie:

R1: pre nejakú pozíciu je neprípustná taká hodnota, ktorá je už umiestnená v útvare
(riadku, stĺpci alebo štvorci), do ktorého skúmaná pozícia patrí;

R2 (heuristika locked candidates): ak nejaká hodnota síce ešte nie je umiestnená
v štvorci, ale je prípustná iba pre pozície na priesečníku tohto štvorca a jedného
riadku (stĺpca), tak táto hodnota potom nie je prípustná pre tie pozície daného riadku
(stĺpca), ktoré nie sú súčasťou daného štvorca. Analogicky, ak nejaká hodnota nie je
ešte umiestnená v riadku (stĺpci), ale je prípustná iba pre pozície tohto riadku (stĺpca)
a jedného štvorca, tak táto hodnota nie je prípustná pre tie pozície daného štvorca,
ktoré nie sú súčasťou daného riadku (stĺpca);

R3 (heuristika naked pairs): ak v nejakom útvare (riadku, stĺpci alebo štvorci) pre dve
rôzne pozície sú prípustné iba dve hodnoty, rovnaké pre obe pozície, tak tieto dve
hodnoty nie sú prípustné pre ostatné pozície daného útvaru;

R4 (heuristika hidden pairs): ak v nejakom útvare (riadku, stĺpci alebo štvorci) dve
rôzne hodnoty sú prípustné iba pre dve pozície, rovnaké pre obe hodnoty, tak pre
tieto dve pozície nie sú prípustné žiadne iné hodnoty.
Keďže kombinácia P1 a R1 v uvedenom modeli je vlastne ekvivalentom zabezpečenia
hranovej konzistencie, tak výsledkom ich použitia je situácia na Obrázku 3. V tejto situácii by
použitie P2 zapríčinilo napr. umiestnenie hodnoty 1 na pozíciu 99, pretože aj keď táto
hodnota je prípustná pre viac pozícií posledného riadku, je prípustná iba pre túto jednu
pozíciu v rámci posledného stĺpca. Následne sa pozícia 77 stáva jedinou prípustnou pozíciou
pre hodnotu 6 v rámci pravého dolného štvorca a preto jej môže byť táto hodnota priradená.
Rovnako je možné na Obrázku 3 ilustrovať aj použitie znalostí R2, R3 a R4. Pri použití
R2 je napr. možné hodnotu 4 určiť ako neprípustnú pre pozície 49 a 59 (hodnota je v rámci
pravého horného štvorca prípustná iba v priesečníku tohto štvorca a posledného stĺpca),
hodnotu 3 ako neprípustnú pre pozície 82 a 92 (hodnota je v rámci prvého stĺpca lokalizovaná
na priesečník tohto stĺpca a ľavého dolného štvorca) a hodnotu 7 ako neprípustnú pre pozície
64, 65 a 66 (hodnota v rámci štvrtého riadku je obmedzená na priesečník tohto riadku
a stredného štvorca).
Použitie R3 by na základe toho, že v siedmom stĺpci sú hodnoty 2 a 8 jedinými
prijateľnými hodnotami pre pozície 27 a 87, umožnilo identifikovať nevhodnosť hodnoty 2
pre pozície 37 a 67 ako aj nevhodnosť hodnoty 8 pre pozície 37 a 77.
Aplikácia R4 by mala za následok, že keďže v rámci štvrtého riadku sa hodnota 7 ako aj
hodnota 9 môžu vyskytovať iba na pozíciách 45 a 46, tak hodnoty 4 a 6 nie sú prípustné pre
pozíciu 45 a hodnoty 2, 4 a 6 zase nie sú prípustné pre pozíciu 46.
Pri porovnaní výkonnosti pri riešení problémov z [16] použitie všetkých šiestich
znalostných heuristík umožnilo vyriešiť všetky úlohy zo všetkých štyroch kategórií. Použitie
iba nejakej podmnožiny znalostných heuristík viedlo k menšej úspešnosti s výskytom úloh,
s ktorými si model vybavený touto podmnožinou nedokázal poradiť.
Pri absencii R2 bolo vyriešených 95 úloh, pri R3 to bolo 99 úloh a pri R4 zase 97 úloh.
Nepoužitie P1 viedlo na vyriešenie 93 úloh zatiaľ čo nepoužitie P2 na 83 úloh.
Na rozdiel od konzistenčných algoritmov, jednotlivé znalostné heuristiky nie je možné
zoradiť podľa ich „sily“ pri riešení úloh – nedá sa povedať, ktorá znalosť je lepšia vo
všeobecnosti. Často sa totiž stáva, že kombinácia heuristík umožní vyriešiť nielen tie úlohy,
ktoré bolo možné vyriešiť jednou z kombinovaných heuristík, ale aj tie úlohy, s ktorými si
žiadna osobitne použitá heuristika neporadila. Vzniká takto synergický efekt, ktorý poskytuje
výkonnosť vyššiu ako je súčet výkonností jednotlivých zložiek.
Pri použití [21] bol model s uvedenými znalostnými heuristikami neúspešný, nedokázal
vyriešiť ani jednu z úloh. Pre ich riešenie je nutné použiť niektoré z heuristík pre zložitejšie
problémy [34].
6 Záver
Prirodzene vystupuje do popredia otázka, ktorý z uvedených prístupov je vhodnejší pri riešení
nejakého konkrétneho prípadu. Táto otázka sa nedá zodpovedať na všeobecnej úrovni, pretože
odpoveď je závislá od charakteristík riešeného problému a podmienok hľadania riešenia. Je
dôležité si uvedomiť, že rozličné typy metód sú založené na rozličných princípoch a to môže
spôsobovať ich rozličnú vhodnosť alebo nevhodnosť.
Kritickým faktorom pre použitie redukčných metód je množstvo propagácií, ktoré
umožňujú ohraničenia. Ak podstata problému je taká, že pomerne malým množstvom úsilia je
možné dosiahnuť veľké orezanie priestoru prehľadávania, tak to je vhodné použitie pre tento
typ metód. Ich použiteľnosť sa však znižuje s nutnosťou zabezpečovať vyššie stupne
konzistencie kvôli veľkému nárastu časových nárokov oproti prípadom, keď postačuje
zabezpečenie iba nižšieho stupňa konzistencie.
Pre rozšírenie použiteľnosti sú konzistenčné metódy spájané s prehľadávacími
algoritmami, keď priestor je redukovaný iba čiastočne a samotné riešenie je vyhľadávané
prehľadávaním tohto redukovaného priestoru nejakým algoritmom, ktorého základ tvorí
prehľadávanie s možnosťou navracania.
Doménou evolučných algoritmov sú najmä problémy, ktorých rozmer neumožňuje ich
riešenie redukčnými a deterministickými prehľadávacími metódami. Dosiahnuté výsledky
pritom favorizujú tie varianty evolučných algoritmov, ktoré sa v nejakej miere vzdali svojej
univerzálnosti zohľadňovaním charakteru ohraničení a štruktúry vzájomnej závislosti
ohraničení. Dobré výsledky boli dosiahnuté aj použitím adaptívnych verzií, ktoré sa v určitej
miere dokázali prispôsobiť konkrétnemu riešenému problému.
Pri použití znalostného princípu narastajú časové nároky na formulovanie problému,
pretože súčasťou tejto formulácie je aj proces získavania potrebných znalostí, nutných pre
vykonávanie jednotlivých krokov znalostného modelu. Pri dostupnosti vhodných znalostí je
však možné riešiť úlohy veľmi efektívne, pretože je možné k jednotlivým ohraničeniam (a ich
porušeniam) pristupovať individuálnym spôsobom so zohľadnením ich podstaty. V prípade
dostupnosti znalostí tento prístup umožňuje riešiť aj veľmi zložité problémy, neriešiteľné
alebo iba obtiažne riešiteľné inými metódami.
Literatúra
[1] Bacchus, F., Van Beek, P.: On the conversion between non-binary and binary constraint
satisfaction problems. In Proc. of the 15th National Conference on Artificial Intelligence
AAAI-98, Madison, Wisconsin, 1998, pp. 311-318.
[2] Berlandier, P.: A symbiotic approach to arc and path consistency checking. In PintoFerreira, C. – Mamede, N.J. (eds.): Progress in Artificial Intelligence (LNAI 990).
Springer Verlag, Heidelberg, 1995, pp. 107-114.
[3] Bessiere, Ch.: Arc-consistency and arc-consistency again. Artificial Intelligence 65
(1994) 179-190.
[4] Bessiere, Ch., Regin, J-Ch.: Using bidirectionality to speed up arc-consistency
processing. In Meyer, M. (ed.): Constraint Processing (LNCS 923). Springer Verlag,
Heidelberg, 1995, pp. 157-169.
[5] Borning, A.: The programming language aspects of ThingLab, a constraint oriented
simulation laboratory. ACM Transactions on Programming Languages and Systems 3
(1981) 252-387.
[6] Clancey, W.J.: Heuristic classification. Artificial Intelligence 27 (1985) 289-350.
[7] Debruyne, R.: A property of path inverse consistency leading to an optimal PIC
algorithm. In Proc. of the European Conference on Artificial Intelligence ECAI-00,
Berlin, 2000, pp. 88-92.
[8] Debruyne, R., Bessiere, Ch.: Some practicable filtering techniques for the constraint
satisfaction problem. In Proc. of the 15th Int. Joint Conference on Artificial Intelligence
IJCAI'97, Nagoya, Japan, 1997, pp. 412-417.
[9] Debruyne, R., Bessiere, Ch.: From restricted path consistency to max-restricted path
consistency. In Proc. of Third Int. Conference on Principles and Practice of Constraint
Programming, Linz, 1997, pp. 312-326.
[10] Dechter, R.: Constraint processing. San Francisco, CA: Morgan Kaufmann 2003.
[11] Eiben, A. E. et al.: Graph coloring with adaptive evolutionary algorithms. Journal of
Heuristics 4 (1998) 25-46.
[12] Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial intelligence through simulated
evolution. New York: John Wiley 1966.
[13] Freuder, E.C.: Synthesizing constraint expressions. Communications of the ACM 21
(1978) 958-966.
[14] Freuder, E.C.: Using metalevel constraint knowledge to reduce constraint checking. In
Meyer, M. (ed.): Constraint Processing (LNCS 923). Springer Verlag, Heidelberg,
1995, pp. 171-183.
[15] Guesgen, H-W., Hertzberg, J.: Some fundamental properties of local constraint
propagation. Artificial Intelligence 36 (1988) 237-247.
[16] Gould, W.: Pravda Sudoku kniha 1. Bratislava: Denník Pravda 2005.
[17] Haralick, R.M., Shapiro, L.G.: The consistent labeling problem: part I. IEEE Trans. on
Pattern Analysis and Machine Intelligence 1 (1979) 173-184.
[18] Holland, J.H.: Adaptation in natural and artificial systems. Ann Arbor: University of
Michigan Press 1975.
[19] Chandrasekaran, B.: Design problem solving: a task analysis. The AI Magazine 11
(1990) 59-71.
[20] Chen, Y.: Arc consistency revisited. Information Processing Letters 70 (1999) 175-184.
[21] Inkala, A.: AI Sudoku Top 10, 2006, on-line: http://www.aisudoku.com/index_en.html
[22] Kumar, V.: Algorithms for constraint satisfaction problems: a survey. The AI Magazine
13 (1992) 32-44.
[23] Mackworth, A.K.: Consistency in networks of relations. Artificial Intelligence 8 (1977)
99-118.
[24] Mach, M.: Evolučné algoritmy: prvky a princípy. Košice: Elfa 2009, on-line:
http://neuron.tuke.sk/~machm/book-eapp-sk.html
[25] Mach, M., Paralič, J.: Úlohy s ohraničeniami: Od teórie k programovaniu. Košice: Elfa
2000, on-line: http://neuron.tuke.sk/~machm/book-uo-sk.html
[26] Michalewicz, Z.: Genetic algorithms + data structures = evolution programs, 3rd edition.
New York: Springer Verlag 1996.
[27] Mohr, R., Henderson, T.C.: Arc and path consistency revisited. Artificial Intelligence 28
(1986) 225-233.
[28] Newell, A.: The knowledge level. Artificial Intelligence 18 (1982) 87-127.
[29] Popper, M., Kelemen, J.: Expertné systémy. Bratislava: Alfa 1989.
[30] Rechenberg, I.: Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien
der biologischen Evolution. Stuttgart: Frommann-Holzboog 1973.
[31] Schreiber, G. et al.: Knowledge engineering and management. The CommonKADS
methodology. Cambridge, MIT Press 2000.
[32] Schwefel, H.P.: Kybernetische Evolution als Strategie der experimentallen Forschung in
der Stroemungstechnik. Diplomová práca, Technická univerzita, Berlín, 1965.
[33] Steels, L.: Components of expertise. The AI Magazine 11 (1990) 29-49.
[34] SuDoKu-Cracker – Levels of difficulty, on-line: http://www.the24net.com/en/sudoku/
help/?id=levels
[35] Sutherland, I.: Sketchpad: a man-machine graphical communication system. In Proc. of
the IFIP Spring Joint Computer Conference, 1963, pp. 329-345.
[36] Tsang, E.: Foundations of constraint satisfaction. San Diego: Academic Press 1993, online: http://www.bracil.net/edward/fcs.html
[37] Van Hentenryck, P., Deville, Y., Teng, Ch.: A generic arc-consistency algorithm and its
specializations. Artificial Intelligence 57 (1992) 291-321.
[38] Waltz, D.: Understanding line drawings of scenes with shadows. In Winston, P.H. (ed.):
The psychology of computer vision. McGraw Hill, New York, 1975, pp. 19-91.
[39] Weigel, R., Bliek, Ch., Faltings, B.V.: On reformulation of constraint satisfaction
problems. In Proc. of the 13th European Conference on Artificial Intelligence, Brighton,
UK, 1998, pp. 254-258.
Download

Riešenie problémov s ohraničeniami