Rozkład jazdy

algorytm przeszukiwania grafow

algorytm przeszukiwania grafow

Tyle to ja wiem. Chodziło mi o jakieś konkrety...

Co rozumiesz przez najszybsze połączenie? Takie z najmniejszą ilością przystanków, najmniejszą ilością przesiadek czy może jeszcze inne (np. jedna przesiadka, ale trzeba czekać 8h na przyjazd autobusu :p) Zastanów się też jakimi danymi dysponujesz.

pzdr,
y.

// Sam pomyśl jakimi danymi moze dysponowac, Przecież w rozkładach jazdy rzadko kiedy sa podane odległości, zazwyczaj same czasy. [mf]

Najszybsze połączeni to takie dzięki któremu bedziesz na miejscu najwcześniej. Czekac 8h? [rotfl]

Moja propozycja to chamski duży graf + alg. Dijkstry. Każdy przystanek to węzeł grafu. Krawędzie etykietujesz czasem przejazdu z jednego przystanku na drugi. Bierzesz wszystkie przystaki na danej linii {1,2,...,N} i robisz krawędzie etykietowane czasem przejazdu: {1,2},...{1,N}, {2,3},...,{2,N} itd. aż do {N-1,N}.
Pozostaje problem przystanków z przesiadkami. Załóżmy, że msz np. 3 linie, które krzyżują się na przystanku P.
Linia1: A-...-P
Linia2: B-...-P
Linia3: C-...-P

Tworzysz 3 dodatkowe wierzchołki P1, P2, P3 (takie wirtualne kopie przstanku P). Dzięki temu linia pierwsza ma przebieg: A-...-P1, druga B-...-P2 a trzecia C-...-P3

Z P1 można dojechać do P z kosztem 0 (bo to taka nasza kopia przystanku), analogicznie {P2,P}, {P3,P}. Krawędzie {P1,P2}, {P2,P3}, {P1,P3} symbolizują
przesiadki z jednej linii na drugą i czas przesiadki.

Dla takiego grafu zapuszczasz algorytm Dijkstry dla pary wierzchołków i czekasz ;> W pewnym momencie algorytmu bierze się sąsiadów danego wierzchołka i tu chyba trzeba jeszcze pamiętać rozkład jazdy (nie tyle w wierzchołku co <ort>wogóle</ort> gdzieś) by wiedzieć czy dojechaliśmy przed odjazdem przesiadkowego autobusu czy przed ;-) i dodać do kosztu czas oczekiwania na przyjazd kolejnego busa.

Powyższe to jedynie moje krótkie przemyślenia, nie wiem czy ten algorytm zadziała (teoretycznie powinien :P). W każdym razie masz punkt zaczepienia.

pzdr,
y.

Co do czekania 8h to chyba nigdy Ci nie uciekł pociąg na przesiadce, tudzież autobus w kierunku cywilizacji ;>

O uciekł mi, uciekł. Ale śmieszne wydaje mi się czekanie 8h, tylko po to aby jechać bezpośrednio (bez przesiadek).

POstarm się pomóc Ci w tym projekcie. Fajny pomysł. Godny uwagi i pracy... Postaram się coś wymyśleć w C++ Builderze.

O uciekł mi, uciekł. Ale śmieszne wydaje mi się czekanie 8h, tylko po to aby jechać bezpośrednio (bez przesiadek).

Rzecz w tym, że z tym czekaniem to chodzi o jazdę z przesiadkami... Jeśli w każde miejsce jesteś w stanie dojechać bez przesiadek to gratuluję ;P

pzdr,
y.

Co do samych grafów skierowanych i szukania drogi mam już gotowy działający algorytm w Delphi. Poza tym mam "powiedzmy" gotowy program, który wyszukuje optymalną drogę. Jako dane używam danych o połączeniach lubelskiego MPK. Jestem w trakcie pracy nad przesiadkami (ten algorytm jest dużo bardziej skomplikowany).

Sama idea wydaje się dosyć prosta, ale jest dużo problemów przy pisaniu takiego projektu. Trzeba uwzględnić bardzo wiele czynników..chociażby sama struktura przechowywanych danych i ich ilość...Za tym idzie szybkość wykonywania programu. Struktura grafu musi być uzależniona od godziny i dnia połączenia, ilości autobusów obsługujących trasę i jeszcze kilku innych rzeczy...
Nie jest to proste...Ważny problem to dostęp do danych. Ich zdobycie w użytecznej formie nie jest wcale łatwe...a systematyzowanie nieuporządkownych danych to wyzwanie...Wiem coś o tym..

PS. (niezwiązane z topikiem) Ja bym to rozwiązał na parach... :D

A więc chodzi o problem komiwojarzera ciekawe zagadnienie