Kényszer-kielégítés Flashcards
Mi a különbség egy általános fakeresési valamint egy kényszer-kielégítési probléma között?
Az állapotot bármilyen struktúra ábrázolhatja a fakeresésben, míg kényszerkielégítési probléma esetén Di tartományából származó Xi változókkal definiáljuk.
Fakeresésben csak az állapotátmenetek, heurisztika és célállapot kell implementálva legyen.
A célteszt kényszerek halmaza, mely mindegyike a változók egy részhalmazát és megfelelő értékeket tartalmazzák.
Mivel lehet megadni egy kényszer-kielégítési feladatot?
állapottér, kezdőállapot, végállapot(ok), rákövetkező függvény, heurisztika
Mit jelent a kemény és puha kényszer? (Abszolút- és preferenciakényszer)
A kemény kényszerek unáris, bináris vagy három változót tartalmaznak.
A puha kényszerek minden értékeléshez költséget kapcsol.
Az egyik a kemény/valódi kényszer az, amelynek nem teljesülése meghiúsítja a megoldást. Míg a puha kényszer esetén egy megoldást még nem kell elvetnünk.
Hogyan lehet megoldani egy kényszer-kielégítési problémát?
- Standard (inkrementális) keresési módszer
- Visszalépéses keresés
- Legkevesebb fennmaradó érték (MRV)
- Fokszám heurisztika
- Legkevésbé korlátozó érték
- Előrenéző ellenőrzés
- Élkonzisztencia
Milyen kényszerek lehetnek egy kényszer-kielégítési problémában?
kemény kényszerek:
- unáris, egyváltozós
- bináris. kétváltozós
- magasabb rendű, több változós
puha kényszerek:
- minden értékeléshez költség kapcsolódik
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ényszereket jelölik
Hogyan működik a visszalépéses keresés egy kényszer-kielégítési probléma esetén?
A kényszerkielégítési feladatra alkalmazott mélységi keresést, ahol egyszerre egy változó kap értéket visszalépéses keresésnek nevezzük egy adott csúcs rákövetkezői között nem szerepel minden változó és annak még lehetséges értéke, hanem csak egy változót engedünk meg, illetve annak lehetséges értékeit. Emiatt a keresőfa egy csúcsának maximum d rákövetkezője lehet, ezért a fának maximum dn levele van.
Tehát az a specialitása ennek a keresésnek, hogy egy adott csúcsban csak egy változó értékadásaival folytathatjuk.
Milyen heurisztikákkal lehet gyorsítani a visszalépéses keresésen? Ismertesse az egyes módszerek lényegét!
- Válasszuk azt a változót mely a legkevesebb megengedett értékkel rendelkezik
- azt válasszuk ami legtöbbször szerepel a hozzárendeletlen változókra vonatkozó kényszerekben
- legkevesebb értéket kizárót válasszuk
- ha valamely változónak nem maradt értéke állítsuk le a keresést
- lokálisan kell érvényesíteni a kényszereket
- minden élt konzisztenssé kell tenni
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?
Az előrenéző ellenőrzés (forward checking) az aktuális változóhoz rendelt értékek előzetes ellenőrzését végzi, míg a kényszerek terjesztése (constraint propagation) a meglévő korlátozásokat terjeszti és aktualizálja a változók között.
Hogyan használható az él-konzisztencia? Milyen korlátai vannak?
Élkonzisztencia : A kényszerek terjesztésének legegyszerűbb formája az, ha minden élt konzisztenssé teszünk az X → Y él konzisztens, ha X minden x értékéhez van y ε Y megengedett érték.
- Ha az X változó egy értékét töröljük, akkor X szomszédait újra kell vizsgálni
- Minden értékadás után érdemes lefuttatni
- O(n2d3) bonyolultság
- Detektálás NP-nehéz
