A* on joukko vaiheita (algoritmi), joiden avulla tietokoneet voivat selvittää, miten päästä nopeasti jonnekin kahden paikan välillä. Jos sinulla on luettelo paikoista ja tiedot siitä, kuinka vaikeaa tai kallista on liikkua suoraan yhdestä paikasta toiseen, A*:n avulla voit tehokkaasti löytää lyhyimmän tai edullisimman reitin. Se on läheistä sukua Dijkstran algoritmille, mutta A* käyttää arvioita (heuristiikkaa) ohjatakseen hakua kohti maalia, joten se tekee vähemmän turhia tarkistuksia kuin pelkkä Dijkstra. A* on hyvä valinta, kun haluat etsiä reitin yhdestä pisteestä toiseen. Jos sen sijaan haluat löytää kaikkien parien pisimmät tai lyhimmät reitit samasta kartasta kerralla, kannattaa harkita esimerkiksi Floyd–Warshallin algoritmia. A* ei myöskään sovellu ratkaisemaan ongelmia, joissa pitää käydä useassa paikassa yhdessä matkassa (travelling salesman -ongelma).

Miten A* toimii

A* pitää yllä kahta joukkoa: open-joukkoa (solmut, joita aiotaan vielä tutkia) ja closed-joukkoa (solmut, jotka on jo tutkittu). Jokaiselle solmulle n algoritmi laskee arvion kustannuksesta päästä lähtökohdasta kyseiseen solmuun (g(n)) ja arvio kustannuksesta solmusta maaliin (h(n), heuristiikka). Solmun kokonaisarvio on f(n) = g(n) + h(n). A* valitsee aina sen open-joukon solmun, jolla on pienin f-arvo, laajentaa sitä ja päivittää naapureita.

Keskeiset käsitteet

  • g(n) = todellinen kustannus lähtöpisteestä solmuun n.
  • h(n) = heuristiikka: arvio jäljellä olevasta kustannuksesta solmusta n maaliin.
  • f(n) = g(n) + h(n) = arvioitu kokonaiskustannus reitistä lähtöpisteestä maaliin, joka kulkee solmun n kautta.
  • Admissible (hyväksyttävä) heuristiikka = heuristiikka, joka ei yliarvioi todellista jäljellä olevaa kustannusta. Jos h(n) ei koskaan yliarvioi, A* on optimaalinen (löytää lyhimmän reitin).
  • Consistent / monotone heuristiikka = heuristiikka, jonka täytyy täyttää h(n) ≤ cost(n, m) + h(m) kaikille kaarille n→m. Konsistentti heuristiikka takaa, että f-arvot eivät pienene polkua pitkin, mikä yksinkertaistaa toteutusta.

Pseudokoodi (lyhyt kuvaus)

Yksinkertaistettuna A* toimii näin:

  • Aseta lähtösolmu open-joukkoon, g(alku)=0, f(alku)=h(alku).
  • Kun open ei ole tyhjä: valitse openista solmu n, jolla on pienin f(n).
  • Jos n on maali → rakenna polku takaisin lähtöön ja palauta se.
  • Siirrä n closed-joukkoon ja käsittele kaikki naapurit m:
  • - laske mahdollinen uusi g-arvo: g_new = g(n) + cost(n,m).
  • - jos m on closed ja g_new ≥ g(m) → ohita; muuten päivitä g(m), f(m) ja edeltäjä ja lisää m openiin.
  • - jos m ei ole openissa → lisää se openiin.

Heuristiikoita (esimerkkejä)

  • Manhattan-etäisyys (ruudukko, liikkuminen neljään suuntaan): |dx| + |dy|.
  • Euclidean-etäisyys (vapaa taso): suora-etäisyys pisteiden välillä.
  • Chebyshev-etäisyys (ruudukossa, jossa sallitaan diagonaaliliikkuminen kustannuksella 1): max(|dx|, |dy|).

Valitse heuristiikka, joka on realistinen ja mieluiten admissible tai konsistentti, jotta saat optimaalisuuden ja tehokkuuden.

Suorituskyky ja rajoitukset

  • Optimaalisuus: Jos heuristiikka on admissible, A* löytää lyhyimmän reitin.
  • Täydellisyys: A* on yleensä täydellinen (löytää ratkaisun jos sellainen on olemassa), kun heuristiikka on järkevä ja hakutila on äärellinen.
  • Aikavaativuus: Pahimmassa tapauksessa A* voi vaatia eksponentiaalisesti aikaa (riippuu heuristiikan laadusta). Hyvä heuristiikka pienentää tutkittavien solmujen määrää merkittävästi.
  • Tila: A* pitää usein suurta open-joukkoa muistissa, joten muistinkulutus voi rajoittaa käytännön sovelluksia suurissa kartoissa.

Käytännön vinkkejä

  • Käytä mahdollisimman informatiivista, mutta admissible-heuristiikkaa. Mitä lähempänä todellista jäljellä olevaa kustannusta h(n) on, sitä tehokkaampi haku on.
  • Jos muisti on ongelma, harkitse IDA*-tyyppisiä iteratiivisia menetelmiä tai muistikompromisseja (esim. weighted A* tai muistirajoitteiset variantit).
  • Pelien reitinhakuissa usein käytetään yksinkertaisia heuristiikkoja (Manhattan / Euclidean) sekä hakun rajaamista (timeout, maksimi solmujen määrä) käytännön suorituskyvyn takia.
  • Jos teet monta hakua samasta verkosta, ennakkolaskenta (esim. etäisyyden tallentaminen tai reititystaulut) voi olla tehokkaampaa kuin toistuva A*.

Sovelluksia

A* on laajasti käytössä: pelikehityksessä hahmojen reitinhakua varten, robotiikassa polun suunnittelussa, karttapalveluissa ja erilaisissa optimointiongelmissa, joissa etsitään lyhintä reittiä kahden pisteen välillä. Kun tarvitset kaikki parien etäisyydet tai erityisiä käyntirajoitteita (esim. travelling salesman -tyyppiset ongelmat), on syytä valita muita menetelmiä tai laajennuksia.

Yhteenvetona: A* on tehokas ja joustava algoritmi yksittäisten reitinetsintätehtävien ratkaisuun, kun valitset sopivan heuristiikan ja pidät mielessä muisti- ja suorituskykyrajoitukset.