COIN-OR::LEMON - Graph Library

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.

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
Last modified 4 years ago Last modified on 04/30/14 02:39:38