Szélességi keresés: mi az és mire jó?

A bevezetőben az Útvonalkeresés fejezetben bemutattunk egy olyan játékot, ahol egy figurát kellett eljuttatni a labirintusban a célig. Induláskor azt mondtuk, hogy a cél önmagától 0 lépésnyire van. Ezután megkerestük az összes olyan négyzetet, ami a céltól egy lépésnyire van. Majd a céltól két lépésnyire levő négyzeteket vettük számba. Azután a három lépés távolság következett, és így tovább, mindaddig, amíg el nem jutottunk ahhoz a négyzethez, ahol a figuránk állt. Ha megjegyezted, hogy melyik, $k$k távolságra levő négyzetről jutottál el a $k+1$k, plus, 1 távolságra levő négyzetre, akkor visszafelé haladva el tudtál jutni a figurával a célig.

Íme a bevezető fejezetben bemutatott ábra:

Bizonyára felismered, hogy ez egy irányítatlan gráf. Minden olyan négyzetnek, ami nem része a falnak, megfelel egy csúcspont, és minden él szomszédos négyzetekre illeszkedik.

A fenti eljárással megkeresett útvonalnak van egy fontos tulajdonsága: nincs olyan másik útvonal a figurától a célig, amelyik kevesebb négyzeten haladna át. Ez azért van, mert a szélességi keresés (breadth-first search, BFS) algoritmusát használtuk a kereséshez. A szélességi keresés megkeresi a legrövidebb (a legkevesebb élt tartalmazó) utat egy adott kiinduló csúcspontból az összes többi csúcsba.

Íme egy másik példa a szélességi keresésre: a „hat lépésre Kevin Bacontól” játék. Ebben a játékban a játékos megpróbál színészeket összekötni Kevin Baconnel egy olyan láncolattal, ami azon alapul, hogy ki kivel szerepelt együtt valamilyen filmben. Minél rövidebb a lánc, annál jobb. Meglepő, hogy hány színész kapcsolható Kevin Baconhoz hat, vagy annál kevesebb elemet tartalmazó lánccal. Például vegyük Kate Bellt, egy ausztrál színésznőt. Nash Edgertonnal játszott 2006-ban a MacBethben; Edgerton szerepelt a The Matrix Reloaded filmben Laurence Fishburnenel 2003-ban; Fishburne benne volt a Mystic Riverben Kevin Baconnal 2003-ban. Így Kate Bell „Kevin Bacon indexe” 3. Valójában többféleképpen is ki lehet mutatni, hogy Kate Belle Kevin Bacon indexe 3. Bármelyik színész vagy színésznő Kevin Bacon indexét megkeresheted a the Oracle of Bacon weboldalon.

Ahogy valószínűleg te is rájöttél, az Oracle of Bacon weboldal egy irányítatlan gráfot kezel, ahol minden csúcspont egy színésznek felel meg, és ha két ember ugyanabban a filmben szerepelt, akkor a két csúcspontra illeszkedik egy él. A Kevin Baconból kiinduló szélességi keresés megtalálja a legrövidebb utat az összes többi színészhez.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.