Hakualgoritmi

Hakualgoritmi on algoritmi, jonka tehtävänä on löytää tietty kohde, arvo tai ratkaisu etsintätilassa joko tiedon sisäisestä rakenteesta tai laajemmasta tilasta. Hakualgoritmit ovat keskeisiä monissa tietojenkäsittelyn tehtävissä, kuten tiedonhaussa, tietorakenteiden käytössä, reitityksessä ja tekoälyn ongelmanratkaisussa. Niitä käytetään sekä yksittäisten alkioiden löytämiseen että suunnitteluun, jossa ratkaisu muodostuu osien yhdistämisestä.

Yleisimmät hakualgoritmit voidaan luokitella eri tavoin. Lineaarinen haku käy läpi kaikki alkiot peräkkäin ja on yksinkertainen, mutta hidas, suurissa kokoelmissa yleensä O(n). Binary search toimii järjestetyissä taulukoissa ja on tehokkaampi, O(log n), mutta vaatii järjestettyä dataa. Hash-hakulaitteissa käytetään hajautustaulua, jolloin haku on keskimäärin O(1). Puissa, kuten tasapainotetuissaBST- tai B-puissa, haku on yleensä O(log n). Grafien läpi tapahtuvia hakuja käytetään verkkojen, reitityksen ja pelitehtävien ratkaisuissa, kuten BFS:llä ja DFS:llä. Erityisesti reitinhakualgoritmit, kuten Dijkstra ja A*, etsivät optimaalisen tai kustannustehokkaan polun verkossa.

Käytännössä hakualgoritmeja sovelletaan tietokannoissa ja hakukoneissa, tiedonhallinnassa, ohjelmistojen etsimisessä sekä robotiikassa ja tekoälyssä. Suorituskyky riippuu sekä datan rakenteesta että algoritmin ominaisuuksista sekä odotetuista tiedonhakutilanteista. Yleisesti ottaen valinta perustuu datajoukon koko, järjestettyvyys, päällekkäisten hakujen tarve ja vasteaikavaatimus.