Section outline

  • V tem poglavju smo najprej spoznali tako imenovane neinformirane preiskovalne algoritme, iskanje v globino, iskanje v širino in iterativno poglabljanje. Poleg same uporabnosti teh algoritmov, nam kasneje velikokrat pridejo prav koncepti, ki smo jih pri tem spoznali (npr. poglabljanje, vračanje ali uporaba iskanja v globino znotraj kompleksnejših algoritmov). Algoritme so primerjali glede na njihovo prostorsko in časovno zahtevnost in glede na optimalnost rešitve (merjene kot število korakov). V drugem delu tega poglavja smo spoznali kako koristne so lahko hevristične ocene, ki vodijo preiskovanje. Spoznali smo informirana algoritma A* in IDA* ter videli, da oba zagotavljata optimalnost rešitve (v smislu njene cene) pod pogojem, da je hevristična funkcija, ki ju vodi, dopustna. Spoznali smo tudi pomen monotone (konsistentne) hevristične funkcije za algoritem IDA*.

    Naučili smo se tudi, kako konkreten problem opišemo v t.i. prostoru stanj, da ga lahko potem rešimo s pomočjo preiskovalnih algoritmov.

    Vse pojme lahko vidite in preizkusite na primeru sveta GridWorld v Python zvezku spodaj. Zraven snemite ločeno datoteko s preprostimi implementacijami preiskovalnih algoritmov (bsearch.py), ki jo zvezek potrebuje za delovanje.