hakualgoritmiin

Hakualgoritmi on ohjelmisto- tai matemaattinen menetelmä, jolla etsitään ratkaisu ongelmalle tilaympäristössä. Ongelma määritellään tilojen joukolla, siirroilla tai muunnoksilla sekä lopetusehdolla, joka määrittelee halutun tilan. Hakualgoritmi etenee tiloja paremmuusjärjestyksessä ja palauttaa yleensä jonkin ratkaisua sisältävän polun tai tilan, kun tavoite toteutuu.

Hakualgoritmit voidaan luokitella useilla tavoilla. Yleisesti erotetaan ei-heuristiset (uninformed) ja heuristiset (informed) hakumenetelmät. Esimerkiksi leveys- ja syvyysjaon hakutoiminnot ovat ei-heuristisia, tutkivat tilaviidakkoa järjestelmällisesti. Niiden vahvuudet ja heikkoudet riippuvat tilojen määrästä ja siirtojen kustannuksista.

Informoituun hakulaskentaan kuuluu heuristiikka, joka antaa arvion kustannuksesta tavoitteeseen. Tunnetuimpia esimerkkejä ovat A*-haku sekä Greedy Best-First -haku. Dijkstran algoritmi hakee pienimmän kustannuksen polun lähdöstä mihin tahansa kohdetilaan, kun kustannukset ovat ei-negatiivisia.

Ominaisuudet: täydellisyys tarkoittaa, että ratkaisu löytyy, jos sellainen on, ja optimaalisuus tarkoittaa, että löydetty ratkaisu on kustannuksiltaan paras mahdollinen. Suorituskyky luetaan usein ajan ja tilan käytön kautta, jotka voivat kasvaa nopeasti tilan määrän kasvaessa.

Sovellukset kattavat tekoälyn ongelmanratkaisun, reittihakulaitteet, verkkosivujen hakukoneiden indeksoinnin sekä tietokantahaun, jossa etsitään merkityksellisiä tiloja tai rivejä. Hakualgoritmit ovat keskeisiä monissa tietojenkäsittelyn ja ohjelmistokehityksen osa-alueissa.