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

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 21., 21:05-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}} __TOC__ ==Általános tudnivalók, tételek, definíciók:== ===5.1. Kényszerkielégítési …”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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 (X1, X2, ..., Xn) és kényszerekkel (C1, C2, ..., Cm) 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.

Változó- és értékrendezés

Az információ terjesztése a kényszereken keresztül

Intelligens visszalépés: visszanézni

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 X1, X2, ..., Xn-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 (Xi, Xj)-re, ahol Xi szülője Xj-nek (j pedig fusson visszafelé n-től 2-ig), és szükség esetén vegyünk ki értékeket a TARTOMÁNY[Xi]-ből.
  3. Adjunk Xj-nek bármilyen, Xi hozzárendelt értékével konzisztens értéket ahol Xi szülője Xj-nek, és j 1-től n-ig halad.

Feladatok: