Láthattuk, hogy a keresési stratégiák milyen sokszínűek. Folyamatosan hangsúlyoztuk, hogy a feladat szabja meg mit érdemes használni. Ehhez még hozzá jön, hogy milyen extra ismeretekkel rendelkezünk a feladatról. Végül pedig, ott van, hogy milyen elképzelhető optimalizálást enged meg az állapottér. Ebből egyenesen következik, hogy nem lehet egy keresőrendszert megírni, majd hátradőlni, és azt mondani, hogy íme egy eljárás, ami univerzális. Ilyen nincs! Tehát sajnos szinte lehetetlen az a hagyományos programozói szemlélet, miszerint egy rutin megírása után már csak be kell másolni a legközelebbi munkánál. Természetesen a keresési stratégia nem változik, de a beépített heurisztika, és más feladatspecifikus elemek, amelyek a kódhoz kapcsolódnak, igen. A feladattól függően a már megismert eljárásoknak vannak további fajtái. Azonban ezek leírására most nem fogunk időt szakítani, hiszen szinte minden feladathoz találunk valamilyen eltérő alkalmazást. Most inkább áttérünk egy másfajta megközelítésre. Jól fogja ez szemléltetni, amit ezt megelőzően már említettem, hogy egy feladat megoldása, a különböző állapotok ábrázolása, nem kötött. Bárhogyan megoldható egy feladat. Természetesen vannak az adott feladathoz jobban, és kevésbé illeszkedő megoldások, de minden esetben többféle módon is el lehet indulni. Most nézzünk meg egy olyan feladat megoldást, amelyik sokkal közelebb áll az emberi logikához, mint az eddig megismert „hagyományos” gráfreprezentáció.
Ahhoz, hogy egy problémát ezzel a módszerrel megoldjunk, először is meg kell ismerkednünk az ÉS/VAGY gráfokkal. Feltételezzük, hogy egy adott csomópontból több él is kiindul. Ezek némelyike szorosabb kapcsolatban áll egymással, mint mások. A csúcsok azonban itt nem az adott feladat egy pillanatnyi állapotát reprezentálják, hanem a feladat megoldásához vezető részproblémát. Hogy jobban lehessen érteni, vegyük elő újra a Hanoi tornyai problémát. A feladat, hogy a harmadik rúdról az elsőre kerüljön mind a három korong. A szabályok betartásával, amit itt már nem ismertetünk. Ahhoz, hogy ezt megtegyük, a legnagyobb korongot át kell helyeznünk, az első rúdra. Ennek eléréséhez azonban a szabályok értelmében az szükséges, hogy se az 1.-es jelű rúdon, se pedig a legnagyobb korongon ne legyen másik korong. Tehát a maradék kettőnek a 2-e számú rúdon kell lennie. Tehát, hogy a feladatot végre tudjuk hajtani az előbb leírt gondolatmenetet, kell alkalmazni arra, a most már rész problémára, hogy a B korongot, hogyan helyezzük át a 2.-es rúdra. -és így tovább, amíg csupa olyan részproblémát nem állítunk elő, amelyeknek megoldásával az eredeti problémát is megoldhatjuk. Az ilyen megoldást tudjuk ábrázolni az ÉS/VAGY gráfban. Ha megoldjuk az első egyszerű problémát, ÉS a másodikat, - És a k-adikat, akkor megoldottuk a problémát VAGY egy másik felbontást követve az ottani részproblémák megoldásával, jutunk a kívánt eredményre. Egy ÉS/VAGY gráfot a következő képen rajzolhatunk fel.
A dekompozíciós reprezentáció során meg kell adnunk a kiinduló problémát, az ábrán a „megoldandó feladat”, és a részproblémák sémáját, az egyszerű problémák megoldhatósági feltételét, és a dekomponáló operátorokat. Nézzük ezt konkrétan a Hanoi tornyai problémára!
A problémát egy rendezett négyessel tudjuk leírni. Ez a négydimenziós
vektor legyen az <a, b, c, d>. Ez reprezentálja, hogy a- korongot
kívánunk átrakni a
b-edik rúdról a c-edikre a d-edik segítségével. A kiinduló problémánk ennek
megfelelően a <3,3,1,2> A fent levezetett gondolatmenet alapján a
dekompozíció során megállapítottuk, hogy ehhez az kell, hogy megoldjuk a
következőt: <2,3,2,1> azaz két korongot átrakjunk a 3-as rúdról a
kettesre, az egyes segítségével. Na ez is megoldhatatlan a szabályok szerint.
Ezt a problémát tovább bontva eljutunk a : <1,3,1,2>. Végre egy
megoldható, azaz „egyszerű probléma”. A teljes dekompozíció a következő:
Amint láthatjuk az ábrát értelmezve egyértelműen megoldható problémák sorozatára bontottuk fel az alap problémát. Azaz dekomponáltuk. Ha megnézzük a az alapproblémát, <a,b,c,d> és a részproblémákat:
<a-1,b,d,c>; <1,b,c,d>;<a-1,d,c,b>
Ez a felosztás egy adott dekomponáló operátor alkalmazása esetén jön létre.
Természetesen itt is alkalmazható más operátor. Ez csak a saját belátásunk
dolga.
A reprezentációt elemezve az is látszik, hogy az adott feladat megoldásban
nincs alternatív megoldás, azaz nincsen VAGY ág. Ahhoz, hogy VAGY ágat is
kapjunk több dekomponáló operátort kéne bevezetnünk. Az ÉS/VAGY gráfban a
megoldást az a részgráf(összetartozó élköteg) képviseli, amelyik a feladatot
csupa egyszerű problémára vezeti vissza. A Hanoi tornyai problémában a
megoldást a teljes gráf képviseli, hiszen minden azonos csomópontból kiinduló
él ÉS kapcsolatban van a többi éllel. Ebből pedig következik, hogy minden rész,
illetve egyszerű probléma is ÉS kapcsolatban áll a többivel. Tehát mindet meg
kell oldani ahhoz, hogy a kiinduló problémát megoldjuk. A megoldás megtalálása
aránylag egyszerű. A kiinduló problémát a dekomponáló operátor segítségével
részproblémák sorozatára bontjuk, majd a részproblémákra alkalmazva az
operátort, azokat tovább bontjuk, egészen addig, amíg megoldható egyszerű
problémák sorozatát nem kapjuk.
Most pedig az eljárás algoritmusát nézzük meg:
1., A problémák közé felvesszük a kiinduló problémát.
2., Amíg nem csupa egyszerű a problémák halmazának tartalma addig ismételgetjük:
3., választunk egy alkalmazható szabályt
4., alkalmazzuk a szabályt a problémára, és a kapott részproblémát felvesszük a problémák halmazba.
5., itt a vége az ismétlendő résznek
Azt láthattuk az előző részekben, hogy nehezen lehet minden problémát egy meghatározható állapottérbe kényszeríteni. Azt is észrevehettük, hogy az előbb leírt dekompozíciós eljárással az olyan feladatok is felírhatóak, amelyeket eddig nem számítógéppel oldottunk meg. Ahhoz, hogy lássuk milyen messzire, mutat ez az eljárás, meg kell ismernünk néhány magasabb szintű matematikát. Ezt azonban későbbre halasztjuk. Elég lesz a következő részekben ismertetésre kerülő eljárások során megismerkedni velük. A következő részben a szabályalapú következtetéssel fogunk megismerkedni, és az azt követő rezolúciós válaszadás, már olyan rendszer, amellyel jól lehet automatizálni a matematikai problémák megoldását. Ilyen rendszereket alkalmaznak, is a tudományban. Természetesen az azóta kifejlesztett eljárások között vannak hatékonyabbak, de azok megismeréséhez nélkülözhetetlen ennek a megismerése is.