Ifi6057lab2

TL;DR

Teises kodutöös tuleb katsetada, kuidas otsingualgoritmid labürinti läbivad.

• Kasuta moodulit lab2.py ja kirjuta laiutiotsingu (breadth-first search) funktsioon labürindis tee leidmiseks.

Edasine on mittekohustuslik, annab rohkem punkte:

1. Lisa otsingufunktsioonile erineva statistika kogumine.
2. Täiusta laiutiotsingut, nii et see ei raiskaks aega lahenduste peale, mis käivad ringiratast või ei uuriks mitu korda sama labürindi ruumi.
3. Katseta erinevaid variante ja kirjuta raport (.PDF/.txt), kus on tabel statistikaga ja selgitus, miks sellised numbrid tulid.
4. Kopeeri laiutiotsingu funktsioon ja muuda see sügavutiotsinguks (depth first search). Tee sügavutiotsingu kohta samasugused katsed ja täienda raportit.
5. Tee juurde omal valikul kas iteratiivselt sügavnev (IDS) või ahne otsing (greedy search). Lisa statistika ja selgitused raportisse.
6. Lisa A*, statistika ja selgitus. A* vajab ka heuristilist funktsiooni

Lõpuks:

• Saada töö 27. oktoobri kella 23.59-ks (päev enne harjutustundi) aadressile priit at whitedb.org.
• Tule harjutustundi ja kaitse töö kuni 11. novembrini (k.a.)

Kõige kohta on allpool detailsem õpetus ja mis veel olulisem, nõuded.

Esimesed katsetused

Et moodulit lab2.py kasutada, laadi see alla. Mediawiki paneb automaatselt faili algustähe suureks, tee see väikseks tagasi (Lab2.py --> lab2.py). Tee esiteks omale eraldi .py fail, kuhu ülesande lahendust hakata tegema ning kirjuta sinna import lab2. Pane oma .py ja lab2.py samasse kataloogi.

Katsetamise jaoks tuleb esiteks genereerida labürint. Selleks tuleb tekitada ülesande objekt (tüüpi SearchProblem), mis oskab matriklinumbri (üliõpilaskoodi numbrilise osa) järgi individuaalse labürindi teha. Grupi peale võib valida ühe osaleja numbri. Näiteks:

 import lab2

 p = lab2.SearchProblem(123456) # siia oma number
 p.dump()

Viimane rida joonistab labürindi plaani. Sissepääs on vasakul ja väljapääs paremal.

Laiutiotsing

Nõuded

• funktsioon, mis implementeerib elementaarse laiutiotsingu, kasutades lab2.SearchProblem klassi.
• siin ja edaspidi eeldatakse, et lab2 moodulit kasutatakse sellisel kujul nagu ette antud. Kui tekib tahtmine või vajadus selle sisu torkida, siis kooskõlastada see õppejõuga, näit. 14. oktoobri harjutustunnis.

Õpetus

Siin on pseudokood loenguslaididelt mõnevõrra lihtsustatud kujul.

 function TreeSearch(problem) returns a goal node, or failure
   fringe.Insert(problem.InitialState)                # alguspunkt järjekorda
   loop do
      if fringe is empty then return failure
      node := fringe.RemoveFront()                 # järjekorras esimene tipp
      if GoalTest(problem, node) then return node
      fringe.AppendAll(problem.Expand(node))       # lisa järglased järjekorda

See on kõik, mida esialgu vaja teha. Kuidas Expand teha, ehk siis millised labürindi ruumid hetkeasukoha kõrval asuvad ning muu tarkus, näiteks otsingupuu andmestruktuuri ehitamine, asuvad kõik lab2 moodulis.

Hakkame ülalt pihta. Fringe tüüpi objekt sobib järjekorra ehitamiseks:

 f = lab2.Fringe()
 f.is_empty()
 True
 f.add_end("a")
 f.add_end("b")
 f.add_end("c")
 f.remove_front()
 'a'
 f.add_front("d")
 f.remove_front()
 'd'
 len(f) # palju veel sees on
 2

Fringe objekti meetodid:

• add_end(node) - mine ilusti järjekorra lõppu
• add_by_priority(node, priority) - vaheletrügimine, vastavalt tähtsusele. Priority on siin ülesandes teepikkuse hinnangufunktsioon, mida väiksem, seda parem.
• add_front(node) - eriti jõhker ettetrügimine esimesele positsioonile
• remove_front() - returnib järjekorras ootava asja. Välja võetakse järjekorrast alati algusest.
• is_empty() - True kui enam pole midagi võtta, muidu False

Esialgu tuleb pseudokoodi järgi järjekorda panna algolek, ehk ruum, kust pihta hakatakse. Selle saab kätte nii:

 #p = lab2.SearchProblem(123456)
 initial_state = p.start_node()

See meetod (ja ka expand edaspidi) tagastavad lab2.Node tüüpi asju, mis kujutavad endast otsingupuu tippe (i.k. node). Need vastavad kõik mingile ruumile labürindis, ehk siis otsinguruumi (search space) ühele olekule. Aga puus võib üks labürindiruum esineda korduvalt, juhul kui otsing näiteks ringiratast käib.

Selleks, et otsing ükskord ära lõppeda saaks, tuleb kontrollida, kas hetkel uuritav puu tipp vastab ülesande lõppolekule (väljapääsu juures asuvale ruumile):

 p.is_goal(initial_state)
 False

Kõige olulisem asi otsingupuu ehitamise juures on tippudele järglaste genereerimine. Seda teeb expand meetod.

 p.expand(initial_state)
 [(1, 13)]

Antud näite puhul saab esimesest ruumist ainult ühes suunas liikuda. Tegu on aga listiga ja seal saab ka rohkem node-sid olla. Kõik võimalikud järglased tagastatakse alati; kui soovid vältida et otsing näiteks kahe ruumi vahel edasi-tagasi ei saaks pendeldada, tuleb juba ise midagi ette võtta. Seda aga kodutöö kõige esimeses osas ei ole nõutud, kuna laiutiotsing kõige lihtsamal kujul piirab ka teatud määral selliseid liikumisi.

Kõik see mahub ilusti ühte lühikesse funktsiooni. Näide, mille võib endale aluseks võtta (Hoiatus: tegu ei ole laiutiotsinguga. Mismoodi see erineb ja kuidas laiutiotsing saada, mõtle juba ise välja).

  from lab2 import SearchProblem, Fringe
  import random

  def silly_search(problem):
      fringe = Fringe()
      fringe.add_front(problem.start_node())

      while 1: # lõputu tsükkel
          if fringe.is_empty():
              return None # ei leitud lahendust

          node = fringe.remove_front()
          if problem.is_goal(node):
              return node # puu tipp. Tee siit puu juurikasse ongi lahendus

          children = problem.expand(node) # children on list tyypi; [ node1, node2, .... ]
          fringe.add_front(random.choice(children))  # valime yhe ja paneme jrk ette

Ja labürindi peale saab seda rakendada sedasi:

   p = SearchProblem(123456)
   res = silly_search(p)
   if res is None:
       print ("Not found")
   else:
       p.print_path(res)
       p.print_solution(res)

Kui tulemus leitakse, siis saab seda kahte moodi näidata. Ülesandeobjekti print_path meetod trükib ainult koordinaadid välja, aga annab ka lahenduse pikkuse sammudes. print_solution joonistab labürindi koos leitud teega.

Laiutiotsingu puhul on vägagi tõenäoline, et lahendust esialgu mingi mõistliku aja jooksul ei leita. Seda probleemi võib hetkel ignoreerida. Mugavuse mõttes võib otsingusse ehitada mingi viisi otsinguaega piirata.

Siiamaani tehtud töö annab 3 punkti ja läheb arvesse eksamieeldusena.

Statistika

Nõuded

Iga testitava otsingustrateegia / algoritmi ja selle variatsiooni puhul peab leidma järgmised parameetrid:

• läbitud tippude arv;
• hargnemistegur b (branching factor). Mitu järglast keskmiselt tipul on, või siis kui palju erinevaid edasiliikumise võimalusi mingist ruumist;
• maksimaalne järjekorra (frontier, fringe) pikkus;
• puu maksimaalne sügavus d.

Kui seda osa ei ole tehtud, siis ei anna täiendavad otsingufunktsioonid lisapunkte.

Õpetus

Pythonis on lubatud mitu väärtust tagastada, seega statistika kätte saamiseks otsingufunktsiooni seest võid teha näiteks nii:

 def silly_search(problem):
     node_count = 0 # mingi esialgne statistika
     max_queue = 0
     # ... otsi, täienda statistikat
     return node, node_count, max_queue
     # ...

Ja välja kutsuv funktsioon saab need niiviisi kätte:

 res, node_count, max_queue = silly_search(p)
 print ("Stats", node_count, max_queue)

Üks nõutud parameeter on järjekorra pikkus. Seda saab nii vaadata:

 len(fringe)

Otsingupuu sügavus võib küsimusi tekitada - rekursiivses sügavutiotsingus oleks selle üle lihtne arvet pidada, aga esialgu on tegu hoopis iteratiivse laiutiotsinguga. Õnneks on Node tüüpi objektide sees juba atribuut depth, mis ütleb, kui sügaval puus antud tipp asub.

 initial_state.depth
 0

Otsingu täiustused

Nõuded

Otsingufunktsioon peab toimima kolmel võimalikul viisil:

1. Pimeotsing, kõik järglasolekud lisatakse alati puule. Tsüklid võimalikud.
2. Kontrolli, kas järglasele vastav ruum on juba läbitud teel puu juurikast hetkeolekusse, sellised järglased visatakse minema; või
3. kontrolli, kas järglasele vastav ruum on juba külastatud kusagil otsingu käigus (võib ka mitte paikneda praegusel teel vaid kuuluda mingi ennem uuritud tee juurde). Kui on, siis uuesti pole vaja ruumi külastada

Nõue kehtib ka kõikide edaspidi implementeeritavate funktsioonide kohta.

Õpetus

Selleks, et vältida uuesti astumist teele, mida mööda algpunktist on tuldud, saab kasutada funktsiooni lab2.in_path.

 newnode = p.expand(initial_state)[0] # lihtsalt mingi ruum näitena
 lab2.in_path(initial_state, newnode)
 False
 lab2.in_path(newnode, initial_state)   # kas initial_state asub teel alguspunktist newnodesse?
 True

Et üleüldse kõiki otsingu poolt külastatud ruume meelde jätta, võib kasutada Pythoni tüüpi set (hulk), mis sisaldab kiiret liikmelisuse kontrolli - listitüübi puhul on see aeglane. Sinna hulka võib otse puu elemente panna, kuna kahte Node tüüpi asja saab omavahel võrrelda ja nad loetakse võrdseks, kui nad sama ruumi esindavad.

 newnode == initial_state
 False

Hulga tegemine, puu tipu lisamine, liikmelisuse kontroll:

 visited = set()
 visited.add(initial_state)
 initial_state in visited
 True
 newnode not in visited
 True

Raport

Nõuded

• formaat on PDF või txt. Mingis muus formaadis raporti puhul võetakse punkte maha.
• Raportis on tabel, kus on iga testitud funktsiooni / variandi kohta mõõdetud parameetrid (vt. nõuded statistikale).
• Saadud numbrilistele tulemustele on lisatud seletus (näiteks miks algoritm A annab optimaalsema tulemuse kui B, miks A külastab rohkem tippe kui B jne).
• Kui labürindi suurust on SearchProblem klassi siin juhendis dokumenteerimata parameetrite kaudu muudetud, siis raportis peavad ikkagi kõik testid ka vaikimisi suurusega (70x22) kajastatud olema.

Laiutiotsingu paranduste, statistika lisamise ja raporti koostamise järel on töö väärtus 9 punkti.

Sügavutiotsing

Sügavutiotsingut saab kõige kiiremini teha nii, et võtta ette juba loodud laiutiotsingu funktsioon ja teha see vastavalt vajadusele ringi. Sedasi tulevad kaasa nii statistika korjamine kui ka teekonna / külastatud tippude kontrollimise funktsionaalsus.

Sügavutiotsingu lisamise ning sellega tehtud katsete raportisse lisamise järel saab töö eest 12 punkti.

Ahne otsing ja A*

Ahne otsingu (greedy search) ja A* puhul läheb tarvis heuristilist funktsiooni. lab2 moodul pakub kahte, mille vahel valida:

• lab2.h1(problem, node) - Manhattan distance; lühim võimalik teepikkus node ja problem-is sisalduva labürindi väljapääsu vahel. Arvestab, et asutakse ruudustikul, kus liikuda on lubatud ainult neljas suunas. Antud täisarvuna
• lab2.h2(problem, node) - kaugus linnulennult. Antud reaalarvuna.

A* tahab teada ka senini läbitud tee pikkust. Selleks on Node objektil meetod path_cost.

 initial_state.path_cost()
 0

Järjekorra koostamiseks kasuta spetsiaalselt selleks mõeldud add_by_priority meetodit.

 f=lab2.Fringe()
 f.add_by_priority("a", 2.3)
 f.add_by_priority("b", 3.3)
 f.add_by_priority("c", 0.1)
 f.remove_front()
 'c'
 f.remove_front()
 'a'

Ahne otsing ja A* annavad korrektse raporteerimise korral kumbki 3 punkti juurde. Ahne otsingu asemel võib aga teha ka iteratiivselt sügavneva otsingu süvitiotsingu baasil (IDS).

Maksimaalselt on võimalik saada 18 punkti.