01 Úvod, Prohledávání I

• počítačové laboratoře na K133 a bezpečnost práce
• https://www.cesnet.cz/sluzby/owncloud/
• (N-1)-puzzle: quiz, programování rozhodnutí o řešitelnosti puzzle
• prohledávání: quiz
• zadání první samostatné úlohy

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

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

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