Az első vizsgált példa a 2. fejezetben bevezetett porszívóvilág (vacuum world) (lásd 2.2. ábra). Ezt problémaként az alábbi módon definiálhatjuk:

A valós világgal összevetve e probléma jellemzői a diszkrét lokációk, a diszkrét kosz, a megbízható takarítás, valamint az, hogy takarítás után piszok soha nem keletkezik újra (a 3.6. alfejezetben ezeket a feltételezéseket feladjuk). Fontos megjegyezni, hogy az állapotot az ágens és a kosz helyzete együttesen határozza meg. Egy nagyobb, n helyű környezetben n 2ⁿ állapot van.

A 3.4. ábrán bemutatott 8-as kirakójáték (8-puzzle) egy 3 × 3-as táblából, 8 számozott kockából és egy üres helyből áll. Az üres hely melletti kockát be lehet csúsztatni az üres helyre. A cél egy meghatározott állás, mint például az ábra jobb oldalán látható állás elérése. A probléma szokásos megfogalmazása a következő:

3.4. ábra - A 8-as kirakójáték egy tipikus feladványa

Milyen absztrakciókhoz folyamodtunk itt? A cselekvéseket a kezdeti és végállapotuk erejéig absztraháltuk, elmozdítás közben egy kocka közbülső helyzeteit figyelmen kívül hagytuk. Az olyan cselekvésektől is elvonatkoztattunk, mint a tábla megrázása, ha a kockák megakadtak, vagy a kockák késsel való kiszedése és visszahelyezése. Amit kaptunk, az a játék szabálykészlete, a manipulációk fizikai részleteitől eltekintve.

A kirakójáték a csúsztatós kirakójátékok (sliding-block puzzles) családjába tartozik, amelyeket gyakran új kereső algoritmusok tesztelésére alkalmaznak az MI-ben. Ez az általános osztály NP-teljes, így nem várható, hogy lényegesen jobb módszert lehet találni az itt és a következő bekezdésben leírt keresési algoritmusoknál. A 8-as kirakójátéknak 9!/2 = 181 440 elérhető állapota van, és így e játék könnyen megoldható. A 15-ös kirakójátéknak (a 4 × 4-es táblán) kb. 10 billió állapota van, és a legjobb algoritmusok a véletlenül generált eseteket optimálisan néhány milliszekundum alatt oldják meg. A 24-es játéknak (az 5 × 5-ös táblán) kb. 10²⁵ állapota van, és a véletlenszerűen kiválasztott esetek optimális megoldása még mindig kemény dió a jelenlegi gépek és algoritmusok számára.

A 8-királynő probléma (8-queens problem) célja, hogy 8 királynőt úgy helyezzünk el egy sakktáblán, hogy egyáltalán ne támadják egymást. (Egy királynő egy vele azonos sorban, oszlopban vagy átlóban lévő bábut támad.) A 3.5. ábra egy sikertelen megoldási kísérletet mutat: a jobb szélső oszlopban lévő királynőt támadja a bal felső sarokban lévő királynő.

3.5. ábra - Egy majdnem jó megoldás a 8-királynő problémára. (A megoldás megkeresését az olvasóra bízzuk.)

Bár hatékony célalgoritmusok léteznek ezen probléma és a teljes n-királynő probléma megoldására, a királynőfeladat mindamellett érdekes tesztproblémája marad a keresési algoritmusoknak. Két fő megfogalmazása létezik. Az inkrementális megfogalmazásban (incremental formulation) az operátorok az állapotleírást bővítik, az üres állapottól kezdve. A 8-királynő probléma esetén ez azt jelenti, hogy a királynőket egyenként helyezzük el a sakktáblán. A teljes állapot leírásban (complete-state formulation) először felhelyezzük mind a 8 királynőt, majd mozgatjuk őket. Az útköltség mindkét esetben érdektelen számunkra, mert csak a végső állapot számít. A probléma első inkrementális megfogalmazása lehet a következő:

Ebben a megfogalmazásban 64 × 63 × … 57 ≈ 1,8 × 10¹⁴ lehetséges vizsgálandó sorozatunk van. Sokkal ésszerűbb választás lenne, ha figyelembe vennénk azt a tényt, hogy egy már eleve támadt mezőre nincs értelme letenni egy királynőt:

Ez a megfogalmazás a 8-királynő probléma állapotterét 1,8 × 10¹⁴-ről 2057 méretű térré csökkenti, minekutána megoldást könnyű megtalálni. Másrészt 100 királynő a korábbi megfogalmazás 10⁴⁰⁰ állapothoz vezet, míg a javítottnál csak kb. 10⁵² állapotunk lesz (3.5. feladat). Ez óriási redukció, a javított eset azonban még mindig túl nagy az ebben a fejezetben ismertetett algoritmusok számára. A teljes állapot leírásról a 4. fejezetben olvashatunk, az 5. fejezet viszont egy olyan egyszerű algoritmust közöl, amellyel a millió királynőt számláló problémát is könnyen meg lehet oldani.

Már korábban láttuk, hogy az útkeresési problémát (route-finding problem) hogyan definiálhatjuk a megadott helyek és a közöttük lévő összeköttetések segítségével. Az útkereső algoritmusokat számos területen alkalmazzák. Használják például számítógép-hálózatokban útvonalkeresésre, katonai műveletek tervezésénél és légi útvonaltervező rendszerekben is. Általában nehéz az ilyen problémákat specifikálni. Nézzük meg a légi útvonaltervezési probléma egy egyszerűsített példáját:

A kereskedelmi útvonaljavasló rendszerek a probléma valami hasonló megfogalmazását használják, sok további bonyolítással, hogy a repülőtársaságok bonyolult viteldíjstruktúráit kezelni tudják. Minden tapasztalt utas tudja azonban, hogy nem minden repülőút zajlik a tervek szerint. Egy igazán jó rendszernek eshetőségi tervekkel – például az alternatív járatokra történő tartalék helyfoglalásokkal – is tudnia kell foglalkozni, ameddig persze ezeket a költség és az eredeti terv összeomlásának a valószínűsége igazolja.

A körutazási problémák (touring problems) az útkeresési problémák rokonai egy fontos különbséggel. Tekintsük például azt a problémát, hogy „A 3.2. ábra minden egyes városába látogass el legalább egyszer úgy, hogy Bukarestből indulj, és az utat ott is fejezd be.” Az útkeresési problémához hasonlóan a cselekvés itt is két szomszédos város közötti utazásnak felel meg. De ebben a problémában az állapottér alapvetően más. Az ágens helye mellett minden egyes állapotban tárolni kell az ágens által korábban meglátogatott városokat is. Így a kiinduló állapot ebben az esetben a „Bukarestben vagyok, eddig meglátogattam {Bukarestet}” állapot lenne, míg egy tipikus közbenső állapot a „Vasluiban vagyok, eddig meglátogattam {Bukarestet, Csalánost, Vasluit}” állapot. A célteszt ellenőrizné, hogy az ágens Bukarestben van-e, és végiglátogatta-e mind a 20 várost.

Az utazó ügynök probléma (Travelling Salesperson Problem – TSP) egy körutazási probléma, amelyben minden várost pontosan egyszer kell meglátogatni. A cél a legrövidebb út megkeresése. A probléma NP-nehéz, de hatalmas erőfeszítések történtek a TSP-algoritmusok képességeinek javítására. Ezen algoritmusokat az utazó ügynökök útjainak megtervezése mellett nyomtatott áramkörök furatainak készítésénél a fúró automata mozgatásának megtervezésére, továbbá áruházak rakodógépeinek útvonaltervezésére is alkalmazták.

A VLSI elhelyezési (VLSI layout) problémában komponensek és összeköttetések millióit egy chipen kell elhelyezni, a terület, az áramköri késleltetés és a szórt kapacitások minimalizálása és a gyártási kihozatal maximalizálása mellett. Az elhelyezési probléma a logikai tervezés fázisát követi, és általában két részből áll: cellaelrendezésből (cell layout) és huzalozásból (channel routing). A cellaelrendezés során az áramkör primitív komponenseit cellákba rendezik, amelyek mindegyike valamilyen jól definiált funkciót lát el. Minden egyes cellának rögzített nyomtatási képe (méret és alak) van, és adott számú összeköttetést igényel a többi cellához. A cél az, hogy az egyes cellákat úgy helyezzük el a chipen, hogy azok ne lapolódjanak át, és a cellák között legyen megfelelő hely az összekötő vezetékek számára. A huzalozás során minden egyes vezetéknek megfelelő vezetési útvonalat keresünk a cellák között. Ezek a keresési problémák hihetetlenül összetettek, de mindenképpen érdemes a megoldásukat megtalálni. A 4. fejezetben látni fogunk néhány algoritmust, amelyek képesek megoldani ezeket a problémákat.

A robotnavigáció (robot navigation) a korábban leírt útkeresési probléma általánosítása. Az utak diszkrét halmaza helyett a robot egy folytonos térben mozog (elvben) végtelen cselekvés- és állapothalmazzal. Egy egyszerű, sík felületen mozgó kör alakú robot esetén az állapot lényegében kétdimenziós. Amennyiben a robotnak karja és lába is van, akkor azokat is vezérelni kell, így a keresési tér sokdimenzióssá válik. Már a keresési tér végessé tételéhez is kifinomult technikákra van szükség. A 25. fejezetben megvizsgálunk néhány ilyen módszert. A probléma összetettsége mellett a valós robotoknak foglalkozniuk kell az érzékelőik által szolgáltatott jelek és a motorvezérlők hibáival is.

Összetett objektumok robotok általi automatikus összeszerelését (automatic assembly sequencing) először a FREDDY robot mutatta be (Michie, 1972). Azóta lassú, de biztos előrehaladás tapasztalható ezen a területen. Ma már például villanymotorok automatikus összeszerelése gazdaságossági szempontból is kivitelezhető. Az összeszerelési feladatoknál a probléma az alkatrészek összeszerelési sorrendjének megkeresése. Amennyiben rossz szerelési sorrendet választunk, valamikor a későbbiek folyamán egy adott alkatrészt nem tudunk egy másik alkatrész kiszerelése nélkül beszerelni. Annak eldöntése, hogy az összeszerelési sorrend egy lépése megvalósítható-e vagy sem, a robotnavigációhoz hasonló összetett geometriai keresési probléma. Így az összeszerelési sorrend megtervezésében a költséges feladat egy kivitelezhető következő lépés megtervezése. Minden gyakorlati fontosságú algoritmusnak kerülnie kell az állapottér egy kis töredékén túlmenő feltárását. Egy másik fontos összeállítási probléma a fehérjetervezés (protein design), ahol a célkitűzés olyan aminosav-szekvencia megkeresése, amely valamilyen betegség gyógyítása szempontjából lényeges tulajdonságokkal rendelkezik és háromdimenziós fehérjévé formálható.

Az utóbbi időben egyre nagyobb a kereslet az interneten kereső (Internet searching) szoftverrobotok iránt, amelyek kérdésekre választ, kapcsolódó információkat, vagy kereskedelmi üzletek lehetőségét kutatják fel. A keresési technikák szempontjából ez igazán jó alkalmazás, mert eléggé nyilvánvaló, hogy az internethez egy gráfszerű kép rendelhető, ahol a csomópontok (weboldalak) linkekkel össze vannak kapcsolva. Az internetkeresés teljes leírását a 10. fejezetre hagyjuk.