Hirdetés

  2. Fórumok
  3. Szoftverfejlesztés
  4. Hogyan / Hogyan ne programozzunk?
  5. (téma lezárva)
Keresés

Aktív témák

  • #141 Vico87 tag kicsitomi88 #139
    #141
    Ö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

    Vico87

    tag

    válasz kicsitomi88 #139 üzenetére

    Ha ez már egy "hogyan / hogyan ne programozzunk" topic, akkor leírom, hogy mindig érdemes algoritmuselméleti könyvben megnézni, ha valamire szükségünk van algoritmusra, ugyanis ha van benne, akkor nagy valószínűséggel jobb, mint amit mi találnánk ki, és még meg sem kell erõltetni magunkat (és így mindenki jobban jár).

    Egy pár "híres" algoritmus:
    gráfok : Dijkstra, Floyd, Bellman-Ford
    rendezés : beszúrásos, összefésüléses, gyorsrendezés, kupac
    keresés : lineáris, bináris

    Ezekhez persze "járnak" adatszerkezetek is. És még egy tanács : ha algoritmusról van szó, akkor biztosan nem az elsõ gondolat a helyes :D.

  • #140 P.H. senior tag kicsitomi88 #139
    #140
    Ö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 #139 üzenetére

    "Miert is erzem ugy, hogy ezt elobb tanulni(tanitani) kene mint csinalni(feladni otthonra)..."

    Ez azért árulkodó: nehogy túlbonyolítsd! Ebbe a hibába sokan beleesnek. Csak azt oldd meg, ami a feladat. :)
    Ha ez túlmutat azon, amit eddig tudsz/tudnod kellene, érdemes megkérdezni még egyszer, hogyan értették; lehet, hogy nem is az a feladat, amit gondolsz.

    Bár az olvasgatás nem árthat meg :)

  • #138 P.H. senior tag kicsitomi88 #134
    #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.

  • #136 cucka addikt kicsitomi88 #134
    #136
    Ö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

    cucka

    addikt

    válasz kicsitomi88 #134 üzenetére

    gráfot csúcsmátrixban vagy éllistával szokás tárolni, legrövidebb utak kereséséhez meg nézz utána a dijkstra algoritmusnak, amit célszerű az első reprezentációra megírni.
    (csúcsmátrixnál a mátrix (x,y) pontjában az x-ből y-ba menő él hosszát tárolod el, éllistánál pedig minden csúcshoz tartozik egy lista, amelyben az adott csúcs szomszédai vannak.)

    elég rég tanultam ezeket, remélhetőleg jól emlékszem a terminológiára :)

  • #135 shev7 veterán kicsitomi88 #134
    #135
    Ö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

    shev7

    veterán

    válasz kicsitomi88 #134 üzenetére

    ha jol emlekszem ehhez az algoritmushoz egy egyszeru matrix a legcelszerubb, ami azt tarolja, hogy mennyi a tavolsag (a te esetedben ido a ket pont kozott) de igazad vna, egy csomo mindent figyelmen kivul hagytam... lehet, hogy felepited a grafot, de adott idopontban ott nem is jar busz... tovabb kell gondolni az algoritmust :)

  • #133 shev7 veterán kicsitomi88 #132
    #133
    Ö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

    shev7

    veterán

    válasz kicsitomi88 #132 üzenetére

    szerintem vegyel elo egy algoritmuselmelet konyvet :) fogsz talalni olyan adatszerkezetet, amiben konnyen tarolhatsz grafokat, es amin gyorsan el tudod vegezni a legrövidebb ut kereseset. Azt a pseudo kodot akarmilyen kodda atirni nem nagy melo, gyorsabbat ugysem talalsz, es nem kell feltalalnod a spanyolviaszt :)

    Sot nem is kell algel konyv itt szepen le van irva a Dijkstra algoritmus.

Aktív témák

Hirdetés