• Ślepe (Uninformed) - wiedzą tylko o rozwiązaniu (gdy trafi to wie, że trafił)
  • Wszerz (BFS)
  • Strategia jednolitego kosztu (Uniform cost search) = BFS jeśli identyczne wagi
  • W głąb (DFS)
  • Algorytm Dijkstry
  • Iteracyjne pogłębianie (Iterative deepening)
  • Dwukierunkowy (Bidirectional search)
• Heurystyczne (Informed) - dodatkowo specyficzna wiedza o konkretnym problemie
  • Zachłanny (Greedy Best-First search)
  • A∗
  • RBFS (Recursive Best-First search)
  • SMA∗ (Simplified Memory-bounded A∗)

Dla chcących wiedzieć więcej: Chapter 3: Searching for Solutions

Mapa obszaru i graf przeszukiwania są niezależne!

• Algorytmy poszukiwania najkrótszej ścieżki bazują na grafie, który jest tylko zbiorem wierzchołków i krawędzi (z ew. wagami) – samodzielnie musimy to przetłumaczyć na rzeczywisty ruch (pokonanie drzwi, przejście na sąsiedni kafelek, cokolwiek innego)
• Graf zbudowany jak mapa jest łatwiejszy w obsłudze, ale …
  … bardziej złożony dla algorytmów przeszukiwania.
  Porównaj różne grafy (dla tej samej mapy) przedstawione poniżej:
  
  
  
• Ważna decyzja projektowa specyficzna dla konkretnego problemu!

Dla chcących wiedzieć więcej: Zestawienie podstawowych reprezentacji wykorzystywanych przy tworzeniu map

Narzędzie webowe: https://krzysztof.kutt.pl/didactics/psi/pathfinder/
(bazuje na https://github.com/qiao/PathFinding.js)

1. Na początek warto pobawić się różnymi algorytmami i sprawdzić jak działają.
   • Można przesuwać początek (zielony) i koniec (czerwony) ścieżki
   • Można rysować krawędzie
2. Później chcemy przetestować różne heurystyki dla A*. W pole My heuristic można wpisać np.:
   • dx
   • dy
   • dx + dy
   • Math.sqrt(dx*dx + dy*dy)
   • -dx - dy
   • 10 * Math.random()
3. Zadanie A:
   • Przygotuj pierwszy test klikając najpierw Clear Walls (wyczyści wszystkie ściany), a później Build 1st test:
     
   • Jaką heurystykę należy wpisać dla A*, aby najkrótszą ścieżką była ta “nad” ścianą?
   • Dlaczego?
4. Zadanie B:
   • Przygotuj drugi test klikając Clear Walls i Build 2nd test:
     
   • Jaką heurystykę przyjąć dla A*, aby znaleźć ścieżkę poniżej 300 operacji (operations w lewym dolnym rogu po zakończeniu wyszukiwania)
   • Warto porównać z włączoną opcją Bi-directional (ale zejść poniżej 300 operacji należy bez tej opcji!)

Dla chcących wiedzieć więcej: Artykuł opisujący heurystyki dla grid map

CodinGame to platforma do nauki/doskonalenia umiejętności programistycznych wykorzystująca gry. Co ważne, większość gry została już przygotowana, a naszym zadaniem jest tylko dopisanie odpowiedniej logiki, co idealnie wpasowuje się w nasze zajęcia!

• Platforma umożliwia programowanie w różnych językach programowania (C/C++/C#, Java, Python 3, Scala, …)
• Każde zadanie na platformie posiada szczegółowy opis problemu oraz opis reprezentacji (jakie konkretnie wartości są używane, zakresy wartości, …)
• Tworzony przez nas kod komunikuje się z silnikiem gry poprzez standardowe wejście/wyjście = w każdej iteracji pętli wczytuje stan planszy / mapę / cokolwiek ze standardowego wyjścia, przetwarza to i generuje akcję, którą wypisuje na standardowe wyjście
• W każdym języku programowania jest już przygotowany szablon rozwiązania obsługujący wejście/wyjście - wartości z wejścia są zapisywane do przykładowych zmiennych, a na końcu printowane są przykładowe wartości wyjściowe
• Zadania można programować bez zakładania konta (ale: konto będzie potrzebne do kliknięcia “submit” i zdobycia maksymalnej liczby punktów)

Zadanie jest dostępne pod adresem: Death First Search - Episode 1

• Twój wirus dostał się do sieci Bobnet (wszelkie skojarzenia z siecią Skynet nie są przypadkowe)
• Znajdujesz się w jednej z podsieci. Znajduje się tutaj również agent Bobnet, który wykrył Twoją obecność i próbuje przemieścić się do bramy, aby przekazać informację o Twoim wirusie do pozostałych części sieci.
• Twoje zadanie: nie dopuścić do tego poprzez uszkadzanie kolejnych połączeń w sieci (aby finalnie nie było możliwości dotarcia przez agenta Bobnet do żadnej z bram)

1. Na początek zapoznaj się ze szczegółowym opisem zadania dostępnym w IDE (po kliknięciu Solve na stronie problemu albo po przejściu bezpośrednio pod link)
2. [3 EXP] Zapoznaj się z interfejsem i przygotuj kod, który rozwiązuje pierwsze dwa test cases (01. Simple test i 02. Several paths; aby sprawdzić dany test case należy kliknąć odpowiedni przycisk Play testcase)
3. [3 EXP] Przygotuj rozwiązanie dla test case 03. Star
4. [3 EXP] Przygotuj kod, który poprawnie rozwiązuje wszystkie test cases + rozwiązuje dodatkowe test cases wykonywane po kliknięciu Submit; możesz wykorzystać dowolny algorytm (ale wystarczy zwykły BFS)
5. Jeżeli to było zbyt proste, spróbuj zmierzyć się z Death First Search - Episode 2 (już bez punktów, dla własnej satysfakcji)