Główna zawartość
Kurs: Informatyka > Rozdział 1
Lekcja 1: Wprowadzenie do algorytmówSzukanie najkrótszej drogi
Google ClassroomCzasem zupełnie różnie wyglądające problemy okazują się być do siebie bardzo podobne gdy myślimy jak je rozwiązać. Co Pac-Man, brytyjska rodzina królewska i podróż do Orlando mają ze sobą wspólnego? Wszystkie związane są z problemem znalezienia najkrótszej drogi:
- Jak jest obecny Książę Wiliam powiązany z Królem Wiliamem III, który założył College of William and Mary w 1693?
- Którą drogą Duch jak najszybciej dogoni Pac-Mana?
- Jaka jest najszybsza droga pomiędzy Dallas w Teksasie a Orlando na Florydzie?
Aby odpowiedzieć na te pytania musimy dysponować pewnymi informacjami.
Na przykład drzewo genealogiczne brytyjskiej rodziny królewskiej zawiera powiązania pomiędzy najbliższymi krewnymi. Książę Wiliam jest synem Charlesa Philipa Arthura Windsora. Charles jest synem królowej Elżbiety II. Rozwiązanie polega na znalezieniu najkrótszej drogi łączącej Wiliama i Wiliama III na drzewie genealogicznym rodziny korzystając z bezpośrednich powiązań. Jak widzisz, dla drzewa poniżej będzie to całkiem sporo bezpośrednich powiązań.
W przypadku Pac-Mana będzie potrzebny plan labiryntu. Ta mapa pokazuje połączenia pomiędzy sąsiadującymi kwadratami, które są otwarte w labiryncie—lub brak połączeń kiedy pomiędzy jest ściana!—a problemem staje się znalezienie drogi wzdłuż czarnych kwadratów, które prowadzą ducha do Pac-Mana.
Aby znaleźć drogę z Dallas do Orlando możemy użyć mapy Stanów Zjednoczonych na której oznaczone są połączenia drogowe (drogi) pomiędzy sąsiednimi miastami. Nie ma drogi łączącej bezpośrednio Dallas z Orlando ale jest kilka dróg złożonych z odcinków pomiędzy sąsiednimi miastami, które doprowadzą nas do celu.
Badanie labiryntu
Labirynty są wciągające, więc zajmijmy się bliżej jedną z takich gier. W tej grze chodzi o to, żeby nasz bohater dotarł do celu w labiryncie.
Twoim zadaniem jest kliknąć na docelowe położenie w labiryncie, a a komputer ma obliczyć w jaki sposób tam dotrzeć. Położenie docelowe zaznaczone jest czerwonym kwadratem z napisem "GOAL", a nasz bohater rozpoczyna swą podróż przez labirynt z kwadratu startowego. Spróbuj zagrać z tę grę poniżej:
Widzisz jak żółte kółko zmierza do celu? Aby to wykonać program musi dokładnie określić zbiór kroków, które żółte kółko musi wykonać aby dotrzeć do wyznaczonego przez Ciebie miejsca i następnie stworzyć odpowiednią animację. Żółte kółko może dotrzeć do celu wieloma drogami i program musi określić która z nich jest najkrótsza.
Zanim wybierzemy algorytm, musimy ustalić zasady. Szare kwadraty oznaczają ściany labiryntu a ruch można wykonać tylko w obszarze zaznaczonym na biało. W jednym ruchu kółko może przemieścić się pomiędzy dwoma sąsiadującymi kwadratami. Tak jak wieża w szachach, nasz bohater nie może poruszać się po przekątnej.
Tu widać sposób w jaki algorytm działa w tym programie: przesuń się jeden kwadrat bliżej celu!—miejsce w które klika użytkownik—w każdym kroku. Ale co to znaczy "bliżej celu"? Ruch po prostej w kierunku celu może skończyć się na ścianie. Algorytm musi ustalić który z pobliskich kwadratów leży rzeczywiście "bliżej celu". Można to ustalić przypisując każdemu kwadratowi "koszt" będący minimalną liczbą kroków koniecznych aby dotrzeć z danego wierzchołka do celu. A oto algorytm który przypisuje każdemu kwadratowi jego wartość:
- Zacznij od celu. Jak daleko leży cel od celu? Zero kroków, oznacz cel liczbą 0.
- Znajdź wszystkie kwadraty znajdujące się dokładnie o jeden krok od celu. Oznacz je numerem 1. W tym labiryncie, jeśli cel znajduje się w wyjściu z labiryntu, jest tylko jeden kwadrat, który leży o jeden krok od niego.
- Znajdź teraz wszystkie kwadraty, które znajdują się dokładnie dwa kroki od celu. Te kwadraty znajdują się o jeden krok od kwadratów oznaczonych 1 i nie zostały jeszcze zaznaczone. Oznacz te kwadraty liczbą 2.
- Znajdź teraz wszystkie kwadraty, które znajdują się dokładnie trzy kroki od celu. Te kwadraty znajdują się o jeden krok od kwadratów oznaczonych 2 i nie zostały jeszcze zaznaczone. Oznacz te kwadraty liczbą 3.
- Oznaczaj kwadraty w labiryncie w kolejności rosnącej odległości od celu. Po oznaczeniu kwadratów z numerem
W końcu algorytm dotrze do miejsca gdzie znajduje się nasz bohater. Następnie program może znaleźć drogę do celu wybierając sekwencję kwadratów tak aby począwszy od startu liczby w kwadratach były coraz mniejsze. Jeśli wyobrazisz sobie liczbę w kwadracie jako jego wysokość będzie to jak zjazd z górki.
Zobacz jak działa algorytm przypisujący każdemu kwadratowi jego wartość. Kliknij na "Restart algorithm" aby obejrzeć od początku.
Przypuśćmy że użytkownik chce dotrzeć od startu do celu? Z algorytmu ustalającego koszt każdego kwadratu wiemy, że start znajduje się w odległości 13 kroków od celu. Na rysunku zaznaczono połączenia pomiędzy możliwymi położeniami żółtego kółka, położenie startowe, cel oraz najkrótszą odległość pomiędzy danym położeniem a celem:
Na południe od kwadratu startowego znajduje się kwadrat odległy o 12 kroków od celu. A zatem, pierwszy ruch to będzie ruch "na południe". Na południe od tego kwadratu znajduje się kwadrat odległy od celu o 11 kroków. A więc znowu na południe. I jeszcze raz na południe do 10. A następnie na wschód do 9. Jeszcze raz na wschód do 7, a potem pięć razy na północ do 2. W końcu jeden krok na zachód, do 1, i wreszcie ostatni krok na północ, prosto do celu.
Nie będziemy teraz dociekać jak wdrożyć algorytm przeszukiwania labiryntu, ale być może sprawi Ci frajdę zastanowić się jak można reprezentować labirynt i naszego bohatera żółte kółko w JavaScript i jak można byłoby zrealizować ten algorytm.
Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormen i Devina Balkcom oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Chcesz dołączyć do dyskusji?
chciałbym wiedzieć how to be szczęśliwy?(1 głos)