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

Testimine

Veel olekuid testimiseks

 1 8 2
   4 3
 7 6 5

 8 6 7
 2 5 4
 3   1