Egy másfajta probléma
Az eddigi leckékben mindig egy megoldáshoz vezető utat kerestünk. A korlátozás-kielégítési problémák másképp működnek. Itt nem az érdekes, milyen lépéseken keresztül jutunk el a megoldáshoz, hanem maga a végállapot. A feladat az, hogy néhány változónak úgy adjunk értéket, hogy közben egy sereg feltétel egyszerre teljesüljön. Ezt a feladattípust angol rövidítéssel CSP-nek is szokták nevezni.
Gondoljunk egy órarend összeállítására. A változók a tantárgyak, mindegyikhez egy időpontot kell rendelni. A korlátok pedig világosak. Egy tanár nem taníthat két helyen egyszerre, egy terem nem fogadhat két csoportot egy időben, és néhány óra nem eshet egybe. A megoldás egy olyan időbeosztás, amelyben minden ilyen szabály teljesül. Ugyanez a szerkezet bújik meg a sudoku, az ültetési rend és a projektek erőforrás-beosztása mögött is.
Változók, tartományok, korlátok
Minden korlátozás-kielégítési problémát három dologgal írunk le. Az elsők a változók, azok az egységek, amelyeknek értéket kell adnunk. A másodikak a tartományok, vagyis hogy az egyes változók milyen értékeket vehetnek fel egyáltalán. A harmadikak a korlátok, azok a szabályok, amelyek megmondják, mely értékkombinációk megengedettek és melyek tilosak. A megoldás egy olyan hozzárendelés, amelyben minden változónak van értéke a tartományából, és egyetlen korlát sem sérül.
Vegyük a térképszínezés klasszikus példáját. A változók a térkép régiói, a tartomány néhány szín, mondjuk három. Az egyetlen korlát, hogy két szomszédos régió nem kaphatja ugyanazt a színt. A feladat egyszerűnek hangzik, de ahogy nő a régiók és a szomszédságok száma, gyorsan nehézzé válik megtalálni egy olyan színezést, amely minden határon teljesíti a szabályt.
Keresés visszalépéssel
A legegyszerűbb megoldó módszer a visszalépéses keresés. A gép fog egy változót, ad neki egy értéket a tartományából, majd a következő változóra lép. Minden hozzárendelésnél ellenőrzi, nem sért-e korlátot. Ha minden rendben, halad tovább. Ha viszont zsákutcába jut, ahol a következő változónak már nem tud érvényes értéket adni, akkor visszalép az előzőhöz, és ott másik értékkel próbálkozik. Ez a próbálkozás és visszalépés ismétlődik, amíg vagy összeáll egy teljes, érvényes megoldás, vagy kiderül, hogy nincs ilyen.
A visszalépés önmagában működik, de nagyon lassú tud lenni, mert sokáig halad egy zsákutcában, mielőtt észrevenné, hogy tévedett. A klasszikus MI ezért két okos ötlettel gyorsítja fel. Az egyik az, hogy a hozzárendelt értékek következményeit azonnal továbbvezeti, a másik pedig az, hogy okosan választja meg, melyik változóval és melyik értékkel próbálkozzon először.
Korlátok terjesztése és okos sorrend
A korlátok terjesztésének lényege, hogy egy hozzárendelés következményeit előre végiggondoljuk. Ha egy régió kék lett, akkor a szomszédjai tartományából a kék azonnal kiesik. Ha emiatt egy szomszédnak már csak egyetlen szín marad, azt is rögzíthetjük, ami újabb következményekhez vezet. Így a gép sokszor már azelőtt kiszúrja a zsákutcát, hogy belesétálna, mert egy változó tartománya idő előtt kiürül. Ez rengeteg felesleges próbálkozást takarít meg.
A másik gyorsítás a jó sorrend. Kézenfekvő ötlet, hogy azzal a változóval kezdjünk, amelyiknek a legkevesebb lehetősége maradt, hiszen ott a legnagyobb a hibázás veszélye, és ott derül ki leghamarabb, ha valami nem áll össze. Ezzel párhuzamosan azt az értéket érdemes előbb kipróbálni, amelyik a legkevésbé szűkíti be a többi változó lehetőségeit. Ez a két egyszerű szabály együtt gyakran drámaian felgyorsítja a megoldást.
Három elem ír le minden ilyen feladatot. Változók, amelyeknek értéket adunk, tartományok, amelyekből választhatunk, és korlátok, amelyeknek teljesülniük kell. Ha egy problémát erre a háromra le tudsz bontani, akkor korlátozás-kielégítésként meg is oldható.
Workshop
AI Transformation Day
Egésznapos, vezetőknek szóló program. Feltérképezzük, hol tart a szervezet, mi az első reális lépés, és milyen belső feltételek szükségesek a sikerhez. A nap végén konkrét, prioritizált cselekvési lista.
Érdekel a program →