Fő tartalom
Tantárgy/kurzus: Számítástudomány > 1. témakör
1. lecke: Bevezetés az algoritmusokbaÚtvonalkeresés
Néha nagyon eltérő problémákról kiderül, hogy hasonlóan oldhatók meg. Miben hasonlít Pac-Man, az angol királyi család és az Orlandóba vezető autóút? Mindháromhoz útvonalkeresési probléma kapcsolódik:
- Milyen rokonsági viszony áll fenn a jelenlegi Vilmos herceg és III. Vilmos király között, aki 1693-ban felavatta a College of William and Mary-t?
- Melyik utat kövesse a szellem, hogy a lehető leggyorsabban eljusson Pac-Manhez?
- Melyik a legjobb útvonal a texasi Dallasból a floridai Orlandoba?
Némi információra van szükségünk ahhoz, hogy a fenti kérdések bármelyikére válaszolni tudjunk.
Például Nagy Britannia királyi családjának családfáján a közvetlen rokonságban levő emberek közötti kapcsolatok láthatóak. Vilmos (William) herceg Charles Philip Arthur Windsor fia. Károly (Charles) II. Erzsébet (Queen Elisabeth II) királynő fia. A feladat az, hogy találjunk egy rövid utat, ami összeköti Vilmos (William) herceget és III. Vilmos (William III) királyt a közvetlen kapcsolatok mentén. Ahogy a lenti családfán is látni, ez jó néhány kapcsolatot jelent.
Pac-Man esetében a labirintus térképére van szükségünk. Ez a térkép az egymás melletti szabad négyzetek közötti kapcsolatokat mutatja – vagy a kapcsolat hiányát, ha ott fal van – és a feladat az, hogy a fekete négyzetek között haladva megtaláljuk a Pac-Manhez vezető utat.
Ha a Dallasból Orlandóba vezető autóutat keressük, használhatjuk ehhez az Egyesült Államok térképét, melyen a közeli városok közötti összeköttetések, utak láthatóak. Nincs egy olyan út sem, mely közvetlenül összekötné Dallast és Orlandót, de több egymás utáni útszakasz eljuttat a célba.
Labirintus felderítése
A labirintusjátékok szórakoztatóak, úgyhogy mélyedjünk el bennük egy kicsit. Ebben a játékban a figura a labirintus különböző pontjaira tud eljutni.
Te, mint ember-játékos, a figurát a következő célpontra kattintva vezérled, a számítógép pedig kikalkulálja, hogyan mozgassa oda a figurát. A célt egy piros „GOAL” feliratú négyzet jelöli. A figura első útjára a start négyszögből indul. Próbáld ki:
Megfigyelted, hogyan jut el a figura a célba? Ehhez a programnak meg kell határoznia a figura által végrehajtandó pontos mozgássort, hogy oda jusson, ahová a játékos kattintott, a mozgást pedig animálni kell. Több lehetséges út létezhet, a programnak ki kell választania ezek közül a legjobbat.
Mielőtt eldöntjük, milyen algoritmust válasszunk, előbb meg kell állapítani a szabályokat: a falakat szürke négyzetek jelölik, és csak üres kockára szabad lépni. Minden lépésben a figura egy szomszédos négyzetre léphet tovább. A figura a sakk bástyájához hasonlóan átlósan nem léphet.
Íme a program által használt algoritmus koncepciója: minden lépéssel menj egy kockával közelebb a játékos által megjelölt célhoz. De mit jelent az, hogy a célhoz közelebb? Ha a figura egyenes vonalban halad, ez gyakran azt eredményezi, hogy beleütközik a falba. Az algoritmusnak meg kell tudnia állapítani, hogy a környező négyzetek közül melyik van „közelebb a célhoz”. Ezt úgy tehetjük meg, hogy minden négyzethez hozzárendelünk egy „költséget”, ami azt a minimális számú lépést jelöli, amit a figurának meg kell tennie ahhoz, hogy onnan elérjen a célig. Az alábbi algoritmussal rendelünk költséget minden négyzethez:
- Indulj a cél négyzettől! Milyen messze van a cél a céltól? 0 lépésre, ezért a célt 0-val jelöljük.
- Keresd meg az összes olyan négyzetet a labirintusban, ami pontosan 1 lépésnyire van a céltól! Jelöld meg ezeket 1-gyel! Ha a cél a kijárat, akkor ebben a labirintusban pontosan egy négyzet lehet pontosan egy lépésnyire.
- Most keresd meg az összes olyan négyzetet, ami pontosan két lépésnyire van a céltól! Ezek a négyzetek egy lépésre vannak az 1-gyel megjelölt négyzettől, és még nem lettek megjelölve. Ezeket a négyzeteket jelöld meg 2-vel!
- Jelöld meg az összes négyzetet, ami pontosan három lépésre van a céltól! Ezek a négyzetek egy lépésre vannak a 2-vel jelölt négyzetektől és még jelöletlenek. Jelöld meg ezeket a négyzeteket 3-mal!
- Folytasd a labirintus négyzeteinek megjelölését abban a sorrendben, ahogy távolodsz a céltól! Miután megjelölted
Végül az algoritmus megjelöli azt a négyzetet, ahonnan a figura indul. Ezután a program úgy találja meg a célhoz vezető utat, hogy kiválasztja a soron következő négyzetet úgy, hogy a számok az út során folyamatosan csökkenjenek. Ha úgy tekinted, mintha a számok a négyzet magasságát jelölnék, akkor ez olyan, mintha egy hegyről ereszkednél alá.
Játssz egy kicsit a lenti költségszámító algoritmussal. Kattints a „Restart algorithm” (Indítsd újra az algoritmust!) gombra az újrakezdéshez!
Mi van akkor, ha a játékos a start négyszögből indul a cél felé? A négyszögjelölő algoritmus használatával a start négyszög 13 lépésnyire van a céltól. Az alábbi ábrán láthatóak a figura lehetséges pozíciói, a kezdő négyzet, valamint a cél közötti kapcsolat, és minden pozíció legrövidebb távolsága a céltól:
A start négyzettől közvetlenül déli irányban van egy négyzet, ami 12 lépésnyire van a céltól. Ezért az első lépés „dél" lesz. Ettől a kockától délre van egy 11-es. Megint délre megyünk. Újra déli irányba a 10-eshez. aztán kétszer keletre a 8-ashoz. Délre a 7-esig, majd keletre a 6-osig, majd ötször délre, hogy elérjük a 2-t. Végül egyszer nyugatra megyünk a 1-re, majd egyszer északra a célhoz.
Most itt nem fogjuk részletesen megtárgyalni, hogyan lehet megvalósítani ezt a labirintus navigáló algoritmust, de elszórakozhatsz azzal, hogy végiggondolod, hogyan valósítanád meg a labirintus és a figura ábrázolását JavaScriptben, és hogyan implementálnád az algoritmust.
Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tantervfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.