GPS po Gdańsku
Jak nawigacja w telefonie znajduje najlepszą drogę? Dla komputera miasto to graf: skrzyżowania i miejsca to punkty, a ulice to linie z odległością. Zobacz krok po kroku, jak algorytm Dijkstry szuka trasy z Oliwy na Westerplatte.
Kliknij miejsce, żeby ustawić start, potem drugie, żeby ustawić cel. Kliknij ulicę, żeby dodać albo usunąć korek. Mapa jest uproszczona, a odległości przybliżone.
Nawigacja
Ty jesteś GPS
Wyznacz trasę sam: klikaj kolejne sąsiednie miejsca od startu do celu. Potem porównamy ją z algorytmem.
Jak działa algorytm Dijkstry?
Algorytm rozchodzi się od startu jak fala. Zawsze bierze najbliższe jeszcze niesprawdzone miejsce i sprawdza, czy przez nie da się dojść do sąsiadów szybciej niż dotąd.
1. Start ma odległość 0, reszta: ∞ (nieznana). 2. Weź niesprawdzone miejsce o najmniejszej odległości. 3. Dla każdego sąsiada policz: odległość tutaj + długość ulicy. Jeśli to mniej niż dotąd zapisane, zapisz nową odległość i skąd przyszedłeś. 4. Oznacz miejsce jako sprawdzone. 5. Powtarzaj, aż sprawdzisz cel. 6. Trasę odczytaj od celu wstecz.
Niebieska obwódka: miejsce, do którego znamy już jakąś drogę. Pomarańczowe: sprawdzane teraz. Ciemne: sprawdzone, czyli najkrótsza droga do nich jest już pewna.
Sprawdź się
Punkty 0 · Seria 0 · Rekord 0Jak działa nawigacja GPS?
Dwa zadania nawigacji
Nawigacja robi dwie różne rzeczy. Najpierw ustala, gdzie jesteś: to zadanie systemu satelitarnego GPS. Potem wyznacza, którędy jechać: to zadanie algorytmu, który przeszukuje mapę zapisaną jako graf. Ta aplikacja pokazuje drugą część.
Skąd telefon wie, gdzie jest?
Nad Ziemią krąży ok. 30 satelitów GPS. Każdy nadaje sygnał z dokładnym czasem wysłania. Telefon mierzy, jak długo sygnał leciał, i oblicza odległość od satelity. Mając odległości od co najmniej czterech satelitów, wyznacza swoje położenie z dokładnością do kilku metrów. Telefony korzystają też z europejskiego systemu Galileo i innych podobnych.
Mapa jako graf
Dla komputera miasto to graf: wierzchołki to skrzyżowania i miejsca, a krawędzie to ulice. Każda krawędź ma wagę: długość w kilometrach albo czas przejazdu. Szukanie trasy to szukanie w grafie drogi o najmniejszej sumie wag.
Algorytm Dijkstry
W 1956 roku holenderski informatyk Edsger Dijkstra wymyślił sposób na znalezienie najkrótszej drogi w grafie. Jak sam wspominał, ułożył go w ok. 20 minut przy kawie w Amsterdamie, bez kartki i ołówka. Algorytm sprawdza miejsca w kolejności od najbliższego, dzięki czemu na pewno znajduje najlepszą trasę.
Najkrótsza czy najszybsza?
Najkrótsza trasa nie zawsze jest najszybsza. Arteria może być dłuższa, ale pozwala jechać 50 km/h zamiast 30 km/h. Wystarczy zamienić wagi krawędzi z kilometrów na minuty, a ten sam algorytm znajdzie inną drogę. Tak samo działają korki: nawigacja dostaje na żywo dane o prędkości ruchu i zwiększa wagi zakorkowanych ulic.
Dlaczego nawigacja nie sprawdza całego kraju?
Prawdziwa mapa ma miliony skrzyżowań. Dlatego nawigacje używają ulepszeń Dijkstry, np. algorytmu A* (A-gwiazdka), który najpierw sprawdza miejsca leżące w kierunku celu, oraz wcześniej przygotowanych „skrótów” po autostradach.
Najczęstsze pytania o GPS i wyznaczanie tras
Jak działa GPS?
Satelity GPS wysyłają sygnały z dokładnym czasem nadania. Odbiornik w telefonie mierzy czas dotarcia sygnałów od kilku satelitów, oblicza odległości i na ich podstawie wyznacza swoje położenie na Ziemi.
Ilu satelitów potrzeba, żeby ustalić położenie?
Co najmniej czterech. Trzy wystarczyłyby do wyznaczenia punktu w przestrzeni, ale czwarty jest potrzebny, bo zegar w telefonie nie jest tak dokładny jak zegary atomowe w satelitach.
Co to jest algorytm Dijkstry?
To algorytm znajdowania najkrótszej drogi w grafie z nieujemnymi wagami krawędzi. Zaczyna od punktu startowego i za każdym razem sprawdza najbliższy jeszcze nieodwiedzony wierzchołek, poprawiając znane odległości do jego sąsiadów.
Co to jest graf w informatyce?
Graf to zbiór wierzchołków (punktów) połączonych krawędziami (liniami). Grafami opisuje się mapy dróg, sieci komputerowe, znajomości w mediach społecznościowych i wiele innych połączeń.
Dlaczego najkrótsza trasa nie zawsze jest najszybsza?
Bo różne drogi pozwalają jechać z różną prędkością, a na niektórych są korki. Trasa dłuższa w kilometrach może prowadzić szybszymi ulicami. Nawigacja liczy wtedy wagi w minutach zamiast w kilometrach.
Skąd nawigacja wie o korkach?
Z anonimowych danych o prędkości wielu telefonów i samochodów jadących danymi ulicami. Jeśli na odcinku wszyscy jadą wolno, nawigacja zwiększa jego wagę i może zaproponować objazd.
Czym różni się A* od algorytmu Dijkstry?
Dijkstra rozchodzi się od startu równo we wszystkich kierunkach. A* dodatkowo szacuje odległość do celu w linii prostej i najpierw sprawdza miejsca leżące w jego stronę, dzięki czemu zwykle odwiedza dużo mniej wierzchołków.