[megoldva] Erős gépen gráfelméleti számítás

UNIX haladó

Van-e valaki, aki egy általam adott 8200 csúcspontú (12000 élű) gráfban R-rel (igraph) megkeresne két pont közötti útvonalat?
Próbáltam a saját gépemen, de napokig nem futott le; erős gép kellene hozzá.

  • 2375 megtekintés

( Nyosigomboc v | 2017. 01. 22., v – 10:24 )

Milyen algoritmust hasznalsz? Mennyire tudtad tobbszalusitani? Ha jol emlekszem, a Dijkstra n^2-es, es nincs nagyon sok csucsod.

Egyebkent egy i7 920-asom van (HT-el 8 mag) 18GB RAMmal (3-asaval bovitheto, nem eliras). Ezzel be tudok szallni.

--
A strange game. The only winning move is not to play. How about a nice game of chess? - Wargames

( mraron | 2017. 01. 22., v – 11:30 )

tényleg nyolcezerkétszáz csúccsal és tizenkétezer éllel rendelkezik az említett gráf? mert ha igen akkor nem nagyon értem a kérdést... továbbá útvonal alatt mit értesz?

( ibenny v | 2017. 01. 22., v – 12:08 )

Milyen algoritmust használsz?

Szinte kizárt, hogy egy ekkora probléma optimális megoldásához tényleg napok kellenek, valószínűleg lehetne még alakítani a modellen, hogy gyorsabb legyen a megoldás, esetleg más eszközt is meg lehetne fontolni (valamelyik modellező nyelvre és egy profi solver-re gondolok elsősorban).

( uid_15426 | 2017. 01. 22., v – 11:58 )

Valami progress status van hozzá? Az itthoni desktopom dual 2660v3, megprobalhatok segíteni.

----------------------
while (!sleep) sheep++;

( persicsb | 2017. 01. 22., v – 12:00 )

Mit számolsz pontosan? Ez a gráf nem is nagy méretű.

Az osszes _legrovidebb_ ut viszont (ami ugye itt es altalaban a gyakorlatban kell) n^3 alatt megtalalhato. Kapasbol a Dijkstra egy pontbol az osszes tobbibe megmondja n^2 alatt, akkor ha ezt butan n csucsra lefuttatom, hogy lenne exponencialis?

--
A strange game. The only winning move is not to play. How about a nice game of chess? - Wargames

Legyenek a csúcsok egy n-oldalú négyzet (egész)rácspontjai, az élek csak a szomszédosak között: "jobbra" ha vízszintes, "fel", ha függőleges (tetszés szerint adhatunk hozzá balra és le linkeket). Ekkor a gráfban a bal alsó és jobb felső pont között a legrövidebb út 2n hosszú és 2n alatt az n különböző ilyen van (n db J betű és n db F betű összes sorrendje), ami elég sok - Stirling nélkül is látható, hogy legalább 2^n.

Igen, ha vissza kell adnod az osszes utat, az sok ido (es sok tarhely, szoval nem csak idoben, tarban is exponencialis).
A legtobb ilyen feladat valamilyen optimalizalasrol szol, ahol altalaban egyetlen, valamilyen szempontbol optimalis (minimalis koltsegu) ut a kerdes. Ezt a korabban emlitett algoritmusok megadjak, es amikor a minimalis hosszt kiszamitod, nyilvan tudsz tartani egy ilyen minimalis utat is, szoval azt is megadja.

De kozben rajottem, hogy mi a felreertes oka: en az osszes pontpar kozti optimalis utra irtam az n^3-ot (mert a Dijkstra az egyik csucsbol az osszesbe vezeto optimalis utat megadja n^2 alatt). Ket adott csucs kozt futo osszes minimalis hosszu ut leirasa persze exponencialis lesz. Ket csucs kozt futo osszes ut (esetleg osszes seta) meg ennel is durvabb, teljes grafban n! a permutaciok miatt.

--
A strange game. The only winning move is not to play. How about a nice game of chess? - Wargames