NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Jozef
Člen
Avatar
Jozef:30.4.2015 20:11

Zdravím,
mám problém. Neviem, akým spôsobom mám reprezentovať ohodnotený, orientovaný graf,ktorý môže mať až 1 000 000 vrcholov. Pre malé čísla som používal maticu susednosti, ale tá by pre milión vrcholov bola 1 000 000 x 1 000 000, čo je pamäťovo nemožné. Vopred vďaka za rady :)

Odpovědět
30.4.2015 20:11
I'm not afraid to die on a treadmill
Avatar
coells
Tvůrce
Avatar
Odpovídá na Jozef
coells:30.4.2015 20:33

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.

 
Nahoru Odpovědět
30.4.2015 20:33
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Jozef
Martin Dráb:30.4.2015 21:27

Nebo jej reprezentuj seznamem sousedů, tzn. pro každý vrchol měj seznam vrcholů, do kterých z něho vede nějaká hrana.

Nahoru Odpovědět
30.4.2015 21:27
2 + 2 = 5 for extremely large values of 2
Avatar
Jozef
Člen
Avatar
Jozef:30.4.2015 22:19

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?

Nahoru Odpovědět
30.4.2015 22:19
I'm not afraid to die on a treadmill
Avatar
coells
Tvůrce
Avatar
Odpovídá na Jozef
coells:30.4.2015 22:33

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.

 
Nahoru Odpovědět
30.4.2015 22:33
Avatar
Jozef
Člen
Avatar
Odpovídá na coells
Jozef:30.4.2015 22:45

Á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.

Nahoru Odpovědět
30.4.2015 22:45
I'm not afraid to die on a treadmill
Avatar
coells
Tvůrce
Avatar
Odpovídá na Jozef
coells:30.4.2015 22:58

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.

 
Nahoru Odpovědět
30.4.2015 22:58
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Jozef
Martin Dráb:1.5.2015 11:11

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ů.

Editováno
Nahoru Odpovědět
1.5.2015 11:11
2 + 2 = 5 for extremely large values of 2
Avatar
coells
Tvůrce
Avatar
Odpovídá na Martin Dráb
coells:1.5.2015 12:20

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í.

 
Nahoru Odpovědět
1.5.2015 12:20
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na coells
Martin Dráb:1.5.2015 13:58

Ano, s přidanou hash-table a z praktického pohledu by se tímhle dalo souhlasit.

Nahoru Odpovědět
1.5.2015 13:58
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.