Heurisztikus algoritmus
A heurisztikus algoritmus (heurisztikus) egy probléma megoldására szolgáló algoritmus , beleértve egy olyan gyakorlati módszert, amely nem garantáltan pontos vagy optimális, de elegendő a probléma megoldásához. Lehetővé teszi a probléma megoldásának felgyorsítását olyan esetekben, amikor a pontos megoldás nem található.
Definíció
A heurisztikus algoritmus egy olyan probléma megoldására szolgáló algoritmus, amelynek helyessége minden lehetséges esetre nem bizonyított, de amelyről ismert, hogy a legtöbb esetben meglehetősen jó megoldást ad. Sőt, még az is lehet, hogy ismert (vagyis bebizonyosodott), hogy a heurisztikus algoritmus formailag hibás. Továbbra is használható, ha ugyanakkor csak bizonyos, meglehetősen ritka és jól megkülönböztethető esetekben ad hibás eredményt, vagy pontatlan, de mégis elfogadható eredményt ad.
Egyszerűen fogalmazva, a heurisztika olyan algoritmus, amely matematikailag nem teljesen helytálló (vagy akár „nem egészen helyes”), ugyanakkor gyakorlatilag hasznos algoritmus.
Fontos megérteni, hogy a heurisztika, ellentétben a problémamegoldás helyes algoritmusával, a következő jellemzőkkel rendelkezik.
- Nem garantálja a legjobb megoldás megtalálását.
- Nem garantálja a megoldás megtalálását, még akkor sem, ha az biztosan létezik (lehet „eltéveszteni a célt”).
- Bizonyos esetekben rossz megoldást adhat.
Alkalmazás
A heurisztikus algoritmusokat széles körben alkalmazzák nagy számítási bonyolultságú problémák megoldására , azaz a lehetőségek teljes felsorolása helyett, ami jelentős időt vesz igénybe, és néha technikailag lehetetlen, sokkal gyorsabb, de elméletileg nem kellően alátámasztott algoritmust használnak. A mesterséges intelligencia területein , mint például a mintafelismerés , a heurisztikus algoritmusokat széles körben alkalmazzák a probléma általános megoldásának hiánya miatt is. Különféle heurisztikus megközelítéseket használnak a vírusirtó programokban , számítógépes játékokban stb. Például a sakkot játszó programok a játék közepén játszanak, főként heurisztikus algoritmusokon alapulnak ( adatbázis használható a nyitásban , Nalimov táblázatok a végjátékban , de a játékban a középső játékban a lehetséges lépések száma gyakran kizárja a teljes felsorolást, és sokáig nem léteztek pontos algoritmusok a helyes játékhoz).
Judah Perl szerint a heurisztikus módszerek a problémamegoldó stratégiák intellektuális keresésén alapulnak több alternatív megközelítés alkalmazásával [1] .
A heurisztika alkalmazásának lehetőségét (megengedhetőségét) az egyes problémák megoldására az egzakt és heurisztikus módszerekkel történő problémamegoldás költségeinek, a hiba költségének és a heurisztika statisztikai paramétereinek aránya határozza meg. Ezenkívül fontos a „józan ész szűrőjének” megléte vagy hiánya a kimeneten, vagyis az eredmény értékelése.
Példa a heurisztikus döntésértékelésre
Nézzünk egy spekulatív példát. Tegyük fel, hogy létezik egy jól ismert, de rendkívül összetett, pontos algoritmus a probléma megoldására, és egy 1000-szer kevesebb erőfeszítést igénylő heurisztika, amely legtöbbször elfogadható megoldást ad (igaz, az esetek 95%-ában). Az egyszerűség kedvéért feltételezzük, hogy egy pontos megoldás költsége állandó, csakúgy, mint egy hiba költsége.
Ekkor átlagosan a heurisztikus megoldás költsége , ahol T a pontos megoldás költsége, E pedig a hiba költsége. A megoldás költségének átlagos különbsége az egzakt és a heurisztikus módszerekkel , vagyis a heurisztika átlagosan jövedelmezőbbnek bizonyul, mint a pontos megoldás, kivéve, ha a hiba költsége meghaladja a megoldás árának húszszorosát (!) pontos megoldás.
Ha a kimeneten egy személy kritikusan értékeli a döntés eredményét, akkor a helyzet még jobbá válik: amikor a heurisztika által generált hiba kicsinek bizonyul ahhoz, hogy az ember észrevegye, ennek a hibának az ára általában jóval alacsonyabb, és a súlyos hibákat a „józan ész szűrője” kiszűri, így nem okoz jelentős kárt.
Lásd még
Jegyzetek
- ↑ Pearl, Júdea. Heurisztika (neopr.) . - Addison-Wesley Pub, 1984. - ISBN 0201055945 .
Irodalom
- S. Goodman. Bevezetés az algoritmusok fejlesztésébe és elemzésébe / S. Goodman, S. Hidetniemi. - M .: Mir, 1981.
- D. D. Ulman . Adatstruktúrák és algoritmusok / A. V. Akho , D. E. Hopcroft , D. D. Ulman . — M .: Williams; SPb. ; Kijev, 2001.