GoldenLine
Zaloguj się
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Cześć,

mam pewien problem, otóż zastanawiam się jak rozwiązać problem drogi z punktu A do punktu B.
Chodzi o przelot np. z Warszawy do Nowego Jorku. Pomijam połączenie bezpośrednie ze względu na jego banał ;)
Ale co jak nie mamy bezpośredniego połączenia i np. aby dolecieć do NJ musimy przesiąść się w Berlinie lub Paryżu.

I tu jest pytanie, jak wyznaczyć w jak najkrótszym czasie drogę z Warszawy do Nowego Jorku uwzględniając w tym przesiadki? ;)

Oczywiście zależy na szybkości działania skryptu - to taka moja praca domowa...
Link do wypowiedziLink

konto usunięte

Temat: Wyświetlanie połączeń z punktu A do punktu B

http://pl.wikipedia.org/wiki/Teoria_grafów - oto klucz do zagadki :)
Link do wypowiedziLink

konto usunięte

Temat: Wyświetlanie połączeń z punktu A do punktu B

http://www.hotscripts.com/forums/database/45585-solved... - to tez moze pomoc, chociaz temat troche inny
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Paweł P.:
http://www.hotscripts.com/forums/database/45585-solved... - to tez moze pomoc, chociaz temat troche inny


o to trochę pomogło, dzięki, teraz aby muszę poprawić ten kod tak aby wyświetlał wszystkie drogi a nie pierwszą najkrótszą ;)
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Poczytałem trochę o algorytmie Dijkstry, znalazłem go nawet na wikipedii http://en.giswiki.net/wiki/Dijkstra%27s_algorithm#Usag... jednak teraz mam taki problem że chciałbym aby wyświetlało mi wszystkie drogi a nie jedną najszybszą ;) Macie na to jakiś pomysł?

[EDIT]
I jak zrobić aby pod uwagę były brane też godziny odlotu? ;)Adrian P. edytował(a) ten post dnia 04.03.10 o godzinie 13:37
Link do wypowiedziLink
Bartłomiej Ogryczak

Bartłomiej Ogryczak Backend Developer @
Layar

Temat: Wyświetlanie połączeń z punktu A do punktu B

http://en.wikipedia.org/wiki/Breadth-first_search
Link do wypowiedziLink
Michał Jarosz

Michał Jarosz Frontend Developer &
Team Leader

Temat: Wyświetlanie połączeń z punktu A do punktu B

Adrian P.:

o to trochę pomogło, dzięki, teraz aby muszę poprawić ten kod tak aby wyświetlał wszystkie drogi a nie pierwszą najkrótszą ;)

Wszystkie?

Warszawa, Frankfurt, Kraków, Amsterdam, Miami, Ontario, Pekin, Sydney, Katowice, Londyn, Nowy Jork też?
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Chodzi o to żeby pokazał inne drogi którymi mogę się dostać z punktu A bo punktu B ;) tak jak to jest w ztm.waw.pl...
Link do wypowiedziLink
Michał Jastrzębski

Michał Jastrzębski Django-fu, phpjutsu,
sql-do

Temat: Wyświetlanie połączeń z punktu A do punktu B

Mimo wszystko trzeba zdefiniować kryteria połączeń. Wszystkich nie pokaże bo przejazd autobusem z domu ja lotniska, potem z powrotem, i znów z domu na lotnisko i tak 50 razy, a potem dopiero lot to też droga dojazdu...bez sensu ale jednak. Może najkrótsza + jakiśtam procent czasu lotu? Np. jeśli lot najkrótszą trasą trwałby 20min, to wypisze wszystkie opcje trwające 20min +- 5min. Tak działa serwis pkp.pl. Ale zrobienie tego systemu to byłaby niezła jazda algorytmiczna...można wyliczyć najkrótszy czas, potem 2gi z kolei, 3ci itd aż przekroczy tą granicę.
Link do wypowiedziLink
Michał Jarosz

Michał Jarosz Frontend Developer &
Team Leader

Temat: Wyświetlanie połączeń z punktu A do punktu B

Albo ograniczyć ilość przesiadek do jakiejś rozsądnej liczby. (Albo nawet dać użytkownikowi możliwość ustalenia ile maksymalnie przesiadek akceptuje)
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Dopiero w poniedziałek będę miał zajęcia z doktorem to wypytam się dokładniej o ten temat, bo póki co to wstępnie go wybrałem, ale jednak potrzebuję wskazówek jak to zrobić :)
Link do wypowiedziLink
Marcin P.

Marcin P. Zakamuflowany
programista

Temat: Wyświetlanie połączeń z punktu A do punktu B

Narysuj sobie graf połączeń z Warszawy do New York'u. Potem pójdzie już z górki, w sumie pod górkę, bo będziesz musiał rekurencyjnie sprawdzić skąd dokąd można się dostać.

Oczywiście dane można sobie keszować i zapisać to w postaci drzewa.
Link do wypowiedziLink
Michał Jastrzębski

Michał Jastrzębski Django-fu, phpjutsu,
sql-do

Temat: Wyświetlanie połączeń z punktu A do punktu B

Michał Jarosz:
Albo ograniczyć ilość przesiadek do jakiejś rozsądnej liczby. (Albo nawet dać użytkownikowi możliwość ustalenia ile maksymalnie przesiadek akceptuje)

Ilość przesiadek nie zadziała, ponieważ lot z Warszawy do Paryża z przesiadką w Berlinie to tyle samo przesiadek co Warszawa->Moskwa->Paryż...
Link do wypowiedziLink
Jakub L.

Jakub L. Programista

Temat: Wyświetlanie połączeń z punktu A do punktu B

Michał Jastrzębski:
Mimo wszystko trzeba zdefiniować kryteria połączeń. Wszystkich nie pokaże bo przejazd autobusem z domu ja lotniska, potem z powrotem, i znów z domu na lotnisko i tak 50 razy, a potem dopiero lot to też droga dojazdu...bez sensu ale jednak. Może najkrótsza + jakiśtam procent czasu lotu? Np. jeśli lot najkrótszą trasą trwałby 20min, to wypisze wszystkie opcje trwające 20min +- 5min. Tak działa serwis pkp.pl. Ale zrobienie tego systemu to byłaby niezła jazda algorytmiczna...można wyliczyć najkrótszy czas, potem 2gi z kolei, 3ci itd aż przekroczy tą granicę.

Zrób graf skierowany robiąc w miejsca krawedzi AB krawędzie A->B i B->A (drugim powodem są najczęściej godziny rejsów w obie strony i czasem nawet różne czasy), a potem nie dopuszczaj do powstania cyklu.

Czas podróży plus liczba przesiadek powinny być wystarczająco dobrym ograniczeniem.
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Marcin P.:
Narysuj sobie graf połączeń z Warszawy do New York'u. Potem pójdzie już z górki, w sumie pod górkę, bo będziesz musiał rekurencyjnie sprawdzić skąd dokąd można się dostać.

Oczywiście dane można sobie keszować i zapisać to w postaci drzewa.
Tak też o tym myślałem aby zrobić funkcję rekurencyjną z limitem wykonań np. 5x

function find_path($start, $finish, $limit) {
// sprawdzamy czy limit jest większy od 0

// sprawdzenie czy jest połączenie z $start do $finish
// jeśli tak to zapisanie wyniku do nowej tablicy

// zmniejszamy limit o 1

// sprawdzamy połączenia pośrednie
// wywołujemy find_path z tymże start to wyniki aktualnego wywołania
// zapisujemy wyniki do nowej tablicy
}

Oczywiście w zapytaniach będą też brane pod uwagę godziny odlotu/przylotu na danym lotnisku aby potem wyświetlić całkowity czas podróży
Link do wypowiedziLink
Michał Jastrzębski

Michał Jastrzębski Django-fu, phpjutsu,
sql-do

Temat: Wyświetlanie połączeń z punktu A do punktu B

Taki algorytm może powtarzać x razy tą samą trasę. Możnaby wykorzystać algorytm dijkstry, w którym czas na przesiadkę także potraktujemy jako drogę(a droga w całości będzie opisana czasem jazdy:)) oraz z możliwością wykluczania już ustalonych tras. I jak już stworzysz takie coś powtarzaj, póki np. liczba przesiadek nie przekroczy 2, lub różnica w czasie pomiędzy najkrótszą trasą a obecną nie przekroczy 20%. (liczby dodane dla przykładu)
Link do wypowiedziLink
Adrian P.

Adrian P. pamiętaj o tym, kto
chce latać musi
skoczyć

Temat: Wyświetlanie połączeń z punktu A do punktu B

Właśnie już użyłem diagramu dijkstry by określić najkrótszą drogę ;)
Muszę trochę go przerobić lub poszukać/dopisać coś by wyświetlało jeszcze kilka dróg a najlepiej wszystkie :P

Póki co to zjarał mi się laptop i nie mogę pracować także obecnie gdybam sobie...
Link do wypowiedziLink
Michał Jastrzębski

Michał Jastrzębski Django-fu, phpjutsu,
sql-do

Temat: Wyświetlanie połączeń z punktu A do punktu B

Weź kartkę i ołówek i szukaj algorytmu;)A jak załatwisz kompa będzie już z górki. Btw. fajny temat programu:)
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj