WItam,
zastanawiam się dlaczego jeżeli wydam polecenie
sort_heap(Q.begin(),Q.end());
to wektor/kopiec mi sie sortuje dobrze poza tym, że korzeń spada na sam koniec i nie podlega sortowaniu.. a zeby posrotowalo calosc dobrze musze wywolac\
pop_heap(Q.begin(),Q.end())
sort_heap(Q.begin(),Q.end());
Czy ktoś umie wyjaśnić to dziwne zjawisko?
Rozumiem, że użyłeś najpierw make_heap?
no logiczne:)
wrzuć najkrótszy kod, w którym będzie ten błąd. U mnie wszystko jest ok.
hmmm najkrótszy to jest w tym 1. poscie..ciężko mi powiedzieć co dokładnie to może powodować
ale dzieje się to przy algorytmie dijkstry, zatem go wklejam (przy okazji mam drugie pytanie dlatego wkleje w calosci):
a wiec tutaj nie dziala: jest to algorytm dijkstry
felerne 2 linie oznaczyłem ########
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream.h>
//!Wartość, od której przyjmujemy nieskończoność
#define nieskonczonosc 1000
using namespace std;
class cGraf{
public:
/*!Macierz przyległości, w indeksie (i,j) zawiera wartości:
0 dla i=j
nieskonczonosc jeśli nie istnieje krawędź (i,j)
K>0 waga krawędzi (i,j)
*/
int A[100][100];
/*!Wektor odległości od pierwszego wierzchołka do pozostałych,
początkowo zawiera pierwszy wiersz macierzy A
*/
int D[100];
//!Liczba wierzchołków grafu
int n;
//!Metoda wyznacza listę następników wierzchołka x
vector<int> Nastepniki(int x){
vector<int> wynik;
for (int i=0;i<n;i++)
if ((A[x][i]!=nieskonczonosc)&&(A[x][i]!=0))
wynik.push_back(i);
return(wynik);
}
};
class cWierzcholek{
public:
//!Wierzchołek
int V;
//!Odległość wierzchołka pierwszego do wierzchołka V
int Odl;
//!Przeciążamy operator mniejszości dla klasy cWierzcholek
friend bool operator < (const cWierzcholek &p1, const cWierzcholek &p2){
return(p1.Odl<p2.Odl);
}
};
void main(void)
{
FILE *plik;
char s[5];
int i,j,k;
cGraf Graf;
/*!Kolejka priorytetowa wierzchołków, uporządkowana wg klucza,
którym jest atrybut Odl klasy cWierzchołek
*/
vector<cWierzcholek> Q;
cWierzcholek wierzcholek;
//!Lista następników
vector<int> nastepniki;
//--------------------------------------------
if ((plik=fopen("graf.txt","r"))==NULL)
printf("Brak pliku graf.txt!\n"); else
{
//!Wczytujemy liczbęwierzchołków grafu
fscanf(plik,"%d",&Graf.n);
//!Wczytujemy dane do macierzy przyległości
for (j=0;j<Graf.n;j++)
for (i=0;i<Graf.n;i++)
{
fscanf(plik,"%s",s);
if (strcmp(s,"*")!=0)
Graf.A[j][i]=atoi(s); else Graf.A[j][i]=nieskonczonosc;
}
fclose(plik);
//!przyjmujemy, że wyznaczamy odległości od pierwszego wierzchołka w macierzy A
//!Tworzmy stóg
make_heap(Q.begin(),Q.end(),less<cWierzcholek>());
for (i=0;i<Graf.n;i++){
//!Początkowo wektor D zawiera pierwszy wiersz macierzy A
Graf.D[i]=Graf.A[0][i];
//!Dodaj dane z macierzy do kolejki Q
wierzcholek.V=i;
wierzcholek.Odl=Graf.A[0][i]; //w sumie to jest niepotrzebne bo i tak się nigdy tego nie używa
Q.insert(Q.begin(),wierzcholek);
}
vector<cWierzcholek>::iterator it;
//!Posortuj kolejkę Q
//#################TUTAJ#############
//jeżeli wyrzucimy pop_heap(...) to będzie zwracać złe wyniki a wedlug tego co mowisz powinno smigac.. (wg. mnie tez)
pop_heap(Q.begin(),Q.end());
sort_heap(Q.begin(),Q.end());
/*!Usuń pierwszy wierzchołek (odległość od pierwszego wierzchołka do pierwszego
wierzchołka wynosi 0
*/
cout << "przed Q.erase(Q.begin()); " << endl;
for(it = Q.begin();it!=Q.end();it++){
cout << "nr "<< (*it).V<< ") " << (*it).Odl << endl ;
}
cout << endl;
Q.erase(Q.begin());
cout << "po Q.erase(Q.begin()); " << endl;
for(it = Q.begin();it!=Q.end();it++){
cout << "nr " << (*it).V<< ") " << (*it).Odl << endl ;
}
cout << endl;
while (Q.empty()!=true){
//!Pobierz pierwszy wierzchołek z kolejki Q (ma on najmniejszą wartość klucza)
wierzcholek=Q[0];
//!Usuń go z kolejki
Q.erase(Q.begin());
cout << "po usunieciu 1. w while " << endl;
for(it = Q.begin();it!=Q.end();it++){
cout << (*it).Odl << " " ;
}
cout << endl;
//!Wyznacz listę jego następników
nastepniki=Graf.Nastepniki(wierzcholek.V);
cout << " rozpatruję wierzchołek nr " << wierzcholek.V << " waga " << Graf.D[wierzcholek.V];
cout << endl;
//!Dokonaj relaksacji odległości od wierzchołka pierwszego do każdego następnika z tej listy
for (i=0;i<nastepniki.size();i++)
Graf.D[nastepniki[i]]=min(Graf.D[nastepniki[i]],Graf.D[wierzcholek.V]+Graf.A[wierzcholek.V][nastepniki[i]]);
}
//!Wypisz wektor D zastępując wartość stałej nieskonczonosc znakiem *
k=nieskonczonosc;
for (i=0;i<Graf.n;i++)
if (Graf.D[i]<k)
printf("D(%i)=%d\n",i,Graf.D[i]);
else
printf("D(%i)=%s\n",i,"*");
}
printf("\nDowolny klawisz...\n");
getch();
return;
}
dodatkowo mam jeszcze jeden problem..
w petli while(Q.empty()!=true)
za kazdym razem powinno z tablicy Q pobierac wierzcholek i o aktualnie najmniejszym D[i] i go usuwac...
tutaj natomiast przed ta petla Q jest sortowane rosnaco a pozniej juz pobierane jest jak leci (dochodzi do tego, ze wierzcholki sa pobierane z Q w kolejnosci takiej, ze wierzcholek, ktory ma wieksze D[i] od innego zostanie pobrany przed nim...
mimo to algorytm dziala jednakze nie wiem czemu...
jest to algorytm ze strony
http://www.algorytm.org/index.php?option=com_content&task=view&id=93&Itemid=0
i nawet na niej w opisie algorytmu jest zapis
Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń go ze zbioru.
czyli za kazdym razem powinien byc wyszukiwany wierzcholek o najmniejszej wartosci D[v].
Ktos wie dlaczego to dziala?
no i dlaczego nie dziala jak wywale pop_heap(...)
Pozdrawiam
Ka-lolek
IMO
Q.insert(Q.begin(),wierzcholek);
nie zachowuje własności kopca. Możesz sprawdzić to wstawiając do kodu np.
is_heap(Q.begin(), Q.end());
Innymi słowy gdy chcesz sortować to w wektorze nie ma kopca.
no dobrze
a sort_heap dziala tylko jezeli jest zachowana wlasnosc kopca tak?
w takim razie dlaczego pop_heap tam rozwiazuje problem i w polaczeniu z sort_heap dziala nawet na czyms co nie jest kopcem
i jaka funkcja zamiast Q.insert zachowywalaby wlasnosc kopca?
a sort_heap dziala tylko jezeli jest zachowana wlasnosc kopca tak?
file:///usr/share/doc/stl-manual/html/sort_heap.html
Tak.
i jaka funkcja zamiast Q.insert zachowywalaby wlasnosc kopca?
file:///usr/share/doc/stl-manual/html/push_heap.html
w takim razie dlaczego pop_heap tam rozwiazuje problem i w polaczeniu z sort_heap dziala nawet na czyms co nie jest kopcem
Pewnie nie działa, tylko dobrałeś złe dane do testów.
Pewnie nie działa, tylko dobrałeś złe dane do testów.
tak jak napisalem to jest z serwisu algorytm.org takze nie jestem pewien czy to na pewno nie dziala...
poza tym mnie interesuje tez dlaczego nie wybiera za kazdym razem w petli while wierzcholka v o najmniejszym D[v] tylko leci po kolei:/ pisalem to w moim przedostatnim poscie
Ten kod jest niepoprawny. Kontrprzykład:
5
0 2 * 5 *
Daje wynik:
D(0)=0
D(1)=2
D(2)=3
D(3)=4
D(4)=8
D(4) powinno być 7 ;-)
dlaczego nie wybiera za kazdym razem w petli while wierzcholka v o najmniejszym D[v] tylko leci po kolei:/
Bo jest błąd.
Autor tego kodu widocznie nie za bardzo zna się na STL'u. Lepiej unikaj niesprawdzonych źródeł kodu, bo tylko nabawisz się złych nawyków. Do tego kodu można mieć wiele zastrzeżeń od formatowania i komentarzy poprzez nieuzasadnione mieszanie(!!) iostream z stdio aż do niepoprawności.
no faktycznie, troche mnie uspokoiłeś bo nie mogłem zrozumieć dlaczego tak jest:)
a to, że w takim serwisie dali niepoprawny kod to już jest troche żenujące;/
sry za drugi post ale mam jeszcze jedno pytanie:
czy pop_heap po usunieciu korzenia zachowuje automatycznie kopiec?
I po tej funkcji nalezy usunac ostatni element bo tam po niej bedzie sie znajdowal korzen?
Wlasnie przy pomocy takich operacji na kopcu powinno byc rozwiazane pobieranie wierzcholka v o minimalnym D[v] w petli while(Q.empty!=true)?
pozdrawiam i dzieki za pomoc:)
czy pop_heap po usunieciu korzenia zachowuje automatycznie kopiec?I po tej funkcji nalezy usunac ostatni element bo tam po niej bedzie sie znajdowal korzen?
na oba pytania: tak (wg. SGI).
Wlasnie przy pomocy takich operacji na kopcu powinno byc rozwiazane pobieranie wierzcholka v o minimalnym D[v] w petli while(Q.empty!=true)?
Tak. Pamiętaj, że zmiana jakiegoś elementu na kopcu Q[coś] = jakaś_wartość; spowoduje utratę własności kopca (najprawdopodobniej).
PS. Jest przycisk edytuj ;-)
Mam pytanie odnosnie algorytmu Dijkstry.. wahalem sie czy dodac to jeszcze tutaj czy zalozyc nowy watek ale wpisze tu bo juz ten algorytm tu wklejalem...
Poprawilem go i teraz dziala jak nalezy (faktycznie na stronie byl blad;/)
jednakze zastanawia mnie czy w petli
while(Q.empty()!=true)
muzse za kazdym razem robic na poczatku make_heap(Q.begin(),Q.edn(),less<cWierzcholek>);
Q to zbior wierzcholkow i ktorym jeszcze nie obliczylem drogi minimalnej D[i]
I jest to kopiec ktory jest ukladany wedlug klucza wlasnie D[i] (ten wierzcholek z najmniejsza wartoscia D[i] powinien byc na samej gorze)
Wiadomo, ze w petli while moze nastapic zmiana wartosci D[i] dla nieiktorych wierzcholkow... dlatego dalem na poczatku tej petli wywolanie make_heap (przed pobraniem korzenia z kopca Q ) zeby w tym korzeniu byl zawsze faktycznie najmniejszy element (rzeczywiscie jezeli nie ma make_heap to zwraca bledne wyniki)
Jednakze czy tak to powinno wyglądać? tzn. czy to make_heap powinno być na początku pętli while i się za każdym razem wywoływać ? czy moze da sie to jakos optymalniej zrobic..
Pozdrawiam i prosze o odpowiedz
skrocony kod:
while (Q.empty()!=true){
make_heap(Q.begin(),Q.end(),less<cWierzcholek>()) ; /*####CZY TO JEST KONIECZNE?####*/
//!Pobierz pierwszy wierzchołek z kolejki Q (ma on najmniejszą wartość klucza)
wierzcholek=Q[0];
//!Usuń go z kolejki
pop_heap(Q.begin(),Q.end());
Q.pop_back();
dalej dla kazdego sasiada wierzcholka wierzcholek sprawdzamy czy droga przez niego nie jest optymalniejsza.. jak jest to aktualizujemy tablice D[i]
I WLASNIE TUTAJ nastepuje to, ze wartosc kopca moze sie schrzanic i wrzucam przy nastepnym obiegu petli while make_heap... mozna to jakos inaczej zrobic?
Jeżeli chodzi Ci o przywrócenie własności kopca zaraz po relaksacji to na pewno możesz to zrobić pętlą (zauważ, że zawsze po zmianie wartości wierzchołek pójdzie w górę kopca <<bo jego wartość się nie zwiększy). AFAIR w STL nie ma algorytmu, który by to wykonał.
hmm a jakby to wygladalo tzn. jak mialaby sie zachowywac ta petla?
wiesz moze jaka zlozonosc ma make_heap()? jezeli jest to O(n) to musimy jeszcze popracowac.. jak mniejsza to chyba sie nie da lepiej;P
to zalezy czy make_heap korzysta z tej czesciowo zachowanej sturktury sterty i dzieki temu dziala szybciej czy wszyskto robi od nowa..;/ mam nadzieje, ze ta 1. wersja ale nie moge jakos znalezc;)
edit
jednak znalazlem... liniowa;|
czyli jak mowiles z ta funkcja ? :]
Kopiec wygląda tak, że wierzchołek (ojciec) ma co najwyżej 2 synów, z których każdy ma większą wartość niż on. Czyli jak zmniejszysz wartość jakiegoś elementu to może on stać się mniejszy niż ojciec (czyt. będzie źle). Inaczej mówiąc wystarczy, że zamienisz dany wierzchołek z jego ojcem. Oczywiście, może się okazać, że nowy ojciec też jest za duży - potrzeba więc pętli. Tak aż do korzenia.
int i = nr jakiegoś wierzchołka. // niech v[i] to jego wartość
relaksacja(i);
while(i > 0 && v[i/2] > v[i])
swap(v[i], v[i/2]).
warunek i > 0 jest w sumie niepotrzebny (ale pokazuje intencje) bo v[0/2] > v[0] == false.
dziekiczyli zlozonosc tego bedzie O(V+nlogn) czyli nawet wikipedia pisze, ze jest to optymalne:P
jeszcez jedno proste pytanie:
ogolnie co to jest relaksacja? bo w tym wypadku, to porownywanie tych wartosci i przypisywanie mniejszej, a w ogolnym przypadku?
thx
Mam dla ciebie złą wiadomość.
To będzie działać dla grafu z dużą ilością krawędzi w czasie O(V* V * lg V)
Dla grafu pełnego V-krotnie wyciągamy wierzchołek, dla każdego z tych wierzchołków przechodzimy każdego z jego sąsiadów(kolejne V) i dokonujemy na nim relaksacji (lg V)
Dla grafu pełnego już lepiej za każdym obrotem pętli budować kopiec od początku, bo ma się wtedy czas O(V*V).
Oczywiście najfajniej byłoby zastosować kopce Fibonnaciego:
http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Kolejki_priorytetowe
hmm ale w srednim przypadku o(V+vlogv) ?
To zależy od liczby krawędzi w grafie. Jeśli E=O(VV) to niestety algorytm będzie działał w czasie średnim O(VVlgV) a optymistycznym O(VV).
Jeżeli wiesz, że masz do czynienia z grafem gęstym, to lepiej nie przeprowadzać relaksacji, tylko za każdym razem poprawiać wartości u sąsiadów i budować kopiec od początku. Jeżeli masz liniowy algorytm budowania kopca, to będzie działać w czasie O(V*V).
Jeżeli natomiast chcesz, aby dla grafów rzadkich działał w czasie O(Vlg V) a dla gęstych O(VV) to pozostają kopce Fibonnaciego. Z drugiej strony te kopce wymagają dużo więcej pamięci i są trudne w implementacji, więc raczej nie warto bić się o te O(lg) bo różnica będzie widoczna tylko dla naprawdę dużych i gęstych grafów.
widzę, że stosujesz inne oznaczenia, więc dla pewności:
E-liczb krawędzi
V-liczba wierzchołków
aha, ok :)
zrobię w takim razie z kopcem fibonacciego
a powiedz mi dokladnie do czego odnosi się termin "relaksacja"?
hej, relaksacja to po prostu uaktualnienie wartości d[i] ;-)
d[i] = min ....
Ten alg. jest kwadratowy. Można zejść do liniowo-logarytmicznego, lekko modyfikując strukturę wartości na kopcu (potem może to opiszę jak będziesz chciał bo się spieszę teraz). Kopców fib. nie polecam.
no tak.. w tym konkretnym algorytmie wiem co to relaksacja ale pytałem tak ogólnie ... to jest po prostu uaktualnianie jakiejś wartości ?
co do liczenia dla np. 106 to chodzi Ci zebym to przeliczyl sobie na kalkulatorze czy jakos inaczej to sie liczy?:P (log(106) = 6 , log(log(10^6)) ~0.78)
pzdr
Słowo relaksacja znam tylko z kontekstu algorytmów operujących na grafach i oznacza zazwyczaj uaktualnienie wartości zgodnie z tym wzorem co w algorytmie dijkstry.
Chodziło mi dokładnie o takie przeliczenie jak zrobiłeś, ale dla logarytmu o podstawie 2 ;-). Zobaczysz, że różnica jest tak niewielka, że jest niemierzalna (taką różnicę można traktować jak stałą - pominąć ;-P).
jeszcze wrócę do kodu który podałeś wcześniej
int i = nr jakiegoś wierzchołka. // niech v[i] to jego wartość
relaksacja(i);
while(i > 0 && v[i/2] > v[i])
swap(v[i], v[i/2])
jezeli tak zrobisz, to przeciez jezeli wartosc wierzcholka np. nr 6(rozumiem, ze chodzi tu o najkrotsza droge do niego ze startu) bedzie wynosila np. 5 a wartosc wierzcholka nr 3 bedzie wynosila 11, to po takiej zamianie
odleglosc minimalna wierzcholka nr 6 bedzie wynosila 11, a wierzcholka nr 3 bedzie teraz rowna 5.
a to nie będzie już prawdą...
poza tym ta pętla miała zamieniać miejscami wierzchołki na kopcu, a tak chyba nie jest..
Pozdrawiam
Ka-lolek
to tylko zarys algorytmu - opisałem jak ma działać. Zamieniasz wartości na kopcu. Jak sobie to narysujesz to chodzi o to, że jak jakiś element robi się lżejszy (zmniejszasz mu wartość) to idzie do góry (kopca) tak daleko jak tylko się da (czyli, aż jego ojciec będzie niewiększy od niego). Element przesuwa się w kopcu, ale jego D[i] jest oczywiście zachowane.
a skąd mam wiedzieć który indeks w tablicy z kopcem ma element, którego D[i] się akurat zmieniło ?
muszę przeszukiwać cały kopiec pod kątem indeksu "i" ?