Heuristinen algoritmi
Heuristinen algoritmi (heuristinen) on algoritmi ongelman ratkaisemiseksi, mukaan lukien käytännön menetelmä, jonka tarkkuutta tai optimaalista ei taata, mutta joka riittää ratkaisemaan ongelman. Voit nopeuttaa ongelman ratkaisua tapauksissa, joissa tarkkaa ratkaisua ei löydy.
Määritelmä
Heuristinen algoritmi on algoritmi ongelman ratkaisemiseksi, jonka oikeellisuutta kaikkiin mahdollisiin tapauksiin ei ole todistettu, mutta jonka tiedetään useimmissa tapauksissa antavan varsin hyvän ratkaisun. Itse asiassa voidaan jopa tietää (eli todistettu), että heuristinen algoritmi on muodollisesti väärä. Sitä voidaan edelleen käyttää, jos se antaa väärän tuloksen vain tietyissä, melko harvinaisissa ja hyvin erottuvissa tapauksissa tai se antaa epätarkan, mutta silti hyväksyttävän tuloksen.
Yksinkertaisesti sanottuna heuristinen on algoritmi, joka ei ole täysin matemaattisesti järkevä (tai edes "ei aivan oikea"), mutta samalla käytännössä hyödyllinen algoritmi.
On tärkeää ymmärtää, että heuristiikassa, toisin kuin oikealla ongelmanratkaisualgoritmilla, on seuraavat ominaisuudet.
- Se ei takaa parhaan ratkaisun löytämistä.
- Se ei takaa ratkaisun löytämistä, vaikka se varmasti olisikin olemassa (on mahdollista "missata tavoite").
- Se voi joissain tapauksissa antaa väärän ratkaisun.
Sovellus
Heuristisia algoritmeja käytetään laajalti laskennallisesti monimutkaisten ongelmien ratkaisemiseen , toisin sanoen täydellisen vaihtoehtojen luettelon sijasta, mikä vie huomattavasti aikaa ja joskus teknisesti mahdotonta, käytetään paljon nopeampaa, mutta teoreettisesti riittämättömästi perusteltua algoritmia. Tekoälyn alueilla , kuten hahmontunnistuksessa , heuristisia algoritmeja käytetään laajalti myös yleisen ratkaisun puuttumisen vuoksi. Erilaisia heuristisia lähestymistapoja käytetään virustorjuntaohjelmissa , tietokonepeleissä jne. Esimerkiksi shakkia pelaavat ohjelmat pelaavat pelin puolivälissä, ja ne perustuvat pääasiassa heuristisiin algoritmeihin ( tietokanta voidaan käyttää avauksessa , Nalimov-taulukoita loppupeleissä , mutta in Keskipelissä mahdollisten siirtojen määrä estää usein tyhjentävän luettelon, eikä tarkkoja algoritmeja oikealle pelille ollut olemassa pitkään aikaan).
Judah Perlin mukaan heuristiset menetelmät perustuvat älylliseen strategioiden etsimiseen ongelman ratkaisemiseksi useiden vaihtoehtoisten lähestymistapojen avulla [1] .
Mahdollisuus (hyväksyttävä) käyttää heuristiikkaa kunkin tietyn ongelman ratkaisemiseen määräytyy ongelman täsmällisillä ja heuristisilla menetelmillä ratkaisemisen kustannusten, virheen kustannusten ja heuristiikan tilastollisten parametrien suhteen. Lisäksi on tärkeää, onko lähdössä "terveen järjen suodatin" eli ihmisen arvio tuloksesta.
Esimerkki heuristisesta päätöksenteosta
Tarkastellaanpa spekulatiivista esimerkkiä. Oletetaan, että ongelman ratkaisemiseksi on olemassa hyvin tunnettu, mutta erittäin monimutkainen, tarkka algoritmi ja heuristinen, joka vaatii 1000 kertaa vähemmän vaivaa ja antaa useimmiten hyväksyttävän ratkaisun (tosin 95 % tapauksista). Yksinkertaisuuden vuoksi oletetaan, että tarkan ratkaisun hinta on vakio, samoin kuin virheen hinta.
Tällöin heuristinen ratkaisu maksaa keskimäärin , missä T on tarkan ratkaisun hinta ja E on virheen hinta. Ratkaisun keskimääräinen kustannusero tarkoilla ja heuristisilla menetelmillä eli heuristinen keskimäärin osoittautuu kannattavammaksi kuin tarkka ratkaisu, ellei virheen hinta ylitä kaksikymmentä kertaa (!) tuotteen hintaa. tarkka ratkaisu.
Jos lähdössä henkilö arvioi päätöksen tuloksen kriittisesti, tilanne paranee entisestään: kun heuristin synnyttämä virhe osoittautuu liian pieneksi, jotta ihminen sitä huomaa, tämän virheen hinta on yleensä paljon pienempi, ja vakavat virheet suodatetaan pois "maalaisjärkisuodattimella", joten niistä ei aiheudu merkittävää haittaa.
Katso myös
Muistiinpanot
- ↑ Helmi, Juudea. Heuristiikka (uuspr.) . - Addison-Wesley Pub, 1984. - ISBN 0201055945 .
Kirjallisuus
- S. Goodman. Johdatus algoritmien kehittämiseen ja analysointiin / S. Goodman, S. Hidetniemi. - M .: Mir, 1981.
- D. D. Ulman . Tietorakenteet ja algoritmit / A. V. Akho , D. E. Hopcroft , D. D. Ulman . - M .: Williams; SPb. ; Kiova, 2001.