Changes between Initial Version and Version 1 of Egyszerűsített kupacok

Timestamp:

04/30/14 00:08:12 (11 years ago)

Author:

Peter Kovacs

Comment:

--

Egyszerűsített kupacok

@@ +1 @@
+= 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 [http://en.wikipedia.org/wiki/Heap_%28data_structure%29 kupac adatszerkezettel] valósítjuk meg (pl. a klasszikus [http://en.wikipedia.org/wiki/Binary_heap 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.
+* [ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-07-36-chen.pdf ​Mo Chen. Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra's Algorithm]
+* [ftp://ftp.cs.utexas.edu/pub/techreports/tr07-54.pdf 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, akár több jelentkező számára is.
+
+'''Kapcsolódó ticketek:''' #381, #313.
+
+== Előfeltételek ==
+
+ - C++ programozási nyelv ismerete
+ - alapvető gráfelméleti ismeretek 
+ - angol nyelvismeret