Aktív témák

• #138 P.H. senior tag kicsitomi88 #134

  2008-03-06 19:39:04 #138

  Ö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

  

  P.H.

  senior tag

  válasz kicsitomi88 #134 üzenetére

  Szegedre jársz - ha nem tévedek -, gondolom, az Algoritmusok és adatszerkezetek tárgy ismerős (lesz, másodév). Oda az azonos című, részben helyi szerkesztésű könyv alapvető (nagy, fekete az a kiadása, ami nekem is megvan), abban nézz körül pl.

  Ahogy írták is, a két alapvető gráftárolási megközelítés a mátrixos és a listás. Pár pro és kontra mindkettőre:
  Mátrix-alapú:
  - az adatszerkezet mérete exponenciális a pontok számával, mivel minden pont-pont kapcsolat helye - ha nem is lézetik ilyen - szerepel benne, ezért sűrű gráfok esetén érdemes alkalmazni
  - Ha a kapcsolatoknak/éleknek több tulajdonsága is van (nem csak a hossza), akkor több, párhuzamos mátrix vagy nagyobb elemi mátrixelem-méret szükséges
  - nagyon hatékony algoritmusok vannak a legrövidebb utak meghatározására (ebből érdemes kiindulni amúgy, az összes lehetséges még könnyű, a többi eléggé elbonyolítható), de nehéz dinamikussá tenni.

  Lista-alapú:
  - nagyon hatékony adattárolási forma ritka mátrixokra: felsorolod a pontok mellé, hogy mely pontokkal állnak kapcsolatban
  - viszont általános megoldásokban egyik kulcsjellemzője az egy ponthoz tartozó maximális (előre látott) lehetséges kapcsolatok száma, ennek változásával a hozzá tartozó algoritmusok is jelentősan változhatnak
  - kézbentarthatóan (= lineárisan) skálázódik az erőforrásigénye (memória, file) a pontok számának növekedésével
  - 'elég' hatékony algoritmusok vannak a legrövidebb utak meghatározására, de kis innovációval az eredetiekhez képest mindenképpen szükséges
  - a tulajdonséggal rendelkező kapcsolatok adott szituációban való kiértékelése nagyon egyszerű, akár tiltással, akár helyzetenkénti eltérő súlyozással, stb.

  A buszjárat-feladat (a megállókkal) nagyon ritka gráfnak fogható fel, viszont rendelkezik jó pár további - dinamikus - kapcsolattulajdonsággal (várakozási idő, a célútvonal időintervalluma (reggel-délben-este), átszállás stb.), ezért - főleg nagyszámú pontnál - alkalmasabb a listás megközelítés, mint a mátrixos. Erre nagyon jó kiindulópont az előbbiekben linkelt Dijkstra-algoritmus.

Aktív témák