Ifi6057w2

2. Nädal

Hulgateooria kordamine.

Algoritmide ja ülesannete keerukus: PDF.

Probleemi formuleerimine ja olekuruum. Lühendatud slaidid PDF; AIMA chapter 3.1-3.2, TI 4-5.

Videoloeng: olekuruum

Harjutustund

Eeldus: olemas on aima-python ja aima-data. Lahendame 8-Puzzle:

 1 2 3
 7   5
 8 4 6

• search.py sees on otsingu funktsioonid ja otsinguülesande formulatsioon Problem class
• oma töö jaoks uus fail ht2.py

 import search
 # ... siin tuleb problem defineerida
 asi = search.breadth_first_tree_search(problem)

• defineeri algolek ja lõppolek

 inistate = (1,2,3,7,0,5,8,4,6)
 goal = (1,2,3,4,5,6,7,8,0)

• tee oma klass EightPuzzle mis põhineb Problem klassil
• defineeri actions meetod

   def actions(self, state):
       space = state.index(0)
       row = space // 3
       col = space % 3
       actions = []
       if row == 0:
           actions.append(state[space + 3])
       elif row == 1:
           actions.append(state[space + 3])
           actions.append(state[space - 3])
       elif row == 2:
           actions.append(state[space - 3])
       if col == 0:
           actions.append(state[space + 1])
       elif col == 1:
           actions.append(state[space + 1])
           actions.append(state[space - 1])
       elif col == 2:
           actions.append(state[space - 1])
       return actions

• defineeri result meetod

   def result(self, state, action):
       newstate = list(state)
       klotsi_idx = newstate.index(action)
       space = newstate.index(0)
       newstate[space] = action
       newstate[klotsi_idx] = 0
       return tuple(newstate)

• kontrolli, et goal_test ja path_cost teevad õiget asjad
• käivita mingi otsingualgoritm, vaata mis vastus tuleb

 problem = EightPuzzle(inistate, goal)
 goalnode = search.breadth_first_search(problem)
 print(goalnode.solution())
 print(goalnode.path())