GoldenLine
Zaloguj się
Piotr K.

Piotr K. Senior DevOps
Engineer

Temat: rozklad jazdy

Czesc,
Mam pytanie. Znacie moze jakis algorytm do wyszukiwania polaczen np. autobusowych? Mam dane o przystankach liniach ulicach czasach itd. Nie musi byc super wydajny, po prostu zeby szukal, uwzglednial przesiadki itp rzeczy.
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: rozklad jazdy

jedyne co na szybko mi do glowy przychodzi do dijkstra :S
Link do wypowiedziLink
Piotr K.

Piotr K. Senior DevOps
Engineer

Temat: rozklad jazdy

Czytalem o nim, czyli szukac mam w algorytmach wyszukiwnia najkrotszej drogi w grafie, no to troche tego jest.
Link do wypowiedziLink
Rafał D.

Rafał D. freelancer

Temat: rozklad jazdy

Oprócz czasów przejazdu pomiędzy przystankami (węzłami) musisz uwzględnić godz. odjazdu kolejnego np. autobusu.
Co z tego, że szybko dojedziesz do miejsca przesiadkowego, bo tam masz szybki transport do celu, skoro jego częstotliwość jazdy jest mała i utkniesz tam w oczekiwaniu na ten szybki transport..

Czyli czasy przjazdów i godz. odjazdów należy brać pod uwagę - to trochę komplikuje problem..
Link do wypowiedziLink
Marcin Paweł S.

Marcin Paweł S. programista
C#/SQL/PHP

Temat: rozklad jazdy

Fajny temat :) w moim mieście średnio wyjdzie (Rzeszów)
chcesz to komercyjnie wykorzystać ?? na stronie czy to jakiś "szkolny" projekt ??

najwygodniejsze było by urzycie języka deklaratywnego a potem próba zbudowania tego samego w PHP(jeśli to wogule musi być w PHP)
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: rozklad jazdy

Rafał D.:
Oprócz czasów przejazdu pomiędzy przystankami (węzłami) musisz uwzględnić godz. odjazdu kolejnego np. autobusu.
Co z tego, że szybko dojedziesz do miejsca przesiadkowego, bo tam masz szybki transport do celu, skoro jego częstotliwość jazdy jest mała i utkniesz tam w oczekiwaniu na ten szybki transport..

Czyli czasy przjazdów i godz. odjazdów należy brać pod uwagę - to trochę komplikuje problem..

ja bym czas odjazdu dodal do czasu w jakim autobus dojedzie do nastepnego wezla i to przyjal jako wage krawedzi w grafie - im dluzej trzeba by czekac na autobus tym "dluzsza" jest droga :P

imho jezyki skryptowe tak sobie nadaja sie do rozwiazywania takich problemow :SŁukasz Cepowski edytował(a) ten post dnia 26.02.09 o godzinie 10:38
Link do wypowiedziLink

konto usunięte

Temat: rozklad jazdy

Fajny pomysł tylko pamiętaj o jednym. Rozkład jazdy to baza danych podlegajaca ustawie o prawach autorskich i pokrewnych ;)
Link do wypowiedziLink

konto usunięte

Temat: rozklad jazdy

tego sobie poszukaj. ten problem nie jest rozwiązywalny aktualnie.

http://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera

Simulated Annealing
Lin-Kernighan Algorithm
Link do wypowiedziLink
Wojciech S.

Wojciech S. BushidoIT.com

Temat: rozklad jazdy

Tomasz Koda:
tego sobie poszukaj. ten problem nie jest rozwiązywalny aktualnie.

http://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera

Simulated Annealing
Lin-Kernighan Algorithm

to że jest np-trudny nie znaczy że jest nierozwiązywalny... http://pl.wikipedia.org/wiki/Problem_NP-trudny
Link do wypowiedziLink

konto usunięte

Temat: rozklad jazdy

Łukasz Cepowski:

imho jezyki skryptowe tak sobie nadaja sie do rozwiazywania takich problemow :S[/edited]

A czemuz mialyby sie nie nadawac?

Tutaj jest calkiem fajnie dzialajaca realizacja takiej wyszukiwarki polaczen dla Krakowa - http://www.mpkoogle.rox.pl/.
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: rozklad jazdy

Marcin Olichwirowicz:
A czemuz mialyby sie nie nadawac?

Tutaj jest calkiem fajnie dzialajaca realizacja takiej wyszukiwarki polaczen dla Krakowa - http://www.mpkoogle.rox.pl/.

srednio mi sie widzi przechodzenie grafu z np: milionem wezlow w php :P

nie ma to jak c/c++, wskazniki i wyniki w mniej niz 1s :]
Link do wypowiedziLink
Piotr Jurczyński

Piotr Jurczyński Grafik, Webmaster,
Studio Wyobrazni

Temat: rozklad jazdy

http://mapy.google.pl/maps?ie=UTF8&dirflg=r&ll=53.7747...

to z takich ciekawostek. Tak wiec mozliwosc jest i google o tym wie ;).
Marcin Olichwirowicz:
Tutaj jest calkiem fajnie dzialajaca realizacja takiej wyszukiwarki polaczen dla Krakowa - http://www.mpkoogle.rox.pl/.
Swoja droga dobrze wiedziec, ze istnieje cos takiego dla Krakowa :).. chociaz czasami daje dzikie wyniki.Piotr Jurczyński edytował(a) ten post dnia 26.02.09 o godzinie 12:32
Link do wypowiedziLink

konto usunięte

Temat: rozklad jazdy

Mi sie wydaje ze takie przechodzenie po grafie powinno byc realizowane w bazie po stronie sql, czy to polaczenie realizowane bedzie w jezyku kompilowanym czy skryptowym :)
Link do wypowiedziLink
Łukasz C.

Łukasz C. Senior Technical
Architect

Temat: rozklad jazdy

Marcin Olichwirowicz:
Mi sie wydaje ze takie przechodzenie po grafie powinno byc realizowane w bazie po stronie sql, czy to polaczenie realizowane bedzie w jezyku kompilowanym czy skryptowym :)

mam szczere watpliwosci czy w przypadku gdy krawedzi grafu beda miliony bedzie to wystarczajaco wydajne pozatym pisanie funkcji po stronie bazy do tego tez srednio przyjamnie mi wyglada :|
Link do wypowiedziLink
Marcin Paweł S.

Marcin Paweł S. programista
C#/SQL/PHP

Temat: rozklad jazdy

na bazie (MS SQL) robiłem takie wynalazki(sudoku, komiwojadzer, kto choduje rybki i kilka innych) i działało nadspodziewanie dobrze ... co nie znaczy że miało jakieś szanse z prologiem albo gams'emMarcin Paweł Stasiak edytował(a) ten post dnia 26.02.09 o godzinie 14:23
Link do wypowiedziLink

konto usunięte

Temat: rozklad jazdy

No i ja z tego co wiem to bazy SQL sie swietnie sprawdzaja co do grafow :) Nigdy jednak nie robilem zadnych statystyk wydajnosci... Mysle ze mimo wszystko milion wezlow to troche abstrakcyjne co do rozkladu jazdy autobusow. Nawet biorac milion to przy madrze porobionych widokach i procedurach mogloby to smigac calkiem milo :)
Link do wypowiedziLink
Marcin Paweł S.

Marcin Paweł S. programista
C#/SQL/PHP

Temat: rozklad jazdy

Kiedyś czytałem artykuł o systemie zbudowanym na sybase(chyba) do optymalizacji róchu lotniczego który działał na lotnisku.. firma która to wdrorzyła opisywała że to sprawdza kilka milionów regół biznesowych w sekundzie (co kolwiek to dla nich znaczy)
Link do wypowiedziLink
Bartosz Ratajczyk

Bartosz Ratajczyk MS SQL Developer

Temat: rozklad jazdy

Tutaj jest calkiem fajnie dzialajaca realizacja takiej wyszukiwarki polaczen dla Krakowa - http://www.mpkoogle.rox.pl/.

Tak OT - dla Warszawy: http://autobuser.pl/
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

rozkład jazdy (przesiadki)




Wyślij zaproszenie do
Anuluj