Új hozzászólás Aktív témák

• #2391 Radíros csendes tag Gerghu #2380

  Új Válasz 2006-12-08 16:53:51 #2391

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Radíros

  csendes tag

  válasz Gerghu #2380 üzenetére

  És (#2385) Joooe üzenetére...
  
  Ez a bitmátrix egy csúcs-szomszédsági mátrix,
  amely azt mondja meg az M[i,j] elemben, hogy
  az i-edik csúcsból vezet-e él a j-edik csúcsba.
  (Pl. ha igen: magas a bit, ha nem, akkor alacsony)
  
  Ha ezt érted élmátrix alatt, akkor a szkópban lehet
  a következő megoldás is:
  1. állítsd elő a mátrix tranzitív lezártját
  2. a tranzitív lezártból könnyen jönnek
  az erős komponensek egy rendezésre
  visszavezethető halmaz-osztályozással
  
  Sajnos a tranzitív lezárt számítása n^3 * log n műveletigényű,
  viszont könnyen párhuzamosítható és a hw-be épített
  bitműveleteket is jól kihasználja.
  (Az én logikám szerint ezt a legegyszerűbb implementálni.)
  
  Ha valaki felcsigázódott szívesen részletezem...
  

• #2385 Joooe tag Gerghu #2380

  Új Válasz 2006-12-08 05:02:36 #2385

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Joooe

  tag

  válasz Gerghu #2380 üzenetére

  Én inkább egy bitmátrixot tartanék megfelelőnek erre a feladatra.
  A memóriában az is elfér (10000^2/8 = kb. 12 MB)
  Bár elgondolkodtató, hogy ez a megközelítés nem használja ki az élek relatíve alacsony számát.
  
  Ami gyorssá teheti a megvalósítást, hogy ha a mátrix azt mutatja, hogy az i-edik csúcsból elérhető a j-edik, akkor a j-edik sort hozzá VAGY-oljuk az i-edik sorhoz, ezzel tovább bővítve az i-ből elérhető csúcsok listáját, azokkal ami j-n keresztül elérhető.
  
  Ez mindenféle implementációban elvégzendő művelet, hogy megvizsgáljuk, hogy mi van ha arra megyünk, de azt hiszem így tudjuk leggyorsabban megtenni. Így processzortól függően egyetlen művelet során nagyon sok (64?) csúcsra történik meg a vizsgálat.
  
  Az még egy kicsit elgondolkodtató, hogy mikor végeztünk, hiszen ezt többször el kell végezni, de ha végeztünk, akkor azokat a csúcsokat listázzuk amire mátrix[i,i]=1, azaz elérhető magából maga, azaz tagja valamely irányított körnek.
  
  
  
  [Szerkesztve]
  
  [Szerkesztve]

• #2381 Jester01 veterán Gerghu #2380

  Új Válasz 2006-12-07 15:27:17 #2381

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Jester01

  veterán

  válasz Gerghu #2380 üzenetére

  És ez le fog futni 0.3s alatt? Főleg java-ban?

Új hozzászólás Aktív témák