Heuristika (počítačová věda) - Heuristic (computer science)

V matematické optimalizaci a počítačové vědě je heuristika (z řeckého εὑρίσκω „nalézám, objevuji“) technikou určenou k rychlejšímu řešení problému, když jsou klasické metody příliš pomalé, nebo k nalezení přibližného řešení, když se klasickým metodám nepodaří najít žádný přesný řešení. Toho je dosaženo optimálností obchodování, úplností, přesností nebo přesností pro rychlost. Svým způsobem to lze považovat za zkratku.

Heuristická funkce , také jednoduše nazvaný heuristické , je funkce , která se řadí alternativy vyhledávacích algoritmů na každém kroku větvení na základě dostupných informací rozhodnout, která pobočka bude následovat. Může například přibližovat přesné řešení.

Definice a motivace

Cílem heuristiky je vytvořit řešení v rozumném časovém rámci, které je dostatečně dobré pro vyřešení daného problému. Toto řešení nemusí být nejlepší ze všech řešení tohoto problému, nebo se může jednoduše přibližovat přesnému řešení. Ale stále je to cenné, protože jeho nalezení nevyžaduje neúměrně dlouhou dobu.

Heuristiky mohou přinášet výsledky samy, nebo mohou být použity ve spojení s optimalizačními algoritmy ke zlepšení jejich účinnosti (např. Mohou být použity ke generování dobrých hodnot osiva).

Výsledky o tvrdosti NP v teoretické informatice činí z heuristiky jedinou schůdnou možnost pro řadu komplexních problémů s optimalizací, které je třeba rutinně řešit v aplikacích v reálném světě.

Heuristika je základem celé oblasti umělé inteligence a počítačové simulace myšlení, protože mohou být použity v situacích, kdy nejsou známy žádné algoritmy .

Kompromis

Kompromisní kritéria pro rozhodování, zda použít heuristiku k řešení daného problému, zahrnují následující:

  • Optimalita: Pokud pro daný problém existuje několik řešení, zaručuje heuristická záruka, že bude nalezeno nejlepší řešení? Je skutečně nutné najít nejlepší řešení?
  • Úplnost: Pokud pro daný problém existuje několik řešení, dokáže je heuristika najít všechny? Opravdu potřebujeme všechna řešení? Mnoho heuristiky má najít pouze jedno řešení.
  • Přesnost a přesnost: Může heuristika poskytnout interval spolehlivosti pro údajné řešení? Není chybová lišta v řešení nepřiměřeně velká?
  • Doba provedení : Je toto nejznámější heuristika pro řešení tohoto typu problému? Některé heuristiky konvergují rychleji než jiné. Některé heuristiky jsou jen okrajově rychlejší než klasické metody, v takovém případě může mít „režie“ na výpočet heuristiky negativní dopad.

V některých případech může být obtížné rozhodnout, zda je řešení nalezené heuristikou dostatečně dobré, protože teorie, která je základem heuristiky, není příliš propracovaná.

Příklady

Jednodušší problém

Jeden způsob, jak dosáhnout nárůstu výpočetního výkonu očekávaného od heuristiky, spočívá v řešení jednoduššího problému, jehož řešení je také řešením počátečního problému.

Problém obchodního cestujícího

Příklad přiblížení popisuje Jon Bentley pro řešení problému obchodního cestujícího (TSP):

  • „Jaká je nejkratší možná trasa, která vzhledem k seznamu měst a vzdálenosti mezi každým párem měst navštíví každé město a vrátí se do původního města?“

tak, aby se vybralo pořadí kreslení pomocí plotrového pera . Je známo, že TSP je NP-Hard, takže optimální řešení i problému střední velikosti je obtížné vyřešit. Namísto toho může být chamtivý algoritmus použit k poskytnutí dobrého, ale ne optimálního řešení (je to přiblížení k optimální odpovědi) v rozumně krátkém čase. Heuristický chamtivý algoritmus říká, že si vyberete, co je aktuálně nejlepší další krok bez ohledu na to, zda to později brání (nebo dokonce znemožňuje) dobré kroky. Je to heuristika v tom, že praxe říká, že je to dost dobré řešení, teorie říká, že existují lepší řešení (a dokonce může určit, o kolik lepší v některých případech).

Vyhledávání

Jiný příklad heuristické zrychlení algoritmu se vyskytuje u určitých problémů s vyhledáváním. Heuristika zpočátku zkouší každou možnost v každém kroku, jako algoritmus pro hledání v plném prostoru. Hledání ale může kdykoli zastavit, pokud je současná možnost již horší než již nalezené nejlepší řešení. Při takových problémech s hledáním lze nejprve použít heuristiku k vyzkoušení dobrých voleb, aby bylo možné brzy odstranit špatné cesty (viz prořezávání alfa-beta ). V případě vyhledávacích algoritmů best-first , jako je A* search , heuristika zlepšuje konvergenci algoritmu při zachování jeho správnosti, pokud je heuristika přípustná .

Newell a Simon: hypotéza heuristického vyhledávání

Allen Newell a Herbert A. Simon ve svém projevu o přijetí Turingovy ceny diskutují o hypotéze heuristického vyhledávání: systém fyzických symbolů bude opakovaně generovat a upravovat známé struktury symbolů, dokud se vytvořená struktura neshoduje se strukturou řešení. Každý následující krok závisí na kroku před ním, a tak se heuristické vyhledávání dozví, jaké cesty je třeba sledovat a které je třeba ignorovat, a to měřením toho, jak blízko je aktuální krok k řešení. Některé možnosti proto nikdy nebudou generovány, protože jsou měřeny tak, aby bylo méně pravděpodobné, že dokončí řešení.

Heuristická metoda může splnit svůj úkol pomocí vyhledávacích stromů. Místo generování všech možných větví řešení však heuristika vybírá větve, u nichž je větší pravděpodobnost, že přinesou výsledky než jiné větve. Je selektivní v každém rozhodovacím bodě a vybírá pobočky, u nichž je větší pravděpodobnost, že vytvoří řešení.

Antivirový software

Antivirový software často používá heuristická pravidla pro detekci virů a jiných forem malwaru. Heuristické skenování hledá kód a/nebo vzorce chování společné pro třídu nebo rodinu virů s různými sadami pravidel pro různé viry. Pokud se zjistí, že soubor nebo prováděcí proces obsahuje odpovídající vzory kódu a/nebo provádí danou sadu aktivit, pak skener vyvodí, že soubor je infikován. Nejpokročilejší částí heuristického skenování založeného na chování je to, že může fungovat proti vysoce randomizovaným samo-modifikujícím/mutujícím ( polymorfním ) virům, které nelze snadno detekovat jednoduššími metodami skenování řetězců. Heuristické skenování má potenciál detekovat budoucí viry, aniž by bylo nutné virus nejprve detekovat někde jinde, odeslat jej vývojáři antivirového programu, analyzovat jej a aktualizaci detekce skeneru poskytnout uživatelům skeneru.

Úskalí

Některé heuristiky mají silnou základní teorii; jsou buď odvozeny z teorie shora dolů, nebo k nim dochází na základě experimentálních nebo skutečných dat. Ostatní jsou pouhými pravidly založenými na pozorování nebo zkušenostech v reálném světě, aniž by se pohlédli na teorii. Ty jsou vystaveny většímu počtu nástrah.

Když je heuristika znovu použita v různých kontextech, protože bylo vidět, že „funguje“ v jednom kontextu, aniž by bylo matematicky prokázáno, že splňuje daný soubor požadavků, je možné, že aktuální soubor dat nemusí nutně představovat budoucí datové soubory ( viz: přeplnění ) a že údajná „řešení“ se ukázala být podobná hluku.

Statistickou analýzu lze provést při použití heuristiky k odhadu pravděpodobnosti nesprávných výsledků. Chcete -li použít heuristiku k řešení problému s hledáním nebo problému s batohem , je nutné zkontrolovat, zda je heuristika přípustná . Vzhledem k heuristické funkci určené k aproximaci skutečné optimální vzdálenosti k cílovému uzlu v nasměrovaném grafu, který obsahuje celkový počet označených uzlů nebo vrcholů , „přípustný“ znamená zhruba to, že heuristika podceňuje náklady na cíl nebo formálně náklady pro všechny kde .

Pokud není heuristika přípustná, nemusí nikdy najít cíl, a to buď tím, že skončí ve slepé uličce grafu, nebo přeskočí tam a zpět mezi dvěma uzly a kde .

Etymologie

Slovo „heuristické“ se začalo používat na počátku 19. století. Je tvořen nepravidelně z řeckého slova heuriskein , což znamená „najít“.

Viz také

Reference