Heurisztikus útvonalkeresés

Különböző heurisztikus algoritmusok implementálása legrövidebb utak keresésére.

Háttér

A legrövidebb utak keresése az egyik legfontosabb gráfelméleti feladat. Az alapvető útvonalkereső algoritmusok (BFS, Dijkstra, Bellman-Ford stb.) implementációja már megtalálható a LEMON-ban, de vannak összetettebb, pl. heurisztikus módszerek, amelyekkel sok esetben lényegesen gyorsabban találhatjuk meg két pont között a legrövidebb utat.

A legegyszerűbb javítási ötlet a ​kétirányú keresés: a megadott két pontból "párhuzamosan" indítunk el egy-egy keresést, és ha a két keresés "összeér", akkor a megkapott eredményekből előállítjuk a legrövidebb utat. A gyakorlati megvalósítás nehézsége a részletek körültekintő kidolgozása és implementálása.

Az ún. ​A* algoritmus pedig egy heurisztikus módszer, amely egy alkalmas távolságbecslést felhasználva a Dijkstra-algoritmusnál "ügyesebben" irányítja az útvonalkeresést, ezáltal sokszor lényegesen gyorsabban találja meg a célcsúcsba vezető legrövidebb utat. Ennek a módszernek is létezik kétirányú változata.

Ezeken kívül számos bonyolultabb módszert is kidolgoztak, főleg olyan esetekre, amikor sok pontpár között keresünk legrövidebb utat, így érdemes lehet valamilyen előfeldolgozást végezni, és a kiszámított adatokat felhasználni a lekérdezések megválaszolásához. Ehhez a témakörhöz rengeteg anyag található ezen az oldalon: ​http://algo2.iti.uka.de/schultes/hwy/.

Feladat

A feladat ezen algoritmusok minél hatékonyabb implementálása és összehasonlítása különböző nagyméretű gráfokon.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Kapcsolódó ticketek: #249, #376.

Előfeltételek

• C++ programozási nyelv ismerete
• alapvető gráfelméleti ismeretek
• angol nyelvismeret