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