Diskuze: Graf s veľkým počtom vrcholov
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Člen
Zobrazeno 10 zpráv z 10.
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Jestli je matice sousednosti sparse, tak ti stačí matice M o rozměrech E x 2, kde E je počet hran a i-tý řádek reprezentuje hranu mezi vrcholy M[i, 1] a M[i, 2].
106 vrcholů je relativně malé číslo, dobře napsaný program na něm spočítá algoritmy o složitosti O(k*N2) v řádu sekund.
Nebo jej reprezentuj seznamem sousedů, tzn. pro každý vrchol měj seznam vrcholů, do kterých z něho vede nějaká hrana.
Tak z každého vrcholu, okrem okrajových, vychádzajú 2 cesty do
ďalších vrcholov, pretože je možné posunúť sa o jeden uzol doprava alebo
o jeden uzol dole. Úlohou je nájsť najlepšiu(tj. najväčšiu) cestu z
určitého bodu do iného.
Vrtule - neviem ako to je s pamäťou pri zoznamoch... Koľko
miesta zaberie milión zoznamov,keď v takmer každom sú odkazy na dva susedné
vrcholy?
Takže máš vážený orientovaný graf a máš za úkol najít minimální nebo maximální cestu mezi dvěma vrcholy? Protože jestli ten graf není vážený, tak to je obyčejná Manhattan distance a dá se to spočítat z hlavy. V tom případě to je základní úloha na dynamické programování, budeš potřebovat A*B paměti, pokud chceš znát cestu, kde A,B je L-sup vzdálenost mezi vrcholy. Pokud ti stačí jen ohodnocení cesty, stačí na to min(A,B) paměti, ale A*B času.
Reprezentace grafu, kterou jsem ti poradil, je vždycky výhodnější, než seznam sousedů - menší, efektivnější, rychlejší a dá se vektorizovat.
Áno, je to vážený orientovaný graf. Konkrétne mám zadaných M*N vrcholov(akoby to bolo chodba s rozmermi M*N)a každý vrchol reprezentuje nejaké číslo. A za úlohu mám nájsť takú cestu, z bodu [0,0] do bodu [M,N], aby bol súčet čísiel vrcholov, cez ktoré prejdem, najväčší možný. Hýbať sa môžem iba smerom doprava alebo doľava.
Graf mám zadaný napr. takto:
4 5 (M,N)
2 2 5 1 2
3 3 1 2 1
1 4 3 2 1
3 1 3 2 2
Maximálne číslo, ktoré môžem dostať je v tomto prípade 22.
Algoritmus pro velký graf funguje úplně stejně jako pro ten malý (o kterém jsi říkal, že už ho máš hotový). Ale v paměti potřebuješ mít vždy pouze 2 řádky z matice sousednosti.
Pokud máš korektně napsaný postup přes dynamické programování, tak si všimni, že platí M[i, j] = M[i, j] + max(M[i-1,j], M[i, j-1]), tzn. v paměti ti stačí mít současně vždy pouze řádky i-1 a i.
Pokud máš garanci, že výstupní stupeň každého vrcholu (tzn. počet hran, které z něho vedou) je menší rovno dvěma, zapamatoval bych si graf maticí |V| x 2, přičemž na i-tém řádku by byla čísla vrcholů, do kterých z vrcholu i vede hrana (případně bys tu matici ještě mohl rozšířit o ohodnocení těch hran, pokud bys chtěl).
Vrtule - neviem ako to je s pamäťou pri zoznamoch...
I kdybys každému vrcholu dal spojový seznam (třeba obousměrný), kde budeš uchovávat sousedy, tak budeš mít spotřebu cca 16B na vrchol, ze kterého nevedou žádné hrany (prázdné obousměrný seznam). Hodně záleží, co se ti hodí víc.
Reprezentace grafu, kterou jsem ti poradil, je vždycky výhodnější, než seznam sousedů - menší, efektivnější, rychlejší a dá se vektorizovat.
Jestli to dobře chápu, tak navrhuješ uchovávat si seznam hran. To určitě bude pro některé algoritmy lepší, ale nemyslím, že vždycky. Obecně bude asi dost problém třeba najít hrany vedoucí z i-tého vrcholu.
P.S. Doufám, že jsem nedubloval některý z předchozích příspěvků.
Jestli to dobře chápu, tak navrhuješ uchovávat si seznam hran.
Ano.
To určitě bude pro některé algoritmy lepší, ale nemyslím, že vždycky.
Napadá tě nějaký protipříklad? Trik spočívá v tom, že pokud máš 1000 vrcholů, je naprosto jedno, co použiješ, to jsou pidi-grafy. Ale u velikosti 109 nebo 1012 vrcholů potřebuješ vektorizovat algoritmus a u seznamu sousedů to jde o dost hůř než u matic.
Obecně bude asi dost problém třeba najít hrany vedoucí z i-tého vrcholu.
Pokud bych potřeboval efektivně hledat hrany z vrcholu, stačí mi seřadit matici a přidat primitivní hash-table, takže overhead bude 4B na vrchol. Stejné platí, pokud bych potřeboval hledat hrany do vrcholu, stačí otočit orientaci grafu.
V praxi dokonce ani nepotřebuješ tu hash-tabulku, protože zpravidla nehledáš hrany z i-tého vrcholu, ale hledáš hrany z nějaké množiny vrcholů, takže projíždíš větší část grafu a tenhle problém se v tom ztratí.
Ano, s přidanou hash-table a z praktického pohledu by se tímhle dalo souhlasit.
Zobrazeno 10 zpráv z 10.