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

Odpowiedz Nowy wątek
2008-05-25 15:54
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 :)

Pozostało 580 znaków

2008-05-25 16:37
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ą ?).

Pozostało 580 znaków

2008-05-25 16:42
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.

Pozostało 580 znaków

2008-05-26 09:59
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ą.

Pozostało 580 znaków

2008-05-26 11:03
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?

Pozostało 580 znaków

2008-05-26 13:04
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ą. ;)

Pozostało 580 znaków

2008-05-26 14:00
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...

Pozostało 580 znaków

2008-05-26 17:58
0

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

Pozostało 580 znaków

2008-05-27 11:05
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ć ;)

Pozostało 580 znaków

2008-05-27 11:18
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.

Pozostało 580 znaków

2008-05-27 11:35
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?

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