JavaScript útkeresés

3. A* algoritmus

A legismertebb gráfkereső eljárás, amelyet Bertram Raphael, Nils Nilsson és Peter Hart alkotott meg 1968-ban. A legfontosabb tulajdonsága, hogy megoldás létezése esetén mindig optimális megoldást talál. Legelső változatát az első generációs Shakey robot irányításához használták. Labirintus és puzzle játékok megoldásának népszerű eszköze.

Nyomkövetés |  Kattintás a sárga cellára

Bemenet: A böngésző munkaterületén kialakított játéktér falakkal és mozgási területtel, valamint az útvonal start és end pontja.

Kimenet: A start és end pozíciók közötti útvonal.

Változók: Játéktér sor és oszlop elemei, a cells tömb a cellák adatainak számításához.

Algoritmus: A start pozíciótól kezdődően folyamatosan kiszámítjuk a szomszédos cellák f(n)=g(n)+h(n) fügvényét, ahol g(n) a cellák start pozicíótól számított költsége, illetve h(n) az a heurisztikus függvény által meghatározott érték, amivel az end pozíció aktuális cellához viszonyított távolságát határozhatjuk meg. A megvizsgált cellákat egy várólistára fűzzük fel, melyből mindig a legkisebb f(n) értékő cellát helyezzük át a vizsgált listába úgy, hogy közben annak szomszédait is elemezzük. Az eljárást addig folytatjuk amíg el nem érjük az end cellát. Ha nincs megoldás, akkor az út egy üres tömb lesz, tehát nem rajzolható meg.

Eseménykezelés: Az onclick esemény bekövetkezésekor végrehajtandó metódusokat a mystep() függvényből hívjuk meg.

Az alábbiakban rendszerezzük a megoldáshoz szükséges ismereteket. A platformfüggetlen megoldás elkészítéséhez gyakorlatilag egy böngésző programra, és esetleg egy egyszerűbb editorra van szükség. A lecke mintaprogramja a böngészőben kipróbálható és módosítható. Indátásához kattintsatok a forráskód alatti "Próbáld ki! »" gombra.

1

Az algoritmus jellemzői

Az algoritmus véges számú, végrehajtható műveletek sorozatának az elnevezése. Fontos szabály még az is, hogy mindig van bemenete és legalább egy kimenete. A számítógép által értelmezhető nyelven megírt algoritmus pedig a program. Azokat a típusalgoritmusokat, amelyek egy feladat egzakt megoldását adják programozási tételeknek nevezzük. Ilyen például a sorozatszámítás, minimim-maximum választás, keresés, rendezés algoritmusa. Az algoritmusokat nem forrásnyelvi kódban szokták megadni, hanem leíróeszközök segítségével (pl. folyamatábrával, struktogrammal, Jackson ábrával vagy pszeudó kóddal) írják le, amit aztán kódolni lehet egy adott környezetben.

Hasznos leírások:

« Előző | Lap eleje

2

Hogyan alakítsuk ki a belső adatszerkezetet?

Az algoritmus által használt értékeket változókban tároljuk. A programnyelvek egyszerű és összetett változókkal dolgoznak. A programtervezés során az adattípusok meghatározása mellet, ügyelnünk kell a belső adatszerkezet optimális kialakítása is. Egy ügyesen tervezett adatszerkezet rengeteg munkát megspórolhat a kódolásnál. A pathfinder programban többdimenziós tömb deklarálásával lehetett a legegyszerűbben kialakítani a cellák adminisztrációját, azt az apró trükköt kihasználva, hogy egy tömb eleme is lehet tömb, illetve objektumok is lehetnek tömbelemek.

A program futtatása közben további úgynevezett segédváltozókat is használunk, amelyekkel bizonyos vezérlőszerkezetek működést tudjuk irányítani. Ugyancsak gondoskodnunk kell a kimenő adatok tárolását biztosító adatszerkezetekről is. Ez utóbbiak lehetnek egy másik programmodul, vagy objektum bemenő adatai.

« Előző | Lap eleje

3

Hogyan működik az A* ?

Egy cellaleíró tömben tároljuk a játéksík jellemzőit. Ezen a síkon akadályok és mozgásra alkalmas területek vegyesen helyezkednek el. Ez utóbbiak közöl jelültük ki a start [A] és end [B] pozíciót. Az astar metódus paraméterként kapja meg ezeket az adatokat. Nézzük meg, milyen műveleteket kell elvégeznünk az átvett adatokkal ahhoz, hogy megkapjuk a start és end pozició közötti utat!

A start pozícióban lévő cellát felvesszük egy várólistára, ahonnan mindig a legkisebb F értékű cellát vesszük elő. Most csak a kezdő cella van a várakozási sorban, tehát az ő F értéke a legkisebb. Sorban megvizsgáljuk a körültötte lévő cellákat, ehhez a sor és oszlop azonosítókra van szükségünk. Ha járható celláról van szó, akkor kíszámítjuk az úgynevezett F értéket. Az F érték az aktuális cella start cellához mért költségének (g) és a cél cellához viszonyított távolságának (h) az összege. (Ha le akarnánk egyszerűsíteni a módszert, akkor azt is mondhatnánk, hogy kiszámoljuk a cellatávolságot mindkét irányban, majd összeadjuk az így kapott értékeket. Ugye könnyen belátható, hogyha nő az F értéke, akkor távolodunk az optimális útvonaltól.) Ezeket a számításokat minden élszomszédos cellánál elvégezzük, és a cellákat rendre felfűzzök a várólistára.

Ha egy cella minden szomszédját megvizsgáltuk akkor őt a vizsgált cellák listájára tesszük át. Az újonan listára tett négyzetek szülője mindig az aktuális cella lesz. "Ha valamelyik szomszédos négyzet már korábbról várólistán volt, megnézzük, hogy nem lenne-e jobb a jelenlegi négyzetünkről odamennünk, mint a régi útvonalát meghagyni. Ha nem jobb, ne csináljunk semmit. Ha jobb, akkor az adott négyzet szülőjének adjuk meg azt, ahol most állunk és számoljuk újra a négyzet G és F értékeit."

Ezeket a műveletek addig folytatjuk, amíg el nem értük az end cellát, vagy nem találtuk ugyan az end cellát, de már minden cellát megvizsgáltunk.

"De hogyan kapjuk meg végre azt a legrövidebb útvonalat? Egyszerűen csak haladjunk az end ponttól visszafelé, mindig a négyzetek szülei felé haladva. Így közvetlenül visszajutunk a kezdőpontunkra, tehát ez lesz az áhított útvonalunk. A-ból B-be tehát csak a már megállapított út celláinak középpontjáról középpontjára haladva juthatunk el."[1]

Hasznos leírások:

« Előző | Lap eleje

4

Érdekel a mesterséges intelligencia?

"A mesterséges intelligencia kutatások célja olyan rendszerek (számítógépes programok, robotok) létrehozása, amelyek intelligens módon képesek feladatokat megoldani. Az utóbbi években egy új szemléletű, viselkedésalapú megközelítés van terjedőben, amely ezt a feladatot úgy fogalmazza meg, hogy kutatások, fejlesztések célja, hogy a feladatmegoldást olyan szereplőkkel, ágensekkel végeztesse el, amelyek az intelligens viselkedés bizonyos vonásaival rendelkeznek."

"Egy intelligens rendszer a problémamegoldás során megszerzett ismeretei alapján oldja meg az adott feladatot és megadja ennek eredményét. Egy ilyen viszonylag független, önálló egységet ágensnek tekintünk. Az ágens eredete a latin ago, agere szó, melynek elsődleges jelentése mozgásba hoz, elintéz, cselekszik. A szó alapjelentése szerint ágens lehet mindaz, ami bizonyos fokú önállósággal bír, valamilyen környezet veszi körül, továbbá ezt a környezetet érzékeli és szükség esetén környezetébe beavatkozik.

Ebben az értelemben ágensnek tekinthető egy ember, aki érzékszervei (pl. fül, szem, orr) segítségével érzékeli környezetét és különböző testrészei (pl. száj, kéz, láb) segítségével beavatkozik. Ágens lehet egy robot is, amely kamerái, szenzorai segítségével érzékel és motorokkal vezérelt beavatkozói (pl. robot karok) segítségével beavatkozik. Ágens lehet továbbá egy szoftver is, amelynél input és output adatok (kódolt bitsorozatok) formájában történik az érzékelés és a beavatkozás." [2]

Így tudod kipörgetni a Rubik-kockát 5 másodperc alatt.

Hasznos leírások:

« Előző | Lap eleje

5

Próbáld ki a megoldást!

A leckében tárgyaltak összefoglalásaként tekintsük át és próbáljuk ki az eredeti feladat megoldását. Az elkészült kód most már több mint 250 soros lett, ezért az áttekinthetőség biztosításának érdekében kommentek előzik meg a fontosabb tevékenységek utasításait. Figyeljük meg az elkészült metódusok felépítését, és fedezzük fel azok hívásának sajátosságait, a paraméterátadást, illetve a visszaadott értékek kezelését.

« Előző | Lap eleje

6

Oldd meg a feladatokat!

Kedves Bakonyi Bitfaragó Jelöltek!

Elérkeztünk az erőgyűjtés szakaszának a végéhez. Az itt szerzett ismereteket fogjátok majd alkalmazni az összemérés fordulójában. A következő erőpróbáig azonban még meg kellene oldani néhány izgalmas feladatot.

A karácsonyi online játékpiacon töretlen népszerűségnek örvendenek a labirintus és kirakós játékok. Reméljük az idén sem lesz ez másképp. Készítsétek el az alábbi játékprogramokat, és a biztos siker érdekében tűzdeljétek meg a felsorolt ötletekkel. A kódoláshoz bátran használjátok fel a most bemutatott programot is. Az igényes megoldásokkal értékes pontokat szerezhettek a versenyben, amivel ismét megerősíthetitek a megszerzett pozíciótokat.

Beküldhető feladatok:

  1. Mike a Shanta Claus család reménysége titokban szeretné a karácsonyfa alá becsempészni az ajándékait, ám Steve Dark a Hacker klán legifjabb csemetéje változó intenzítással mindent elkövet, hogy ebben megakadályozza.
    • Tervezzétek meg a játék labirintusát!
    • Helyezzetek el valamelyik cellában egy virtuális karácsonyfát!
    • Tegyétek pályára Mike-ot, és Steve-t!
    • Az egér- vagy billentyű-eseményekkel irányítsátok Mike mozgását!
    • A most megismert útkereső algoritmusra hagyatkozva indítsátok el Steve-t. Ne feledjétek, ő sztochasztikus intenzítással különböző irányba mozog.
    • Nehezítsétek a pályát akadályok elhelyezésével!
    • Kezeljétek le az esetleges ütközésket!
    • Használjátok fel ez előző fordulóban megírt kattintás-számláló, óra és naplozó metódusokat!

    1000 0000|2 pont

  2. A 8-as kirakójátéknak 9!/2=181 440 elérhető állapota van, és így a játék viszonylag könnyen megoldható. Valósítsátok meg a 8-as puzzle kirakását az A* algoritmus felhasználásával.

     HELP  Számoljátok ki a puzzle celláinak célállapothoz viszonyított F értékét minden egyes cellánál, majd összesítsétek a kapott értékeket. Tegyétek várakozási sorba az elmozdítható cellákat a következő állapotra kiszámított F értékekkel, ezután válasszátok ki a legkisebb F értékűt, és mozdítsátok el a játéksíkon. Ismételjétek a fenti műveleteket addig, amíg az aktuális F érték nem egyezik a célállapot értékével.

    1000 0000|2 pont

Lazításként oldjátok meg, majd töltsétek fel az alábbi gondolatébresztő feladatokat is. Lehet, hogy éppen az itt szerzett bitpoint-ok vezetnek el benneteket egyenesen a döntőig.

Beküldhető feladatok:

  1. Az (x1,y1), (x2,y2),…,(xn,yn) valós értékpárok egy síkbeli, n csúcspontú konvex sokszög csúcspontjainak az óramutató járásával ellenkező irányú körüljárási sorrendben megadott koordinátái.
    • Számítsátok ki a sokszög kerületét!
    • Határozzátok meg a sokszög területét!
      Útmutató: Feltételezzük, hogy a sokszog az origot körbefogja. Az origót összekötve a csúcsokkal háromszögeket kapunk. Egy háromszög területét – ha az oldalakat a, b, c jelöli – a már megismert Heron képlettel számolhatjuk ki: T=Math.sqrt(s*(s-a)*(s-b)*(s-c)), ahol s=0,5*(a+b+c).

    10 0000|2 pont

  2. Számítsátok ki egy szám négyzetgyökét Newton módszerrel. A beolvasott szám legyen A. X1=A/2, Xn+1=(Xn+A/Xn)/2 ha n>=1. A számítást addig folytassátok, amíg |Xn+1-Xn|<0,0001. Az eredményt négy tizedes jeggyel jelenítsétek meg!

    1 0000|2 pont

« Előző | Lap eleje

Hivatkozások, felhasznált források

[1] Útkereső algoritmus kezdőknek 2006.04.15

[2] Piglerné Lakner Rozália - Starkné Werner Ágnes: Ágens-technológia Typotex, 2011