Iti0210lab4

Otsing aima-python paketiga

Sissejuhatus

Vaatame, kuidas ülesannet formaliseerida kui olekute ruumi, olekute üleminekuid ja soovitud oleku otsingut. Selleks kasutame aima-python paketti.

8-Puzzle on vähendatud, 3x3 versioon viieteistkümnemängust. Vaatame, kuidas seda ülesannet samm-sammult formaliseerida ja testime aima-python abil erinevate otsingustrateegiate efektiivsust.

Ettevalmistus

Hangi endale AIMA õpiku algoritme implementeeriv teek siit (klooni või võta kokkupakitult master branch). aima-python on pigem kogum faile, kui installitav pakett, seetõttu võib selle lihtsalt kusagile lahti pakkida. Kõige lihtsam on edaspidi oma programmifailid ka samasse kataloogi teha.

Java jaoks on olemas sarnane teek, aima-java. Selle kasutamist tuleb iseseisvalt uurida.

8-Puzzle kodeerimine

Kasutame search moodulit, mis toimib järgmiselt:

• Ülesanne kirjeldatakse search.Problem klassi kasutades
• Otsing pannakse käima ülesande instantsi peal (konkreetne algolek ja lõppolek)

Klassi skelett peaks olema umbes selline (detailsemaks selgituseks vt. [AIMA] õpik 3.1.1):

import search

class EightPuzzle(search.Problem):
    def actions(self, state):
        # returnib actionite listi
    
    def result(self, state, action):
        # returnib UUE oleku

    def goal_test(self, state):
        # returnib True kui state on lõppolek

    def path_cost(self, c, state1, action, state2):
        return c + 1    # uus cost peale ühe sammu tegemist

Ja seda kasutatakse järgmiselt:

problem = EightPuzzle(inistate, goal)
goalnode = search.breadth_first_search(problem)
# sammud (tegevused, käigud) algolekust lõppolekuni
print(goalnode.solution())
# olekud algolekust lõppolekuni
print(goalnode.path())

Oleku esitus

Alustada tuleks sellest, et otsustada, kuidas esitada programmis:

• üks mänguseis, ehk olek
• üks tegevus (action), mis selles mängus on klotsi liigutamine

eeldame, et algolek ja lõppolek on sellised:

 1 2 3  1 2 3
 7   5  4 5 6
 8 4 6  7 8

Märkus: kui oled valinud oleku esituse, proovi Pythoni konsoolist, kas hash(olek) toimib. Osad otsingualgoritmid eeldavad seda.

Actions

   def actions(self, state):
       # returnib actionite listi
   

Tee meetod, mis leiab kõik võimalikud käigud suvalisest etteantud olekust. Seda meetodit rakendatakse iga kord, kui suvalise oleku naaberolekuid otsitakse.

Result

   def result(self, state, action):
       # returnib UUE oleku

Tee meetod, mis returnib oleku, mis tekib kui olekus state tehakse tegevus action. Pane tähele, et state ei tohi modifitseerida. Pead konstrueerima uue oleku.

Goal test

   def goal_test(self, state):
       # returnib True kui state on lõppolek

Kontrolli, kas state on lõppolek. search.Problem lähtekoodi uurides võid veenduda, et selle klassi instantsi initsialiseerimisel pannaks self.goal väärtuseks etteantud lõppolek. Sellega tulebki võrrelda.

Path cost

Seda meetodit pole vaja defineerida, kuna vaikimisi on Problem klassis ühe sammu maksumus 1. 8-Puzzle puhul see sobib, kuna klotside nihutamisega ei ole seotud mingit teepikkust, kulu vms.

Testimine

Veel olekuid testimiseks

 1 8 2
   4 3
 7 6 5

 5 4
 6 1 8
 7 3 2

 8 6 7
 2 5 4
 3   1