CourseWare Wiki
Switch Term
Summer 2023 / 2024
Summer 2022 / 2023
Summer 2021 / 2022
Summer 2020 / 2021
Summer 2019 / 2020
Summer 2018 / 2019
Summer 2017 / 2018
Older
Search
Log In
b232
courses
b3b33kui
cviceni
program_po_tydnech
tyden_01
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Both sides previous revision
Previous revision
2024/02/21 14:50 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 14:43 xposik [programování hledání]
2024/02/21 14:42 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 11:11 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 11:11 xposik [Seznámení s prostředím KUIMaze]
2024/02/21 11:10 xposik [Seznámení s prostředím KUIMaze]
2024/02/21 11:01 xposik
2024/02/21 11:00 xposik [Seznámení s prostředím KUIMaze]
2024/02/20 17:39 xposik [Seznámení s prostředím KUIMaze]
2024/02/20 17:37 xposik [Seznámení s prostředím KUIMaze]
2023/04/28 14:01 external edit
Go
Previous revision
2024/02/21 14:50 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 14:43 xposik [programování hledání]
2024/02/21 14:42 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 11:11 xposik [Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
2024/02/21 11:11 xposik [Seznámení s prostředím KUIMaze]
2024/02/21 11:10 xposik [Seznámení s prostředím KUIMaze]
2024/02/21 11:01 xposik
2024/02/21 11:00 xposik [Seznámení s prostředím KUIMaze]
2024/02/20 17:39 xposik [Seznámení s prostředím KUIMaze]
2024/02/20 17:37 xposik [Seznámení s prostředím KUIMaze]
2023/04/28 14:01 external edit
Go
courses:b3b33kui:cviceni:program_po_tydnech:tyden_01 [2019/02/20 11:12]
courses:b3b33kui:cviceni:program_po_tydnech:tyden_01 [2024/02/21 14:50]
(current)
xposik
[Prohledávácí rozcvička - nepovinná úloha 01-easy_search]
Line 1:
Line 1:
+
====== 01 Úvod, Prohledávání ======
+
* [[https://cyber.felk.cvut.cz/study/computer-labs/|počítačové laboratoře]] na [[http://cyber.felk.cvut.cz|K133]] a bezpečnost práce
+
* https://www.cesnet.cz/sluzby/owncloud/
+
* https://gitlab.fel.cvut.cz
+
* **prohledávání**: vysvětlení
+
* zadání první samostatné úlohy
+
===== Kvíz I - bonusový =====
+
/* * startovní kvíz, na n-puzzle
+
* bodovaný, bonusových 0.5bodu
+
* řešení odevzdat do BRUTE do úlohy **lab01quiz**, do půlnoci dne, kdy běží dané cvičení
+
* formát: textový soubor, fotka řešení na papíře, pdf - co Vám nejlépe vyhovuje a dokážeme to přečíst
+
*/
+
+
/*==== Kvíz ====*/
+
> {{page>courses:b3b33kui:internal:quizzes#Plánování letových hladin}}
+
+
+
+
+
===== Prohledávání I =====
+
* vysvětlení /*, on-line výuka*/
+
* budeme diskutovat, jak hledat, když nevím jak je cíl daleko
+
* co znamená, že algoritmus prohledávání je //úplný, optimální//.
+
/* * prezentace {{ :courses:b3b33kui:cviceni:program_po_tydnech:searchi_example_cz.pdf |SearchI_example_cz.pdf}}*/
+
+
/* ==== Kvíz ==== */
+
> {{page>courses:b3b33kui:internal:quizzes#Zapomnětlivý cestovatel}}
+
+
+
===== Zadání úlohy: hledání cesty v bludišti =====
+
+
V prostředí [[courses:b3b33kui:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|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 =====
+
* [[courses:b3b33kui:semestralni_ulohy:kuimaze:00_install|Stáhněte a zprovozněte si prostředí KUIMaze]]
+
* Projděte si sekci [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start#jak_na_to|Jak na to]] v popisu úlohy [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|1. Prohledávání stavového prostoru]]
+
* Vytvořte si prostředí ''SearchProblem'', tj. instanci třídy ''kuimaze2.SearchProblem'', s mapou danou obrázkem v souboru ''maps/easy_intro/easy_intro_1.png'':
+
<code python>
+
>>> 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)</code>
+
* Vykreslete si prostředí metodou ''render()'':
+
<code>
+
>>> env.render()
+
</code>
+
Měli byste vidět obrázek podobný následujícímu:
+
{{ :courses:b3b33kui:cviceni:program_po_tydnech:easy_intro_1.png?200 |}}
+
**Nechte okno s obrázkem otevřené, nezavírejte ho!**
+
* Zkuste použít různé metody, které prostředí nabízí:
+
<code>
+
>>> 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)
+
</code>
+
* Zkuste zavolat ''env.render()'' znovu. Změnilo se zobrazení nějak?
+
* Zkuste přidat do volání metody ''render()'' další parametry:
+
<code python>
+
>>> texts = {State(0,0): "S", State(0,1): "1"}
+
>>> env.render(texts = texts, current_state=State(0,0), next_states=[State(1,0)])
+
</code>
+
* 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 [[https://cw.felk.cvut.cz/brute/|BRUTE]] do úlohy ''01-easy_search''.
+
+
===== Prohledávácí rozcvička - nepovinná úloha 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 [[https://cw.felk.cvut.cz/brute/|BRUTE]] a prozkoumejte, jakou zpětnou vazbu vám hodnoticí skript poskytl.
+
+
===== 1. povinná úloha: Hledání cesty v bludišty algoritmem A* =====
+
V [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|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é =====
+
* [[http://tristanpenman.com/demos/n-puzzle/|visualizace]] různých prohledávacích algoritmů demonstrována na problému n-1 puzzle