W wybranej aplikacji wpisujemy, skąd jedziemy (dworzec PKP) i dokąd chcemy dojechać (Słowackiego 11). Aplikacja poszuka możliwych rozwiązań tego problemu, czyli sposobów dotarcia z punktu A do B. Jako możliwe rozwiązania zobaczymy numer autobusu, w który musimy wsiąść, by dojechać do celu. Dodatkowo możemy widzieć czas odjazdu i podróży, a może nawet koszty podróży, czyli ceny biletów. Pozostaje wybrać rozwiązanie, z którego chcemy skorzystać.

Oczywiście z miejsca A do miejsca B może prowadzić tylko jedna linia autobusowa, ale można też dojechać tam z przesiadkami. Czy droga z przesiadkami oznacza, że jedzie się dłużej? Niekoniecznie. Czasem podróż z przesiadką może odbyć się szybciej, ale drożej, bo np. trzeba dwa razy skasować bilet. Aplikacja może (choć nie musi) uwzględniać korki, roboty drogowe, zmiany w ruchu i wyliczać nam rzeczywisty czas dojazdu na miejsce.

Aplikacje do planowania trasy rozwiązują problemy związane z wyszukiwaniem i planowaniem. Stosowane w nich algorytmy sprawdzają się nie tylko w nawigacji, ale też w grach. Nie będziemy o nich opowiadać w tym kursie. Zamiast tego przedstawimy pierwszy etap rozwiązywania problemów, czyli:

• określenie celu działania, czyli sytuacji, w której uznamy, że problem jest rozwiązany;
• znalezienie możliwych rozwiązań i wybranie najlepszego.

Zagadka I: lis, zając i marchew

Być może znasz starą zagadkę z dzieciństwa o pasterzu, lisie i zającu. Na lewym brzegu rzeki znajdują się:

• pasterz 
• lis 
• zając 
• marchewka 

Pasterz ma łódź, którą tylko on może sterować. Twoim zadaniem jest przeprawienie pasterza, zwierząt i marchwi na prawy brzeg rzeki, ale musisz przestrzegać zasad:

• obok pasterza w łódce jest miejsce na tylko jeden ładunek: zająca, lisa albo marchew
• zając nie może być sam na brzegu z lisem, bo lis go zje
• zając nie może być sam na brzegu z marchewką, bo ją zje
• tylko pasterz może powstrzymać zwierzęta od jedzenia
• pasterz, lis, zając i marchew mogą zmieniać brzeg dowolną ilość razy.

W jaki sposób pasterz może przewieźć bezpiecznie wszystkie ładunki na prawy brzeg?

Zapewne potrafisz znaleźć rozwiązanie zagadki i sztuczna inteligencja nie jest Ci do tego potrzebna. W tym rozdziale chcemy jednak pokazać, jak problemy rozwiązuje właśnie sztuczna inteligencja.

Stany elementów

Zaczniemy od rozpisania stanów każdego z ruchomych elementów tej zagadki: pasterza, lisa, zająca i marchewki. Łódź służy tylko do transportu i zawsze jest tam, gdzie pasterz, dlatego nie będziemy uwzględniać jej stanu.

Stan elementu to jego położenie względem rzeki. W naszej zagadce element może być na jej prawym (P) lub lewym (L) brzegu, czyli mieć dwa stany. Możliwości ułożenia tych stanów nazywamy kombinacjami. Wszystkich kombinacji jest 16.

Teraz nie będziemy analizować kolejności przepraw na drugi brzeg. Zajmiemy się wszystkimi kombinacjami, czyli rozpiszemy, na których brzegach mogą być wszystkie elementy.

Żeby było łatwiej zrozumieć nasz zapis, wytłumaczymy go na kilku przykładach:

Pozycja 1 tabeli to start naszej gry. Wszystkie elementy są po lewej stronie brzegu, dlatego w skrócie zapisaliśmy kombinację LLLL (jedna litera to stan kolejnego elementu z tabeli). Kombinacja nr 2 LLLP oznacza, że pasterz, lis i zając są po stronie lewej, a marchew po prawej stronie rzeki, itd.

Kombinacja, do której chcemy dojść, to wszystkie elementy po prawej stronie rzeki, czyli PPPP (pozycja 16 w tabeli). W poniższej tabeli znajdują się wszystkie możliwe stany elementów. Jeśli chcesz, możesz sobie rozpisać je samodzielnie i sprawdzić.

Teraz musimy na chwilę wrócić do zasad naszej zagadki. Pamiętajmy, że:

• zając nie może być sam na brzegu z lisem, bo lis go zje
• zając nie może być sam na brzegu z marchewką, bo ją zje

Oznacza to, że takie kombinacje kończą naszą grę. Musimy więc wykreślić je z tabelki. Sytuacje, w których te elementy są na innym brzegu niż pasterz to numery: 5, 6, 7, 8, 9, 15. Po usunięciu ich z tabeli zostaje nam 10 możliwych kombinacji gry, które doprowadzą nas do rozwiązania:

Przejścia między kombinacjami

Kolejna rzecz, którą musimy zrobić, to ustalić, które kombinacje można ze sobą połączyć. Dzięki temu dojdziemy do rozwiązania zagadki. Żeby sobie uprościć to zadanie, po lewej stronie rzeki umieścimy te, w których pasterz jest także po lewej stronie, a po prawej te, w których jest po prawej. Zrobimy tak dlatego, że to pasterz przewozi ładunki, więc za każdym razem zmienia swój stan z L na P i odwrotnie. Dzięki temu możemy płynnie przechodzić z lewej do prawej strony obrazka i znów wracać do lewej. Wygląda to tak:

Uwaga! Numery przy kombinacjach nie są ich kolejnością. Pozwalają one jedynie odwołać się do konkretnego stanu przy tłumaczeniu tego ćwiczenia.

A teraz rozwiążemy zagadkę:

kombinacja nr 1 (start)

Wszystkie elementy są po lewej stronie. Wiemy, że pasterz może zabrać tylko jeden ładunek. Zatem musimy po prawej stronie znaleźć stan, w którym pasterz jest z innym elementem w stanie P, a reszta elementów zostaje po lewej stronie rzeki (L).

kombinacja nr 2

To stan, którego szukaliśmy: pasterz z zającem są po prawej stronie rzeki, lis i marchew zostali po stronie lewej. Teraz pasterz powinien zostawić zająca i wrócić na lewy brzeg.

kombinacja nr 5

Pasterz wrócił na lewy brzeg. Jest na nim wraz z lisem i marchewką, a zając jest po prawej. Co dalej? Pasterz może popłynąć na prawy brzeg z marchewką lub lisem. Musimy wybrać jedną z tych opcji.

kombinacja nr 4

Pasterz zabrał ze sobą lisa, więc po lewej stronie rzeki mamy marchew, a po prawej pasterza, zająca i lisa. Pamiętaj, że pasterz nie może wrócić sam. Zostawiłby lisa i zająca samych, co skończyłoby się zjedzeniem tego drugiego. Nawet nie mamy takiego stanu do wyboru, bo wykluczyliśmy go jako oznaczający „przegraną”. Pasterz musi zabrać któryś element. Ponieważ dopiero co przypłynął z lisem, zabieranie go z powrotem oznaczałoby powrót do poprzedniego stanu gry.

kombinacja nr 7

Pasterz zabrał zająca. Jest z nim i marchewką po lewej stronie. Po prawej pozostał lis. Nie ma sensu zabierać na prawą stronę zająca, bo dopiero co tam był. Zabierzmy więc marchew.

kombinacja nr 8

Pasterz, marchew i lis są po prawej stronie, po lewej został zając. Co to oznacza? Pasterz może bezpiecznie wrócić sam na lewy brzeg.

kombinacja nr 9

Pasterz z zającem są po stronie lewej, a lis i marchew po prawej. Pozostał nam ostatni ruch, który prowadzi do rozwiązania zagadki.

kombinacja 10 (meta)

Jedyny ruch, jaki nam pozostał, to przepłynięcie pasterza i zająca na prawy brzeg. Wszyscy są w komplecie!

Wszystkie nasze ruchy potrzebne do rozwiązania zagadki widać na poniższym obrazku:

Podczas naszej gry przeszliśmy przez osiem kombinacji siedmioma ruchami. Było to jedno z dwóch rozwiązań.