24c - Metódy riešenia úloh s obmedzujúcimi podmienkami

na rozdiel od predchádzajúcich metód je nutné skúmať aj vnútornú štruktúru stavov
úloha s obmedzujúcimi podmienkami (CSP):
- existuje množina premenných {X1, X2, … XN}, každá premenná môže nadobúdať hodnoty z neprázdnej domény D
- existuje množina obmedzujúcich podmienok {C1, C2, … CN}, každá podmienka predpisuje vzťah medzi nejakou podmnožinou premenných
- stav úlohy je definovaný hodnotami priradenými jednotlivým premennými
- legálny stav znamená, že premenné s priradenými hodnotami vyhovujú predpísaným podmienkam
- v počiatočnom stave nie je priradená hodnota žiadnej premennej
- všeobecný operátor priradzuje hodnotu ľubovoľnej premennej tak, aby nasledujúci stav bol legálny
- riešením je legálny stav, v ktorom majú všetky premenné priradené hodnoty
typy úloh - úloha N dám, zafarbovanie máp, úloha kryptoaritmetických algoritmov

Metóda Backtracking for CSP

v každom kroku priraďuje hodnotu neoznačenej premennej a ak nie je nový stav legálny, priraďuje ďalšiu hodnotu, atď.

po každom priradení hodnoty nejakej premennej vyraddí z množín prípustných hodnôt tie hodnoty, ktoré sú v konflikte
Přiřaď každé proměnné i (i = 1,…,n) množinu přípustných hodnot Si.
Volej proceduru Forward_Checking pro první proměnnou (i = 1).
procedúra Forward checking:
1. Odstraň první hodnotu z množiny Si a přiřaď tuto hodnotu proměnné i, nechť X je nový stav.
2. Je-li X cílovým, tj. legálním stavem, skonči proceduru úspěchem (vrať X), jinak pokračuj.
3. Odstraň z množin Sj, (j = i + 1, …, n) všechny hodnoty, které jsou v konfliktu s dosud přiřazenými hodnotami.
4. Jestliže je nějaká množina Sj (j = i + 1, …, n) prázdná, obnov původní stav množin Sj (tj. stav před bodem 3) a jdi na bod 7. Jinak pokračuj.
5. Volej proceduru Forward_Checking pro proměnnou k = i + 1.
6. Skončí-li procedura Forward_Checking pro proměnnou k úspěchem, skonči také úspěchem (vrať vrácený stav). Jinak pokračuj.
7. Není-li množina Si prázdná, vrať se na bod 1. Jinak skonči neúspěchem.

vychádza z ľubovoľného úplneho (všetkým premenným sú priradené hodnoty), ale nelegálneho stavu
snaží sa zmenšovať počet konfliktov
jednoduchá, ale často veľmi efektívna

temata/24-reseni_uloh/obmedzujuce_podmienky.txt · Poslední úprava: 2011/06/07 16:59 autor: vagabund

Starší verze