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. Otsingualgoritme ennast pole vaja implementeerida, need on juba olemas ning meil tuleb ülesanne lihtsalt sobival kujul ära kirjeldada.

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_graph_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.

Otsingustrateegiate võrdlus

Võrdluse tegemiseks uuri search.py lõppu. Seal on funktsioon compare_searchers

search.compare_searchers([problem], ["Strateegia", "algolek1"],
                      searchers=[search.breadth_first_graph_search])

Tekib umbes selline väljund:

Strateegia                   algolek1             
breadth_first_graph_search         <  45/  84/ 128/(1, >

Numbrid tulevad klassist search.InstrumentedProblem. Uuri seda, et aru saada, mida need tähendavad. Põhimõtteliselt huvitab meid läbitud tsüklite arv, ehkki ka genereeritud järglaste arv võib olla oluline mälukasutuse seisukohast.

Testimise lihtsustamiseks võib nii seda klassi kui ka search.py sees olevaid otsingualgoritme modifitseerida:

• prindi leitud lahenduse pikkus sammudes
• lõpeta otsing näit. 10000 või 100000 tsükli järel

Vaja on testida selliseid strateegiaid (puuotsingu strateegiaid me ei vaata)

search.breadth_first_graph_search
search.depth_first_graph_search
search.iterative_deepening_search

Veel algolekuid testimiseks

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

Lisaülesanne

(Mittekohustuslik)

Leia 8-Puzzle jaoks sobivaid heuristikuid. Ideede saamiseks vt. õpikust 3.6.

Implementeeri heuristik(ud) oma EightPuzzle klassi meetodina, see võimaldab ligipääsu näit. otsitavale lõppolekule.

Korda ülalolevat testi nende algoritmidega:

search.greedy_best_first_graph_search
search.astar_search
search.recursive_best_first_search

Kuna compare_searchers() ei oska nendele heuristiku parameetrit ette anda, siis tee ise vajalik wrapper näiteks nii:

def astar_h1(p):
    return search.astar_search(p, p.h1)