Etsintätilaa

Etsintätila on termi, jota käytetään tietojenkäsittelytieteessä kuvaamaan kaikkia mahdollisia ratkaisujen tai tilojen joukkoja, joita ongelman ratkaisemiseksi voidaan tarkastella. Etsintätilan koko ja rakenne vaikuttavat siihen, millaisia algoritmeja voidaan käyttää ja miten tehokkaita ne ovat.

Käytännössä etsintätila mallinnetaan grafina tai puuna, jossa solmut ovat tiloja ja reunat kelvollisia siirtymisiä. Esimerkkejä: reitin etsimisessä tilat ovat sijainteja ja siirrot liikkeitä; pulmien ratkaisuissa tilat ovat pelin asetuksia; optimoinnissa tilat ovat päätösmuuttujien arvoja.

Algoritmit hyödyntävät erilaisia hakustrategioita. Systemaattinen haku etenee tiloja järjestelmällisesti ja pyrkii kattamaan koko tilan; esimerkkejä ovat tilojen laaja läpikäynti ja syvyyssuuntautunut haku. Heuristiikkaan perustuvat menetelmät, kuten A*-tyyppiset ratkaisut, ohjaavat hakua lupaavimpiin tiloihin. Paikallinen haku tutkii naapuritiloja ja parantaa ratkaisua pienissä osissa. Rajoitusmenetelmät ja karsinta pienentävät tutkittavaa tilaa.

Kokonaisuudessaan etsintätilan tehokkuuteen vaikuttavat ongelman luonne ja tilan räjähdysmäinen kasvu. Monimutkaisissa tapauksissa kombinatorinen räjähdys on keskeinen haaste; heuristiikka, prunet, rajoitteiden kautta tapahtuva päättely ja symmetrian hyödyntäminen auttavat.

Etymologia: termi juontuu suomen sanoista etsintä ja tila. Sillä viitataan abstraktiin tilaan, jota ratkaiseva järjestelmä tutkii.