Heuristik (matematik)
Från Rilpedia
 |
En eller flera användare anser att denna text bör infogas i Heuristik. (Diskussion) |
Heuristik används inom datavetenskap och matematik för att beteckna ett sätt att göra smarta gissningar som hjälper till att hitta lösningar till ett problem. Själva heuristiken garanterar inte en korrekt eller optimal lösning men den kan vara ett bra tillägg till en deterministisk algoritm.
Det som kännetecknar en heuristik är dels att det inte finns något bevis för att den fungerar, annars skulle den vara en deterministisk algoritm, men också att det finns en metodik bakom heuristiken som förbättrar chansen att hitta den önskade lösningen. Slumpmässiga gissningar bildar alltså ingen heuristik. För att veta om en viss heuristik hjälper eller stjälper måste man testa den noga. Observera att en heuristik kan fungera olika bra för olika indata.
Det kan finnas flera skäl till att man använder en heuristik istället för en deterministisk algoritm:
- Det finns ingen känd algoritm för att lösa ett specifikt problem, en heuristik är det enda sättet att närma sig en lösning.
- Vissa problem är svåra att lösa effektivt eller snabbt och en heuristik kan ge rimliga lösningar. I dessa fall föredrar man oftast att försöka hitta en lösning som är tillräckligt bra eller en lösning överhuvudtaget framför att hitta den optimala lösningen.
- En bra algoritm kan vara svår att implementera och en heuristik kan ibland godtas för att den är enkel att beskriva i ett programspråk och är beprövad, dvs heuristiken är känd för att ge goda resultat.
Det främsta skälet för att använda en heuristik i kombination med en deterministisk algoritm är att man vill hjälpa algoritmen på traven så att säga. Sofistikerade algoritmer gynnas av en heuristik om den är tillräckligt snabb och enkel i jämförelse med algoritmen. Oftast används heuristiker i sökalgoritmer för att öka chansen att hitta en bra eller optimal lösning snabbt eftersom många problem är NP-fullständiga. Dessa kan bara lösas genom uttömmande sökning vilket tar mycket lång tid redan för ganska små problem.
En heuristik ska inte blandas ihop med begreppet approximationsalgoritm, då man visserligen ger avkall på att beräkna en optimal lösning för ett optimeringsproblem, men har garanterat hur pass bra eller dålig lösningen är.
