Rozkład jazdy

Odpowiedz Nowy wątek
2004-11-10 17:22
0

Muszę napisać program przeszukujący rozkład jazdy autobusów w poszukiwaniu najszybszego połączenia. Zdaję sobie sprawę, że nie jestem pierwszy i stąd moje pytanie: ma ktoś może gotowy algorytm przeszukiwania (zresztą i tworzenia) bazy polaczen w poszukiwaniu najszybszego?

Pozostało 580 znaków

2004-11-10 17:58
0

algorytm przeszukiwania grafow


I spojrzał Bóg na naszą pracę, i był zadowolony. Zapytał się o zarobki... usiadł i zapłakał


http://wedrowcy.elk.pl

Pozostało 580 znaków

2004-11-10 18:23
0

algorytm przeszukiwania grafow

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

Pozostało 580 znaków

2004-11-10 22:17
y.
0

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]

Pozostało 580 znaków

2004-11-10 23:25
0

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


JKM czy HGW?

Pozostało 580 znaków

2004-11-11 16:09
y.
0

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 ;>

Pozostało 580 znaków

2004-11-12 01:07
0

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


JKM czy HGW?

Pozostało 580 znaków

2004-11-12 18:42
Milo
0

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

Pozostało 580 znaków

2004-11-12 20:59
y.
0

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.

Pozostało 580 znaków

2004-11-13 18:52
0

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


Pozostało 580 znaków

2004-11-13 23:06
0

A więc chodzi o problem komiwojarzera ciekawe zagadnienie


To Like What You Have Is To Have What You Like
Jedyne co mam to złudzenia, ze mogę mieć pragnienia, bo Ta, która wiecznie zawodzi, wiecznie też jest przedmiotem nadziei. Najbardziej odczujesz tego brak gdy będzie obok i nigdy nie będzie Twoja.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0