Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}} TOC ==Általános tudnivalók, tételek, definíciók:== ===5.1. Kényszerkielégítési …”

2012-10-21T20:05:35Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}} __TOC__ ==Általános tudnivalók, tételek, definíciók:== ===5.1. Kényszerkielégítési …”

Új lap

{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}}

__TOC__

==Á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:'''
# 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.
# 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.
# 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:==

[[Category:Infoalap]]

5. Kényszerkielégítési problémák - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}} __TOC__ ==Általános tudnivalók, tételek, definíciók:== ===5.1. Kényszerkielégítési …”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloKenyszerkielegitesiProblemak}} TOC ==Általános tudnivalók, tételek, definíciók:== ===5.1. Kényszerkielégítési …”