Warning
This page is located in archive.

01 Úvod, Prohledávání

Kvíz I - bonusový

Prohledávání I

  • vysvětlení
  • budeme diskutovat, jak hledat, když nevím jak je cíl daleko
  • co znamená, že algoritmus prohledávání je úplný, optimální.

Zadání úlohy: hledání cesty v bludišti

V prostředí Prohledávání stavového prostoru naprogramujte nalezení nejlevnější cesty. Nezapomeňte, že cena přechodu mezi pozicemi nemusí být nutně všude stejná.

Seznámení s prostředím KUIMaze

>>> from kuimaze2 import SearchProblem, State
>>> from kuimaze2.map_image import map_from_image
>>> map_path = 'maps/easy_intro/easy_intro_1.png'
>>> env = SearchProblem(map_from_image(map_path), graphics=True)

  • Vykreslete si prostředí metodou render():

>>> env.render()
Měli byste vidět obrázek podobný následujícímu: Nechte okno s obrázkem otevřené, nezavírejte ho!

  • Zkuste použít různé metody, které prostředí nabízí:

>>> start = env.get_start()
>>> start
State(r=0, c=1)
>>> env.get_goals()   # Notice the different return type, this returns a Set
{State(r=2, c=4)}
>>> actions = env.get_actions(start)
>>> actions
[<Action.UP: 0>, <Action.RIGHT: 1>, <Action.DOWN: 2>, <Action.LEFT: 3>]
>>> new_state, trans_cost = env.get_transition_result(start, actions[1])
>>> new_state
State(r=0, c=2)

  • Zkuste zavolat env.render() znovu. Změnilo se zobrazení nějak?
  • Zkuste přidat do volání metody render() další parametry:

>>> texts = {State(0,0): "S", State(0,1): "1"}
>>> env.render(texts = texts, current_state=State(0,0), next_states=[State(1,0)])

  • Prozkoumejte example_search.py a zkuste pochopit, co se tam děje.
  • Zkuste manuálně zkonstruovat cestu ze startu do cíle a vrátit ji z metody Agent.find_path().
  • Zkuste si takového agenta odevzdat do BRUTE do úlohy 01-easy_search.

Ačkoli jste mnozí již netrpěliví se rovnou vrhnout na implementaci algoritmu A*, zkuste napřed jednodušší algoritmy (BFS, UCS) a jednoduchá bludiště. Je to menší problém, bude se vám snáz krokovat a debugovat, ověříte si správné zacházení s prostředím.

Rozmyslete si trochu nad papírem datové struktury, které budete potřebovat. Zkuste implementovat různé strategie/algoritmy. Pokud je implementujete dostatečně obecným způsobem, většina vašeho kódu půjde použít i pro algoritmus A* (což je první povinná úloha).

Zkuste svůj algoritmus v modulu agent.py odevzdat do BRUTE a prozkoumejte, jakou zpětnou vazbu vám hodnoticí skript poskytl.

1. povinná úloha: Hledání cesty v bludišty algoritmem A*

V první povinné úloze je vaším úkolem naimplementovat algoritmus A*, který vám bude představen nejpozději na druhé přednášce. Pokud jste ale “Prohledávací rozcvičku” zvládli rychle a nedělá vám potíže programovat v Pythonu, můžete začít pracovat na první povinné úloze.

Nezapomeňte, že cena za přechod z jednoho stavu do druhého nemusí být stále stejná.

různé

  • visualizace různých prohledávacích algoritmů demonstrována na problému n-1 puzzle
courses/b3b33kui/cviceni/program_po_tydnech/tyden_01.txt · Last modified: 2024/02/21 14:50 by xposik