Teoria grafów i znajdowanie najkrótszej ścieżki

0

Witam. Postanowiłem urozmaicić swój serwis o plan kursowania linii autobusowych. Program będzie wyświetlał informacje o numerach linii autobusowych, które zawiozą nas z punku A do punktu B możliwie najkrótszą droga, z możliwością doprecyzowania, czy mogą być przesiadki (możliwa krótsza droga), czy nie (możliwa dłuższa droga). Rzecz nie w tym jak to zaimplementować, tylko na co powinienem zwrócić uwagę i z jakich algorytmów skorzystać. Rozumiem, że będzie to graf nieskierowany? Do przeszukiwania chciałem zastosować algorytm Dijkstry, ponieważ wagi ujemne nigdy nie będą? Kiedy w ogóle mogą wystąpić wagi ujemne i co oznaczają? Czy można to zrealizować wykorzystując tylko samo przeszukiwanie drzewa przez DFS? A może w ogóle da sie to w inny sposób rozwiązać, nie wykorzystując grafów? Wszelkie wypowiedzi w temacie mile widziane :)

0
  1. Najlepszy będzie algorytm A*, Dijkstra robi to samo, ale jest wolniejszy.

  2. Użyj wag dodatnich, by odpowiadały odległościom między wierzchołkami grafu, o wagach ujemnych po prostu nie myśl ;)

  3. Możliwe, że będzie konieczność zastosowania grafu skierowanego (jeśli autobus inaczej jedzie w jedną stronę, inaczej w drugą ?).

0

Dziękuję za odpowiedź :) Zakładam, że tak samo kursuje w obie strony, ale może to być złe założenie heh.

0

Najlepszy będzie algorytm Dijkstry. Bez sensu jest stosowanie algorytmu przybliżonego A*, który może wcale nie znaleźć najkrótsze drogi, skoro dijkstra wcale nie jest aż tak kosztowny, a daje odpowiedź na 100% poprawną, i do tego będzie działał w ułamku sekundy nawet dla sieci z 1000000 połączeń, a takiej to nawet w największym mieście nie znajdziemy :P

Ujemne to można różnie tłumaczyć, np. jak w grafie waga oznacza zysk/stratę, ale w przypadku odległości nie stosuje się żadnych ujemnych i dlatego algorytm dijkstry będzie w tym wypadku działał dobrze.

Lepszy jest graf skierowany, co najwyżej większość krawędzi będzie w obie strony, ale czasem może się przecież zdarzyć krawędź w jedną.

0
Spykaj napisał(a)

Lepszy jest graf skierowany, co najwyżej większość krawędzi będzie w obie strony, ale czasem może się przecież zdarzyć krawędź w jedną.

Tylko, że traktując węzeł jako przystanek, to wiele linii autobusowych przez jedną krawędź będzie przejeżdżało, wtedy będę musiał dla każdego autobusu robić inny węzeł?, a tak będzie jeden na tej samej trasie. Nie wiem czy dobrze myślę. Nie mogę popełnić błędu w założeniach bo darmo cała robota będzie :) A miasto nie jest za bardzo rozwinięte komunikacyjnie, 65 tys mieszkańców, parę linii autobusowych. No a co jeśli konieczna będzie przesiadka i np. podjechanie jednego przystanku wstecz, chyba graf skierowany nie będzie najlepszy?

0

@Spykaj
A* z dobrze dobraną heurystyką (tutaj takową będzie odległość w linii prostej) ZAWSZE zwraca poprawny wynik, więc kolegi w błąd nie wprowadzaj ;)

Ponadto implementacyjnie nie jest wiele trudniejszy. Ze 3-4 linijki kodu więcej będą. ;)

0

No i już wiem, że będzie do 130 przystanków i do 20 linii autobusowych. Do tego dodać czas zatrzymywania się poszczególnych autobusów na poszczególnych przystankach i mamy trochę tych danych...

0

No to rzeczywiście mało tego ... Jeśli będzie to dla Ciebie łatwiejsze, możesz zostać śmiało przy Dijkstrze.

0

Moja propozycja to oczywiście Dijkstra. Z tym, że jest spora różnica pomiędzy minimalizacją drogi a czasu dojazdu. Jak trzeba zminimalizować drogę to nie ma żadnego problemu, bo jest standardowa Dijkstra (ale nie wiem kto by sie ucieszył, ze znalazl najktrotszy dojazd tracąc na niego kilkanaście godzin w oczekiwaniu na przesiadki :D). Przy minimalizacji czasu trzeba to robic troche inaczej, budowac wierzchołki w ktorych bedzie zapisany czas przyjazdu i krawedzie z niego wychodzace to kursy ktore maja czas odjazdu pozniejszy od tego w wierzchołku. Można to robić dynamicznie, oszczedzając troche na pamięci. Nie wiem czy pisać coś wiecej, bo może piszę nie na temat. Jak coś to moge jeszcze wytłumaczyć ;)

0

Zordonix, pisz jak najwięcej :) Jeśli mowa o minimalizacji. Chce po prostu wyświetlić wiele opcji użytkownikowi, z przesiadkami lub nie, niech sobie on sam wybierze, która opcje wybrać. Chodzi dokładnie o coś takiego jak na http://rozklad.pkp.pl. Zaznaczamy skąd i dokąd i pojawia nam sie lista tras, z przesiadkami i bez, Którą pasażer pojedzie, zależy już od niego. Przy każdej opcji będzie informacja o ilości przesiadek i czasie przejazdu. Trzeba uwzględnić będzie czas oczekiwania na autobus. Problem w tym, ze dalej nie wiem, czy to będzie graf nieskierowany czy zrobić to na skierowanym, czy autobusy będą wracały dokładnie tą sama drogą, czy nie, co jeśli tak, jaką opcję wybrać, a co jeśli nie. Jak sie do tego w ogóle zabrać :)

Wracając jeszcze to tych tras, to nie wiem, czy wyświetlać wszystkie? Chyba dużo kombinacji może być jeśli wziąć pod uwagę, że mogą być przesiadki? Może doprecyzuje użytkownik, ze chce jechać maks 1h i inne ścieżki wywalę?

Inny system http://83.242.81.164/, pkp może mieć akurat na stale wpisane, ale tu już nie.

0

IMO skierowany graf. Większość busów jeździ tą samą trasą w obie strony, ale w mieście gdzie studiuję jest to w miarę niemożliwe, bo są dwie równoległe ulice, ale jednokierunkowe, więc w obie strony różnymi ulicami jeździ, a wiec różne przystanki zalicza. Kto wie, może i w twojej okolicy takie cuś się trafi, a wtedy będziesz już na to przygotowany w miarę.

Ile wyświetlać? Kilka najkrótszych czasowo i odległościowo. Za dużo nie ma sensu, bo sie okaże, że z katowic do warszawy przez gdańsk się da dojechać, tylko po co?

0

Odnośnie pytania graf skierowany czy nieskierowany, to zależy czym są krawędzie, czy reprezentują dany odcinek na mapie czy jeden szczególny kurs autobusu. Wiedząc to odpowiedź sama się nasuwa. A swoją drogą graf nieskierowany to nic innego jak skierowany tylko, ze są krawędzie w obie strony zamiast jednej... przynajmniej tak najwygodniej sie to implementuje. Przy takiej implementacji kwestia skierowany/nieskierowany nie robi żadnej różnicy.

0

Nie chcę zniechęcać bo pomysł fajny i użyteczny, jednak jest mały problem. Komunikacja miejska znacząco różni się od komunikacji PKP. Po pierwsze dlatego, że dworce są w dużej odległości od siebie i przejście na pieszo między 2 dworcami jest niedorzeczne. Z przystankami sprawa wygląda nieco inaczej. Trzeba też założyć jakiś zapas czasu na przesiadkę, który może zależeć właśnie od czasu ewentualnego "dojścia" np. na rondzie to już kilka minut i autobus może zwiać. Niemniej, gdyby w moim mieście istaniła taka aplikacja to chętnie bym z niej skorzystał. Co do grafu, to IMO musi być graf skierowany. Dlatego, że jak już ktoś wcześniej zauważył, powinieneś operować na czasie, a nie na odległości. Bardzo wątpię, żeby czas przejazdu autobusu nie zależał od godziny (szczyt lub pustka na trasie) oraz od kierunku (rano są korki do centrum, wieczorem na odwrót). W związku z tym powinieneś operować na takim samym zestawie danych jak w rozkładzie, chociaż najlepiej przekształcić godziny na różnice czasu. Ja by nie upraszczał, tylko zrobił dla każdego przystanku początkowego i dla każdego autobusu godzinę odjazdu, a następnie dla każdego z autobusów jego własny czas przejazdu przez kolejne przystanki. Tak więc miałbyś graf z liczą węzłów odpowiadającą liczbie przystanków. Między każdymi dwoma węzłami musiałbyś mieć tyle połączeń skierowanych, ile danego dnia łącznie przejedzie autobusów między danymi przystankami. Przypomnę - wynika to z tego, że choć odległości między przystankami są stałe, to czasy przejazdu mogą zmieniać się w zależności od godziny, a Ciebie interesuje czas a nie godzina.

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