Ifi6057w3

3. Nädal

Ülesannete lahendamine otsinguga; AIMA chapter 3.3-3.4, TI 14-15.

Lühendatud slaidid PDF

Videoloeng: BFS ja DFS

Harjutustund

Lahenda 4x4 sudoku kasutades search.Problem klassi ja search mooduli otsingualgoritme.

Olek tuleb kodeerida 16-kohaliseks tupleks järgmiselt:

 (2, 1, 0, 0,
  0, 3, 2, 0,
  0, 0, 0, 4,
  1, 0, 0, 0)

Ja üks tegevus (action) tuleb edasi anda tuplena (number, x-koordinaat, y-koordinaat), mis tähendab et number kirjutatakse antud koordinaatidega ruutu. Koordinaadid on 0-st 3-ni.

 (2, 3, 3)

Tähendab, et number "2" kirjutatakse alumisse ritta viimasesse veergu.

Veel algolekuid testimiseks:

 (1, 0, 3, 4, 0, 3, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1)
 (4, 2, 0, 0, 1, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 3)
 (0, 0, 0, 3, 4, 0, 0, 0, 0, 1, 3, 0, 3, 0, 2, 0)

Ülesande klassi toorik

 class MiniSudoku(search.Problem):
   def actions(self, state):
       act = []
       # ...
       return act
   def result(self, state, action):
       newstate = list(state)
       # ...
       return tuple(newstate)
   def goal_test(self, state):
       # blah asemel on lõppseisu tingimus
       if blah: return True
       return False