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 ?

do góry

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

do góry

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

do góry

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

do góry

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

do góry

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/

do góry

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

do góry

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

do góry

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/

do góry

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

do góry