Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Dijkstra - przyśpieszenie algorytmu

Ostatnio zmodyfikowano 2015-04-25 08:39
Autor Wiadomość
Malina94
Temat założony przez niniejszego użytkownika
Dijkstra - przyśpieszenie algorytmu
» 2015-04-23 16:30:41
Jak można przyśpieszyć działanie algorytmu Dijkstry?
Do przechowywania danych mam kilka tablic:
C/C++
int * koszty = NULL; //koszty
int * poprzednicy = NULL; //poprzednicy
int * kopiec = NULL; //kopiec
int * polozenie = NULL; //polozenie w kopcu
int ** dane = NULL; //wczytane informacje
bool * czyStos = NULL; //najmniejsze znalezione sciezki
sasiad ** sasiedzi = NULL; //graf
Sąsiedzi są tablicą dwuwymiarową, gdzie sasiedzi[x][y] są sąsiednimi wierzchołkami z sasiedzi[x][0].
koszty[x] - koszt dojścia do x-tego wierzchołka
poprzednicy[x] - indeks poprzedniego wierzchołka dla x-tego wierzchołka
kopiec[x] - kolejka, gdzie x-te pole w kopcu zawiera numer wierzchołka, który się w nim znajduje (kopiec binarny)
polozenie[x] - indeks, jaki zajmuje w kopcu x-ty wierzchołek
dane - informacje podane przez użytkownika
czyStos[x] - jeśli dla x-tego wierzchołka znaleziono najkrótszą trasę, to ustawiam na true

Czy opisanie grafu z użyciem normalnej listy + jednowymiarowej tablicy wskaźników może istotnie przyspieszyć działanie algorytmu? Największa ilość danych na której muszę operować to 2000 * 2000.
P-131331
darko202
» 2015-04-24 07:48:25
1.
czy mógłbyś określić otrzymywane czasy i Twój algorytm ?
przy użyciu tych samych elementów można zbudować algorytmy o istotnie różnych czasach
wykonania 
np. sortowanie bąbelkowe, quicksort, itp. inne algorytmy sortowania 


2.
np. na
http://rafalnowak.pl/wiki​/index.php​?title=Algorytm_Dijkstry
jest realizacja tego algorytmu przy pomocy kopca
autor chwali się że jest szybki.
 

inny na
http://www.algorytm.org​/algorytmy-grafowe​/algorytm-dijkstry​/dijkstra-kopce-c.html

porównaj te czasy ze swoim algorytmem.
P-131356
Malina94
Temat założony przez niniejszego użytkownika
» 2015-04-24 11:40:59
Mój kod oparłam na tym algorytmie, na wersji z kopcem:
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0138.php

Moje czasy przy małej ilości danych to 0,001 / 0,002, przy około 1000 rekordów 0,639, a przy +1000000 nawet nie chce mi się czekać aż policzy wynik.
Mój graf zawsze wygląda analogicznie:

o---o---o---o
|   |   |   |
o---o---o---o
|   |   |   |
o---o---o---o
|   |   |   |
o---o---o---o
Użytkownik wczytuje same wierzchołki i na ich podstawie wyznaczam sąsiadów każdego wierzchołka oraz obliczam wagi.
No i sama implementuję struktury, nie korzystam z gotowych kontenerów.
P-131363
darko202
» 2015-04-25 08:39:46
nie za bardzo zrozumiałem który algorytm użyłeś
zastanów się jaka jest złożoność użytego przez Ciebie algorytmu

na zacytowanej przez Ciebie stronie można wyczytać
"
Podstawowym zyskiem zastosowania kolejki priorytetowej w algorytmie Dijkstry jest zmniejszenie klasy złożoności obliczeniowej z O(n2) na O(n log n).
"

dlatego może obserwowany przez Ciebie efekt nie jest taki dziwny





P-131403
« 1 »
  Strona 1 z 1