Ifi6057w4

4. Nädal

Heuristiline otsing. AIMA chapter 3.5, TI 17 (eeldab ka 16 lugemist).

Hinnangufunktsioon, heuristiline funktsioon. Ahne otsing.

A*; selle optimaalsus ja täielikkus. Introduction to A* (mängu-AI / Python)

Loenguslaidid: PDF

Harjutustund

Ülesanne - 4st ruumist ("A", "B", "C", "D") koosnev tolmuimejamaailm. Leiame lühima lahenduse algolekust seisu, kus kõik ruumid on puhtad. Lõppolekus pole oluline, kus on tolmuimeja. Kasutame search.Problem klassi, et maailma kirjeldada.

import search

class VacWorld(search.Problem):
  def actions(self, state):
      act = []
      # ...
      return act
  def result(self, state, action):
      newstate = state.copy()
      # action on yks nendest: "Left", "Right", "Suck", "NoOp"
      return newstate
  def goal_test(self, state):
      # kui on k6ik puhas, return True
      # muidu return False

Oleku esitus

 algolek = {
   "A" : "Dirty",
   "B": "Clean",
   "C": "Clean",
   "D": "Dirty",
   "loc": "C"
 }