01 Úvod, Prohledávání I

N-1 puzzle

Quiz

Řešitelnost: programovací úloha

Bylo diskutováno na přednášce. Stáhněte si npuzzle.py. Vaším úkolem je naimplementovat funkci is_solvable(env), která rozhodne, zda je rozestavění destiček řešitelné čí nikoli. Funkci naimplementujte v modulu solvability_check.py a odevzdejte do BRUTE. Za správné řešení máte 2 body.

Základní kostra (solvability_check.py):

import npuzzle
 
def is_solvable(env):
   '''
   True or False?
   Tady naprogramujte svoje reseni
   '''
 
if __name__=="__main__":
   env = npuzzle.NPuzzle(3)
   env.reset()
   env.visualise()
   # just check
   print(is_solvable(env))

Základní komunikace s objektem NPuzzle je přes metodu env.read_tile(row, col), která vrátí hodnotu dlaždice, prázdná je None nebo vyvolá výjimku IndexError v případě pokud se pokusíte číst mimo hrací pole. Příklad použítí je dobře vidět v npuzzle.py

Prohledávání I

Budeme diskutovat jak hledat, když nevím jak je cíl daleko. Co znamená, že algoritmus prohledávání je úplný, optimální.

Quiz

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á.

courses/b3b33kui/cviceni/program_po_tydnech/tyden_01.txt · Last modified: 2019/02/26 08:43 by kostkja2