3. fejezet - Problémamegoldás kereséssel

Ebben a fejezetben megnézzük, hogy egy ágens hogyan tudja megtalálni azt a cselekvéssorozatot, amely elvezet a célhoz, ha erre egyetlen egyedi cselekvés sem elegendő.

A 2. fejezetben említett legegyszerűbb ágensek a reflexszerű ágensek voltak, amelyek cselekvései az állapotok és a cselekvések közötti közvetlen leképzésen alapulnak. Az ilyen ágensek nem képesek olyan környezetben tevékenykedni, ahol e leképzés tárolási igénye túl nagy lenne, vagy ahol a leképezés megtanulása túl sok időt venne igénybe. A célorientált ágensek azonban sikerrel járhatnak a jövőbeli cselekvéseknek és annak a számbavételével, hogy ezen cselekvések kimenetelei mennyire kívánatosak.

Ebben a fejezetben a célorientált ágensek egyik típusát, a problémamegoldó ágenst (problem-solving agent) ismertetjük. A problémamegoldó ágensek úgy határozzák meg, mit is kell tenniük, hogy olyan cselekvéssorozatokat keresnek, amelyek a kívánt állapotokba vezetnek. Azzal kezdjük, hogy pontosan megfogalmazzuk a „problémát” és a „megoldását” felépítő alkotóelemeket, és számos példával illusztráljuk ezen definíciókat. Ezek után néhány általános rendeltetésű keresési algoritmust mutatunk be, amelyek e problémák megoldására alkalmasak, majd az egyes algoritmusok előnyeit összehasonlítjuk. Az algoritmusok nem informáltak (uninformed) abban az értelemben, hogy a probléma definícióján túlmenően más információval a problémáról nem rendelkeznek. A 4. fejezet informált (informed) keresési stratégiákat tárgyal, amelyek rendelkeznek valamilyen elképzeléssel arról, hogy a megoldást merrefelé is kell keresni.

Ebben a fejezetben az algoritmuselmélet területén használt fogalmakat alkalmazzuk. Az aszimptotikus komplexitás (azaz az O() jelölésmód) és az NP-teljesség fogalomkörében nem járatos olvasó számára az A) függelék nyújt bővebb információkat.