5. Kényszerkielégítési problémák

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Általános tudnivalók, tételek, definíciók:

5.1. Kényszerkielégítési problémák

Formális definíciója változókkal (X₁, X₂, ..., X_n) és kényszerekkel (C₁, C₂, ..., C_m) történik. Problémaállapot definiálása a változók értékadásával lehetséges, ami:

• =konzisztens:= ha egyetlen kényszert sem sért meg
• =teljes:= ha mindegyik változó szerepel benne, és az összes kényszer teljesül.

Kényszergráf: csomópontok a változók, és az élek a kényszerek

Inkrementális megfogalmazás:

• =kiindulási állapot:= üres hozzárendelés {}, ahol egyik változónak sincs értéke
• =állapotátmenet-függvény:= bármelyik hozzárendéls nélküli változó értéket kaphat, amennyiben ez nem ütközik a korábbi értékadásokkal
• =célteszt:= az aktuális hozzárendelés teljes
• =az út költsége:= egy konstans költség (pl.: 1) mindegyik lépésre

Kényszerkielégítési problémák esetei:

• diszkrét változók véges tartománnyal
• diszkrét változók végtelen tartománnyal
• folytonos változók

Kényszerek fajtái:

• =unáris:= egy változóra tesz megkötést
• =bináris:= két változóra tesz megkötést
• =abszolút:= egy kényszer megszegése kizár egy megoldásjelöltet
• =preferencia:= jelzik, hogy mely megoldások a preferáltak

5.2. A visszalépéses keresés alkalmazása kényszerkielégítési problémákra

Egy probléma akkor kommutatív, ha a végeredmény szempontjából közömbös, hogy cselekvések egy adott sorozatát milyen sorrendben alkalmazzuk. Mindegyik kényszerkielégítési problémamegoldó a következő állapot generálásakor a keresési fa minden csomópontjában csak egyetlen változó lehetséges hozzárendeléseit veszi tekintetbe.

A visszalépéses keresés kifejezést olyan mélységi keresésekre használjuk, melyek egyszerre csak egy változóhoz rendelnek értéket, és visszalépnek, ha már nincs megengedett hozzárendelési lehetőség.

5.3. Lokális kersés kényszerkielégítési problémákkal

A kiinduló állapotban minden változóhoz rendelnek értéket, és az állapotátmenet-függvény működése során általában egyszerre csak egy változó értékét módosítja. Előnyös, ha egy viszonylag jó kezdeti állapot adott, vagy az, ha online az elrendezésben, vagyis a probléma változik (ütemezés).

Min-konfliktusok heurisztika: olyan értéket választunk a változónak, ami a legkevesebb konfliktust eredményezi a többi változóval szemben

5.4. A problémák struktúrája

Bármely fastruktúrájú kényszerkielégítési probléma megoldható a változók száma szerinti lineáris időben.

Az algoritmus lépései:

1. Válasszuk ki bármelyik változót a fa gyökércsomópontjául, és rendezzük a többi változót a gyökértől a levelekig úgy, hogy mindegyik csomópontot a sorrendezésben megelőzzön a szülője. Címkézzük ezeket a változókat sorban X₁, X₂, ..., X_n-nel. Most a gyökércsomópontot leszámítva, mindegyik változónak pontosan egy szülője van.
2. Alkalmazzuk az élkonzisztenciát (X_i, X_j)-re, ahol X_i szülője X_j-nek (j pedig fusson visszafelé n-től 2-ig), és szükség esetén vegyünk ki értékeket a TARTOMÁNY[X_i]-ből.
3. Adjunk X_j-nek bármilyen, X_i hozzárendelt értékével konzisztens értéket ahol X_i szülője X_j-nek, és j 1-től n-ig halad.