předchozí - ÚVOD - následující

Heuristiky

 

Heuristiky jsou pravidla "vycucaná z prstu" založená na zkušenosti. Heuristiky (heuristická pravidla) je označení pro znalosti používané v experních systémech. Jde o znalosti založené na zkušenostech experta, na zobecnění situací, ve kterých se expert rozhodoval.

Význam heuristické informace

Metody slepého prohledávání vedou k nalezení optimálního řešení. Při jejich aplikaci nutno generovat neúměrně velký počet uzlů, což vede k vysokým nárokům na čas a paměť využitého počítače. V mnoha úlohách lze zformulovat pravidla, která zmenšují rozsah výběru ve stavovém prostoru. Informaci tohoto druhu nazveme heuristickou informací. Jednou z možností je zavedení "inteligentního operátoru , který bude redukovat počet generovaných uzlů tak, že se omezí pouze na "nejsnadnější" stavy. Druhý způsob používá heuristickou informaci, kdy je vybírán pro expanzi z právě generovaných uzlů vždy ten nejnadějnější. Příslušnou funkci nazveme ohodnocující funkci.

Význam heuristických metod:

  1. určují speciální postupy, jimiž je užitečné se řídit při řešení,

  2. míří k programování úloh, které bude vykonávat počítač (např. klasifikace dat, konstrukce všech možných kombinací apod.),

Heuristické postupy jsou do značné míry ovlivněny subjektem, jsou nepřenosné a proto se setkáváme s pokusy vymezit standardní vlastnosti heuristických postupů [4, 16, 17]:

  1. existuje zásobních různých metod,

  2. existuje zásobník zkušeností se získanými řešeními,

  3. tyto zkušenosti jsou opatřeny příznaky a identifikátory, respektujícími popřípadě i vztahy k zásobníku řešení úloh,

  4. vyskytne se úloha, jejíž řešení není známo ve formě standardního algoritmu

  5. pokus o popsání nové úlohy pomocí příznaků a identifikátorů,

  6. najde se dohodnutá (minimální) míra vhodných příznaků a následně je možno použít pro řešení nové úlohy těch řešení, která byla vybrána.

Jde vlastně o nalezení náhradního řešení v případě, že přímé řešení není známo, ale pravidla pro hledání a nalezení jsou v zásobě řešení (vlastních i převzatých).

Jiné typy heuristik:

  1. výběr po etapách - při konstrukci výběrového stromu se může stát, že paměť počítače je vyčerpána ještě před nalezením řešení. V tom případě je možné ponechat v paměti pouze jistý výsek tohoto grafu, čímž se paměť uvolní pro další hledání řešení úlohy,

  2. ohraničení počtu expandovaných uzlů - je používán "lépe informovaný" operátor , který pro další řešení vybírá pouze nejperspektivnější uzly.

Nejznámější heuristický program  je "Obecný řešitel problémů" (GPS) autorů Newella, Shawa a Simona [17]. Tento program byl zkonstruován původně pro dokazování logických teorémů, ale může se použít i pro řešení jiných úkolů, svou strukturou analogických původním (důkazy geometrických vět, transformace geometrických výrazů, hra v šachy apod.). Pro tyto úlohy není možné sestrojit efektivní algoritmus vedoucí k řešení. Jediný algoritmus, která můžeme zkonstruovat, je algoritmus pokusů o řešení. Ale použití metody postupného vyzkoušení všech variant se ukazuje prakticky nemožné. Proto je nutné zúžit množství prověřovaných variant, tj. aplikujeme speciální pravidla (heuristiky).

Jediný rozdíl mezi heuristickými programy a algoritmy je rozdílnost v rezultativnosti (algoritmus je vždy zaměřen na získání hledaného výsledku, lze ho dosáhnout - ale ne při libovolných výchozích datech). Systém použitých pravidel v heuristických programech není úplný, tj. heuristické programy:

  1. nezaručují vyřešení,

  2. když řešení dosáhneme, je ho dosaženo s menšími ztrátami času a prostředků.

Jsou to vlastně "neúplné" algoritmy.

 

předchozí - ÚVOD - následující