5. Kényszer kielégítés Flashcards
(10 cards)
Különbség egy általános fakeresési valamint egy kényszer-kielégítési probléma között?
1.Kényszer, 2.Keresés
Cél:
1.Érték hozzárendelése minden változóhoz úgy hogy minden kényszer teljesüljön
2.útvonal megtalálása kezdő és cél
Keresési tér:
1.Állapotok és cselekvések által meghatározott fa vagy gráf
2.A változók értékeik kombinációk
Mivel lehet megadni egy kényszer-kielégítési feladatot?
Állapotot D tartományból származó X változókkal definiáljuk
Célteszt kényszerek halmaza mely mindegyike a változók egy részhalmazát és megfelelő értékeket tartalmazzák
Mit jelent a kemény és puha kényszer? (Abszolút- és preferenciakényszer)
Kemény:
Unáris kényszerek
SA != zöld
Bináris kényszer két változóval:
Sa!=WA
magasabb rendű kenyszer legalább három változót tartalmaz
S + M + X = O +10X
Puha:
a piros jobb mint a zöld
rendszerint minden értékeléshez költség kapcsolódik
Hogyan lehet megoldani egy kényszer-kielégítési problémát?
-Standard keresési módszer
-Visszalépéses keresés
-Legkevesebb fennmaradó érték
-
Milyen kényszerek lehetnek egy kényszer-kielégítési problémában?
Unáris kényszerek
SA != zöld
Bináris kényszer két változóval:
Sa!=WA
magasabb rendű kenyszer legalább három változót tartalmaz
S + M + X = O +10X
Egyenlőség reláció
Aritmetikai
Globális
Tiltó
Mit tartalmaz a kényszergráf, és mit jelölnek egyes alkotórészei?
A csúcsok a változók az élek a kényszerek
Hogyan működik a visszalépéses keresés egy kényszer-kielégítési probléma esetén?
A visszalépéses keresés lépésenként rendel értéket a változókhoz, és minden lépés után ellenőrzi, hogy nem sértett-e meg valamilyen kényszert.
Ha megsértett egy kényszert, akkor visszalép (backtrack-el) az előző változóhoz, és más értéket próbál ki.
Milyen heurisztikákkal lehet gyorsítani a visszalépéses keresésen? Ismertesse az egyes módszerek lényegét!
Fokszám heurisztika:
holtverseny esetén dönt a legkevesebb fennmaradó érték heurisztika változóiról
(Válasszuk at a változót mely legtöbbszőr szerepel a hozzárendeletlen változókra vonatkozó kényszerekven)
MRV minimum hátralévő értékek:
Azt a változót választja először, amelynek a legkevesebb még lehetséges értéke van (a legszűkebb domén).
LCV legkevésbé korlátozó érték:
Azt az értéket próbálja ki először, amely a legkevesebb kizárást okozza a többi változó doménjében.
Előre ellenőrzés:
Minden értékadás után megnézi, hogy a többi változónak marad-e még érvényes értéke.
Kényszer terjesztés:
Egy értékadás után láncreakciószerűen frissíti az összes változó doménjét a kényszerek alapján.
Mi a különbség a előrenéző ellenőrzés (forward checking) és a kényszerek terjesztése (constaint propagation) között?
1.Előre 2.kényszer terjesztés
Mire néz?
Csak a közvetlen szomszédokra
Minden elérhető következményre
Vizsgálat mélysége
Sekély Mély, láncszerű
Sebesség Gyorsabb Lassabb
Hogyan használható az él-konzisztencia? Milyen korlátai vannak?
Ha az X változó értékét töröljük akkor X szomszédjait újra kell vizsgálni.
Gyorsabban felfedezi a hibákat mint az előrenéző ellenőrzés.
