Algoritmityylejä

Algoritmityylejä kuvaa erilaisten ongelmien ratkaisuun ja algoritmien suunnitteluun liittyviä lähestymistapoja ja periaatteita. Termi viittaa siihen, miten ongelma jäsentyy ja miten ratkaisua etsitään, eikä koodauksen syntaksiin. Algoritmityylien tunteminen auttaa valitsemaan sopivan menetelmän sekä ymmärtämään, millaisia etuja ja rajoituksia kukin lähestymistapa tuo erilaisiin ongelmatilanteisiin.

Yleisimmät tyylit ovat brute-force, greedy, divide and conquer, dynamic programming sekä backtracking. Brute-force tarkoittaa kaikkien mahdollisuuksien täydellistä läpikäyntiä. Greedy-tyylinen lähestymistapa valitsee kussakin vaiheessa parhaan nykyisen vaihtoehdon, usein ilman takaisinseurantaa. Divide and conquer jakaa ongelman pienempiin osiin, ratkaisee ne rekursiivisesti ja yhdistää tulokset. Dynamic programming tallentaa aliohjelmien ratkaisut ja käyttää niitä uudelleen päällekkäisten alojen välttämiseksi. Backtracking etsii ratkaisuja rajoja pitkin, mutta käyttää seuranta- ja leikkausmenetelmiä tehokkuuden parantamiseksi.

Lisäksi käytetään heuristiikkoja ja satunnaistettuja menetelmiä sekä online- ja offline-lähestymistapoja. Heuristiikat tarjoavat käytännön, usein nopeita ratkaisuja, kun täydellinen ratkaisu on epärealistinen. Satunnaistettuja menetelmiä käytetään erityisesti suurissa tai epälineaarisissa ongelmissa, joissa deterministinen ratkaisu on liian hidasta.

Algoritmityylin valinta perustuu ongelman ominaisuuksiin, kuten onko ongelmalla optimaaliset aliratkaisut, onko ratkaisut päällekkäisiä ja millaiset aikavaatimukset on asetettu. Esimerkkejä ovat Huffman-koodaus (greedy), mergesort (divide and conquer), knapsack-ongelma (dynamic programming) ja N-queens-ongelma (backtracking). Lyhyimmän polun etsintään sovelletaan sekä greedyn että DP:n periaatteita.