eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingalgorytm wyszukiwania autobusu (autobusów)
Ilość wypowiedzi w tym wątku: 15

  • 1. Data: 2010-07-04 08:51:30
    Temat: algorytm wyszukiwania autobusu (autobusów)
    Od: "bagno" <b...@o...pl>

    Witam

    Od razy przyznaje się, że zadania domowego nie odrobiłem (może jakieś 2
    minuty
    szukałem).

    Zastanawiam się na takim algorytmem jaki jest na pkp.pl tyle, że chodzi o
    autobusy.

    Mam listy tras, wiem kiedy dany autobus jest na jakimś przystanku no i wiem
    skąd i gdzie
    chcemy się dostać. Zakładamy oczywiście możliwość przesiadek (dla
    utrudnienia można
    jeszcze założyć, że trzeba będzie wysiąść z autobusu i przejść kawałek na
    inny przystanek -
    dane o najbliższych przystankach i czasie potrzebnym na przejście do nich
    też są).

    I chciałbym wiedzieć na razie jak bardzo będzie to skomplikowany algorytm.

    Wydaje mi się, że tego jest na tyle mało, że możnaby próbować metody
    sprawdzania
    wszystkich możliwości (może po wykluczeniu najbardziej bezsensownych tras)
    ale to chyba
    jednak będzie zupełnie nieoptymalne.

    Jak coś takiego się robi ?




  • 2. Data: 2010-07-04 14:13:10
    Temat: Re: algorytm wyszukiwania autobusu (autobusów)
    Od: Tomasz Sowa <t...@t...NOSPAM.org>

    Dnia Sun, 4 Jul 2010 10:51:30 +0200, bagno napisał(a):

    > Jak coś takiego się robi ?

    http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

    --
    Tomek


  • 3. Data: 2010-07-04 19:52:32
    Temat: Re: algorytm wyszukiwania autobusu (autobusów)
    Od: Mariusz Marszałkowski <m...@g...com>

    On 4 Lip, 10:51, "bagno" <b...@o...pl> wrote:

    Jest "dużo", rośnie wykładniczo. Np. masz docierasz przystanku i masz
    do wyboru 5 decyzji, docierasz do nastepnego przystanku i masz 4
    decyzjie,
    to rośnie jak 5*4*.... Jeśli nie zabezpieczysz przed jazda w kolko to
    ilosc
    tras bedzie nieskonczeni duza.

    > Jak coś takiego się robi ?
    Graf sie robi. Wierzcholki to miejsca na mapie. Krawedzie to koszt
    przejscia/przejazdu od jednego miejsca do drugiego. Przy czym
    koszt moze byc czymkolwiek, czasem, zuzyciem paliwa, preferencjami
    osobistymi, albo kombinacja powyzszych... byle dalo sie go wyrazic
    jakas liczba. Jesli koszt zawsze jest liczba dodatnia to najprosciej
    algorytmem Dijkstry. Jesli pojawiają się ujemne, to Bellmana-Forda.

    Pozdrawiam


  • 4. Data: 2010-07-05 01:32:58
    Temat: Re: algorytm wyszukiwania autobusu (autobusów)
    Od: bartekltg <b...@g...com>

    On 4 Lip, 21:52, Mariusz Marszałkowski <m...@g...com> wrote:

    >
    > Graf sie robi. Wierzcholki to miejsca na mapie. Krawedzie to koszt
    > przejscia/przejazdu od jednego miejsca do drugiego. Przy czym
    > koszt moze byc czymkolwiek, czasem, zuzyciem paliwa, preferencjami
    > osobistymi, albo kombinacja powyzszych... byle dalo sie go wyrazic
    > jakas liczba. Jesli koszt zawsze jest liczba dodatnia to najprosciej
    > algorytmem Dijkstry. Jesli pojawiają się ujemne, to Bellmana-Forda.

    Pamietajmy, ze tutaj koszt (czas) jest zalezny od momentu dotarcia,
    trzeba sie chwile zastanowic, czy nadal Dijkstry bedzie dobry
    (na oko tak).

    pozdrawiam
    bartekltg


  • 5. Data: 2010-07-05 06:34:16
    Temat: Re: algorytm wyszukiwania autobusu (autobusów)
    Od: Wit Jakuczun <w...@g...com>

    W dniu 2010-07-05 03:32, bartekltg pisze:
    > On 4 Lip, 21:52, Mariusz Marszałkowski<m...@g...com> wrote:
    >
    >>
    >> Graf sie robi. Wierzcholki to miejsca na mapie. Krawedzie to koszt
    >> przejscia/przejazdu od jednego miejsca do drugiego. Przy czym
    >> koszt moze byc czymkolwiek, czasem, zuzyciem paliwa, preferencjami
    >> osobistymi, albo kombinacja powyzszych... byle dalo sie go wyrazic
    >> jakas liczba. Jesli koszt zawsze jest liczba dodatnia to najprosciej
    >> algorytmem Dijkstry. Jesli pojawiają się ujemne, to Bellmana-Forda.
    >
    > Pamietajmy, ze tutaj koszt (czas) jest zalezny od momentu dotarcia,
    > trzeba sie chwile zastanowic, czy nadal Dijkstry bedzie dobry
    > (na oko tak).
    >
    Obawiam się, że nie będzie. Co nie znaczy, że podejście programowania
    dynamicznego nie może się tutaj sprawdzić.

    Pozdrawiam,
    Wit Jakuczun


  • 6. Data: 2010-07-06 05:40:40
    Temat: Re: algorytm wyszukiwania autobusu (autobusów)
    Od: Maciej Pilichowski <P...@g...com>

    On Mon, 05 Jul 2010 08:34:16 +0200, Wit Jakuczun
    <w...@g...com> wrote:

    >> Pamietajmy, ze tutaj koszt (czas) jest zalezny od momentu dotarcia,
    >> trzeba sie chwile zastanowic, czy nadal Dijkstry bedzie dobry
    >> (na oko tak).
    >>
    >Obawiam się, że nie będzie.

    Czemu? Wezlami nie sa przystanki, ale pociagi (czy autobusy,
    whatever).

    milego dnia, hej
    --
    Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
    http://www.garaz.pol.pl/


  • 7. Data: 2010-07-06 06:11:34
    Temat: Re: algorytm wyszukiwania autobusu (autobus?w)
    Od: Wit Jakuczun <w...@g...com>

    W dniu 2010-07-06 07:40, Maciej Pilichowski pisze:
    > On Mon, 05 Jul 2010 08:34:16 +0200, Wit Jakuczun
    > <w...@g...com> wrote:
    >
    >>> Pamietajmy, ze tutaj koszt (czas) jest zalezny od momentu dotarcia,
    >>> trzeba sie chwile zastanowic, czy nadal Dijkstry bedzie dobry
    >>> (na oko tak).
    >>>
    >> Obawiam się, że nie będzie.
    >
    > Czemu? Wezlami nie sa przystanki, ale pociagi (czy autobusy,
    > whatever).
    >
    Temu, że OP nie podał dokładnego sformułowania. Napisał jedynie, że
    szuka trasy ale kryteriów nie podał (najkrótsza, najszybsza, dowolna?).
    Przykład: http://www.math.tau.ac.il/~hassin/restrictedPath.pdf
    Artykuł opisuje problem gdzie szukamy najkrótszej (najtańszej) trasy z
    ograniczeniem na czas trwania. Problem jest NP-zupełny. W artykule
    podane są pseudowielomianowe algorytmy aproksymacyjne

    Twoja sugestia, żeby spojrzeć na problem jako sieć połączeń między
    autobusami wydaje się być ciekawa. Z tym, że może zadziałać jedynie
    dlatego, że godziny wyjazdu i przyjazdu są ściśle określone (Dzięki temu
    dałoby się skonstruować graf powiązań między autobusami z góry (nie
    zależny od rozwiązania)). No i trzeba by założyć, że nie jest to problem
    z przykładu powyżej.
    Dopuszczając możliwość przyjechania w przedziale czasowym (np. rozkład
    +/- 15min) problem staje się NP-Complete.

    Swoją tu jest przykładowy kod:
    http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/
    r_c_shortest_paths.html
    ze wskazaniem na literaturą. Kodu nie testowałem więc nie wiem na ile to
    działa.

    Pozdrawiam,
    Wit Jakuczun


  • 8. Data: 2010-07-06 07:15:31
    Temat: Re: algorytm wyszukiwania autobusu (autobus w)
    Od: Mariusz Marszałkowski <m...@g...com>

    On 6 Lip, 08:11, Wit Jakuczun <w...@g...com> wrote:


    > Z tym, że może zadziałać jedynie
    > dlatego, że godziny wyjazdu i przyjazdu są ściśle określone (Dzięki temu
    > dałoby się skonstruować graf powiązań między autobusami z góry (nie
    > zależny od rozwiązania)).
    Przy takich założeniach a. dijkstry powinien dać trasę o najmniejszym
    koszcie. Jest stała ilość przystanków, stała ilość tras, a "trasy"
    będące
    odpowiednikiem kosztu oczekiwania można dobudować dynamicznie w
    trakcie działania algorytmu.
    Pozdrawiam



  • 9. Data: 2010-07-07 05:15:29
    Temat: Re: algorytm wyszukiwania autobusu (autobus?w)
    Od: Maciej Pilichowski <P...@g...com>

    On Tue, 06 Jul 2010 08:11:34 +0200, Wit Jakuczun
    <w...@g...com> wrote:

    >Dopuszczając możliwość przyjechania w przedziale czasowym (np. rozkład
    >+/- 15min) problem staje się NP-Complete.

    Ale wtedy sie szukac czegos innego -- najmniej ryzykownego przejazdu o
    najkrotszym czasie. I wtedy zakladasz, ze przyjezdzasz te 15 minut po
    czasie.

    milego dnia, hej
    --
    Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
    http://www.garaz.pol.pl/


  • 10. Data: 2010-07-07 06:30:01
    Temat: Re: algorytm wyszukiwania autobusu (autobus?w)
    Od: Wit Jakuczun <w...@g...com>

    W dniu 2010-07-07 07:15, Maciej Pilichowski pisze:
    > On Tue, 06 Jul 2010 08:11:34 +0200, Wit Jakuczun
    > <w...@g...com> wrote:
    >
    >> Dopuszczając możliwość przyjechania w przedziale czasowym (np. rozkład
    >> +/- 15min) problem staje się NP-Complete.
    >
    > Ale wtedy sie szukac czegos innego -- najmniej ryzykownego przejazdu o
    > najkrotszym czasie. I wtedy zakladasz, ze przyjezdzasz te 15 minut po
    > czasie.
    >
    Jak szukasz najmniej ryzykownego to tak.

    Pozdrawiam,
    Wit

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: