Heuristisk algoritme

Heuristisk algoritme (heuristisk) er en algoritme til at løse et problem, herunder en praktisk metode, der ikke er garanteret nøjagtig eller optimal, men tilstrækkelig til at løse problemet. Giver dig mulighed for at fremskynde løsningen af ​​problemet i tilfælde, hvor den nøjagtige løsning ikke kan findes.

Definition

En heuristisk algoritme er en algoritme til løsning af et problem, hvis rigtighed for alle mulige tilfælde ikke er bevist, men som er kendt for at give en ret god løsning i de fleste tilfælde. Faktisk kan det endda være kendt (det vil sige bevist), at den heuristiske algoritme er formelt forkert. Det kan stadig bruges, hvis det samtidig kun giver et forkert resultat i visse, ret sjældne og velkendte tilfælde, eller det giver et unøjagtigt, men stadig acceptabelt resultat.

Enkelt sagt er en heuristik en algoritme, der ikke er helt matematisk forsvarlig (eller endda "ikke helt korrekt"), men samtidig en praktisk anvendelig algoritme.

Det er vigtigt at forstå, at heuristik, i modsætning til den korrekte algoritme til løsning af et problem, har følgende funktioner.

Ansøgning

Heuristiske algoritmer bruges i vid udstrækning til at løse problemer med høj beregningskompleksitet , det vil sige i stedet for en komplet opregning af muligheder, hvilket tager betydelig tid, og nogle gange teknisk umuligt, bruges en meget hurtigere, men utilstrækkeligt teoretisk underbygget algoritme. I områder med kunstig intelligens , såsom mønstergenkendelse , er heuristiske algoritmer meget brugt, også på grund af manglen på en generel løsning på problemet. Forskellige heuristiske tilgange bruges i antivirusprogrammer , computerspil osv. Programmer, der spiller skak , spiller for eksempel midt i spillet, hovedsageligt baseret på heuristiske algoritmer ( en database kan bruges i åbningen , Nalimov-tabeller i slutspillet  , men i I mellemspillet , antallet af mulige træk udelukker ofte udtømmende opregning, og nøjagtige algoritmer for korrekt spil eksisterede ikke i lang tid).

Ifølge Judah Perl er heuristiske metoder baseret på den intellektuelle søgen efter strategier til løsning af et problem ved hjælp af flere alternative tilgange [1] .

Muligheden (antageligheden) for at bruge heuristik til at løse hvert specifikt problem bestemmes af forholdet mellem omkostningerne ved at løse problemet med eksakte og heuristiske metoder, omkostningerne ved en fejl og de statistiske parametre for heuristikken. Derudover er tilstedeværelsen eller fraværet af et "sund fornuftsfilter" ved udgangen, det vil sige en persons vurdering af resultatet, vigtig.

Et eksempel på heuristisk beslutningsevaluering

Lad os overveje et spekulativt eksempel. Antag, at der er en velkendt, men ekstremt kompleks, nøjagtig algoritme til at løse problemet, og en heuristik, der kræver 1000 gange mindre indsats og oftest giver en acceptabel løsning (omend i 95% af tilfældene). For nemheds skyld antager vi, at prisen på en nøjagtig løsning er konstant, ligesom prisen på en fejl er.

Så vil den heuristiske løsning i gennemsnit koste , hvor T er prisen på den nøjagtige løsning, og E er prisen på fejlen. Den gennemsnitlige forskel i prisen på løsningen ved de nøjagtige og heuristiske metoder , det vil sige, at heuristikken i gennemsnit viser sig at være mere rentabel end den nøjagtige løsning, medmindre omkostningerne ved fejlen overstiger tyve gange (!) prisen på præcis løsning.

Hvis resultatet af beslutningen ved udgangen vurderes kritisk af en person, så bliver situationen endnu bedre: når fejlen genereret af heuristikken viser sig at være for lille til, at en person kan bemærke det, er prisen for denne fejl er normalt meget lavere, og alvorlige fejl vil blive bortfiltreret af "sund fornuftsfilteret", og vil derfor ikke forårsage væsentlig skade.

Se også

Noter

  1. ↑ Perle, Judæa. Heuristik  (neopr.) . - Addison-Wesley Pub, 1984. - ISBN 0201055945 .

Litteratur