Witam,

pisze wyszukiwarkę do połączeń komunikacyjnych.
Struktura aplikacji wygląda w ten sposób:
1. Każdy punkt (przystanek autobusowy) oznaczony jest identyfikatorem oraz współprzędnymi x i y
2. Linia autobusowa zawiera punkty

Implementacja w bazie danych wygląda tak:


Połączenia mogą być również z przesiadkami, czyli w punkcie przecięcia się linii możliwość przesiadki do innej linii.
W skrócie, wyszukanie wszystkich możliwych połączeń.

Mój problem polega na tym, że nie wiem jak zabrać się za wyszukiwanie połączęń.
Może istnieje już na to jakiś algorytm, który mógłbym wykorzystać.
Czy ktoś juz robił coś podobnego i może podzielić się doświadczeniem?

http://www.artfulsoftware.com/infotree/que...amp;bw=1280#766

Pamiętaj, że to jest tylko zobrazowany przykład. Wydaje mi się, że można zastosować dodatkowe techniki do ewentualnej optymalizacji

Heh, właśnie w hyde parku toczy się dyskusja, jak bardzo matematyka się przydaje w informatyce . Ten temat to złoty dowód .

eai -> taką bazę możesz od razu do kosza wyrzucić. Twój problem to klasyczne wyszukiwanie najkrótszej ścieżki w grafie i do tego zupełnie niepotrzebna jest znajomość lokalizacji przystanków w przestrzeni. Algorytmy rozwiązujące ten problem omawia chyba każda przyzwoita książka do algorytmów. Najpierw przemyśl i zrozum zasady, które będą kierowały działaniem systemu, a dopiero potem bierz się za phpMyAdmina, inaczej będziesz zmierzać prosto ku klęsce. To jest zasada, którą warto zapamiętać nie tylko do tego, ale też wielu innych projektów.

Nie do końca się z Tobą zgodze, pozycja (x,y) jest mi potrzebna ze względu na to, że muszę określić odległość z punktu A do B jadąc ścieżkami, drugim elementem jest ilość przesiadek - zmian linii (im mniej tym lepiej). Wszystkie możliwości dojazdu z punktu A do B, mają być wyświetlone w formie listy posortowane względem ilości przesiadek, odległości (czasu podróży),

Co do przydatności matematyki w informatyce zgadzam się z Tobą, bez niej ani rusz.

I co Ci niby da informacja, że punkty A i B mają współrzędne (100,100) oraz (200,200), a C i D: (300,300) oraz (400,400), kiedy między jednym a drugim czas przejazdu będzie wynosić 2 minuty, a między trzecim a czwartym osiemnaście? Bardzo fajnie, że wiesz, jak to wszystko ma funkcjonować od strony klienta, ale od strony algorytmicznej Twoja koncepcja jest wyjątkowo nieprzemyślana. Pytałeś o podzielenie się doświadczeniem, więc dzielę się doświadczeniem. Sam takiego systemu nie pisałem, ale raz że znam trochę algorytmikę i matematykę, a dwa że interesuję się mocno zagadnieniami komunikacyjnymi czysto hobbystycznie (i trzy że znajomi robią coś takiego w ramach całorocznego projektu inżynierskiego). To, co Ci jest potrzebne, to czasy przejazdu między przystankami i organizator komunikacji miejskiej właśnie nimi się posługuje przy ustalaniu rozkładów jazdy, a nie współrzędnymi przystanków. Te można bardzo łatwo wyrazić w formie grafowej, co sprowadza nas z powrotem do problemu wyszukiwania ścieżki w grafie i tego, że Twoja baza jest do wyrzucenia, bo przechowujesz w niej zupełnie inne informacje niż te, które Ci są faktycznie potrzebne.

robiłem coś takiego z nauczycielem na informatyce
i tak jak pisali koledzy to po prostu najkrótsza droga w grafie ;-)
zamiast współrzędnych podawaj odległości od najbliższych przystanków - bo gwarantuję, żę na współrzędnych się wyłożysz (bo nie spotkałem miasta, gdzie drogi byłyby prowadzone liniami prostymi od przystanku do przystanku...)

Po zgłębieniu tematu grafów, doszedłem do wniosku, że mieliście racje.


Polecam materiały, tym którzy są zainteresowani tematem:
http://www.rafalnowak.pl/wiki/images/e/e6/...aRNO_graphs.pdf
http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol009.php
http://en.giswiki.net/wiki/Dijkstra%27s_algorithm