Heuristický algoritmus

Heuristický algoritmus (heuristický) je algoritmus pro řešení problému, včetně praktické metody, která není zaručeně přesná nebo optimální, ale postačuje k vyřešení problému. Umožňuje urychlit řešení problému v případech, kdy nelze nalézt přesné řešení.

Definice

Heuristický algoritmus je algoritmus pro řešení problému, jehož správnost pro všechny možné případy nebyla prokázána, ale o kterém je známo, že ve většině případů poskytuje poměrně dobré řešení. Ve skutečnosti může být dokonce známo (to znamená dokázáno), že heuristický algoritmus je formálně nesprávný. Může být stále použit, pokud zároveň dává nesprávný výsledek pouze v určitých, spíše vzácných a dobře rozlišených případech, nebo dává nepřesný, ale stále přijatelný výsledek.

Jednoduše řečeno, heuristika je algoritmus, který není zcela matematicky správný (nebo dokonce „ne zcela správný“), ale zároveň je prakticky užitečný algoritmus.

Je důležité pochopit, že heuristika, na rozdíl od správného algoritmu pro řešení problému, má následující vlastnosti.

Aplikace

Heuristické algoritmy jsou široce používány pro řešení problémů s vysokou výpočetní složitostí , to znamená, že místo úplného výčtu možností, který zabere značný čas a někdy je technicky nemožné, se používá mnohem rychlejší, ale nedostatečně teoreticky podložený algoritmus. V oblastech umělé inteligence , jako je rozpoznávání vzorů , jsou heuristické algoritmy široce používány také kvůli nedostatku obecného řešení problému. Různé heuristické přístupy se používají v antivirových programech , počítačových hrách atd. Například programy hrající uprostřed hry šachy, založené hlavně na heuristických algoritmech ( databázi lze použít v úvodu , Nalimovovy tabulky v koncovce  , ale v střední hra , počet možných tahů často vylučuje vyčerpávající výčet a přesné algoritmy pro správnou hru dlouho neexistovaly).

Podle Judaha Perla jsou heuristické metody založeny na intelektuálním hledání strategií řešení problému pomocí několika alternativních přístupů [1] .

Možnost (přípustnost) použití heuristiky pro řešení každého konkrétního problému je dána poměrem nákladů na řešení problému exaktními a heuristickými metodami, nákladů na chybu a statistických parametrů heuristiky. Kromě toho je důležitá přítomnost nebo nepřítomnost „filtru zdravého rozumu“ na výstupu, tedy hodnocení výsledku osobou.

Příklad vyhodnocení heuristického rozhodnutí

Podívejme se na spekulativní příklad. Předpokládejme, že existuje dobře známý, ale extrémně složitý přesný algoritmus pro řešení problému a heuristika, která vyžaduje 1000krát méně úsilí a nejčastěji poskytuje přijatelné řešení (i když v 95 % případů). Pro zjednodušení předpokládáme, že náklady na přesné řešení jsou konstantní, stejně jako náklady na chybu.

Pak bude v průměru heuristické řešení stát , kde T je cena přesného řešení a E je cena chyby. Průměrný rozdíl v nákladech na řešení exaktními a heuristickými metodami , to znamená, že heuristika se v průměru ukazuje jako výnosnější než přesné řešení, pokud náklady na chybu nepřekročí dvacetinásobek (!) ceny přesné řešení.

Pokud na výstupu člověk kriticky zhodnotí výsledek rozhodnutí, pak se situace ještě zlepší: když se chyba vygenerovaná heuristikou ukáže být příliš malá na to, aby si jí člověk všiml, cena této chyby je obvykle mnohem nižší a závažné chyby budou odfiltrovány „filtrem zdravého rozumu“, takže nezpůsobí významnou škodu.

Viz také

Poznámky

  1. ↑ Pearl, Judea. Heuristika  (neopr.) . - Addison-Wesley Pub, 1984. - ISBN 0201055945 .

Literatura