Otsingualgoritmides

Otsingualgoritmides on meetodid, mille abil leitakse lahendus antud probleemile, kui lahenduseks on tee ruumi läbi seisundite ja üleminekute. Probleemid mudeldatakse tavaliselt graafi või puu kujul, kus iga sõlm kirjeldab olekut ja servad tähistavad tehtavaid samme või üleminekuid. Eesmärk võib olla leida lühim tee, odavaim tee või mis tahes kehtiv lahendus.

Otsingualgoritmide klassifikatsioon jaguneb sageli uninformed (blind) ja informed (heuristiline) otsingute vahel. Uninformed otsingud kasutavad ainult probleemi kirjeldust ning näiteid on lai otsing (Breadth-First Search, BFS) ja sügav otsing (Depth-First Search, DFS), samuti ühtlase kulu otsing (Uniform-Cost Search). Informeeritud otsingud kasutavad heuristikat: näidetena A* otsing (A*), mis püüab odavama kogukuluga lahendust leida, ning Greedy best-first otsing, mis eelistab teed, mis näib sihtkohta lähemal. Heuristikad peaksid andma head hinnangu ja mõnel juhul olema lubavad ning järjepidevad, et tagada soovitud omadused.

Otsingualgoritmide omadused hõlmavad täielikkust (kas algoritm leiab lahenduse kui see eksisteerib) ja optimaalsust (kas leiab parima lahenduse), samuti aega ja ruumi keerukust. Paljud lähenemised püüavad tasakaalustada mälu ja kiirust, näiteks iteratiivse sügavusotsingu või kahendsuhtelise otsingu abil.

Rakendused hõlmavad teekonna planeerimist, puslemängude lahendamist (nt 8-puzzle), tehisintellekti probleemide otsingul ning robotite liikumise kavandamist. Otsingualgoritmid on seetõttu keskne osa paljudes arvutipõsetes lahendustes.