Egyszerűsített kupacok

Kulcsmódosítás nélküli, egyszerűsített kupac adatszerkezetek implementálása és alkalmazása a Dijkstra-algoritmusban.

Háttér

Sok algoritmus épül prioritásos sorok használatára, köztük az egyik legalapvetőbb gráfalgoritmus, a Dijkstra-algoritmus is. A prioritásos sort általában valamilyen ​kupac adatszerkezettel valósítjuk meg (pl. a klasszikus ​bináris kupaccal). Fontos kérdés, hogy az alapvető műveletek (elem beszúrása, minimális kulcsú elem kivétele) mellett van-e lehetőség arra, hogy egy, már a kupacban lévő elem kulcsát csökkentsük. A Dijkstra-algoritmusban erre szükségünk van, de a szokásos implementáció (pl. amit a LEMON-ban található kupac struktúrákban is alkalmazunk) helyett egy másik lehetőség, hogy az érintett elemet beszúrjuk újra a kupacba a módosított, kisebb kulccsal. Kivételkor a legkisebb (legjobb) kulcsértékkel rendelkező előfordulását fogjuk először megkapni, a többi felesleges előfordulását pedig később könnyen kiszűrhetjük ha nyilvántartjuk, hogy mely elemeket vettük már ki a kupacból.

Ez a változat tulajdonképpen egy egyszerűsítést jelent, hiszen egyrészt kevesebb műveletet kell megvalósítanunk, másrészt pedig ezáltal elkerülhetjük, hogy a kupacban lévő elemekről tárolnunk kelljen az aktuális elhelyezkedésüket (a kulcscsökkentéshez erre szükségünk van, de a többi alapművelethez nincs). Így a beszúrás és törlés műveletek gyorsabbá válhatnak.

Mivel a gyakorlatban előforduló útvonalkeresések esetén kulcscsökkentésre tipikusan viszonylag ritkán van szükség, az egyszerűsített kupacok hatékonyabbak lehetnek. Több tanulmány is született, amely ezt támasztja alá, pl.

• ​Mo Chen. Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra's Algorithm
• ​Mo Chen et. al. Priority Queues and Dijkstra's Algorithm

Feladat

A feladat néhány fontos kupac adatszerkezetből kulcscsökkentés nélküli változat implementálása, valamint a Dijkstra-algoritmusban mért hatékonyságuk alapos összehasonlító elemzése különböző gráfokon. Egy lehetséges folytatás további speciális kupac adatszerkezetek implementálása és összehasonlítása.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat.

Kapcsolódó ticketek: #381, #313.

Előfeltételek

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