Presná definícia
Čo znamená heuristika?
Heuristika je účelová skratka alebo odhad, ktorý pomocou lacno dostupnej informácie usmerňuje výber možností bez úplného prehľadania. Pri informovanom vyhľadávaní je h(n) odhad najnižších zostávajúcich nákladov z uzla n do cieľa. Prípustná heuristika skutočné minimálne náklady nikdy nenadhodnotí; táto vlastnosť umožňuje A* zachovať optimálnosť za príslušných podmienok. Heuristika zrýchľuje výpočet, no jej kvalita je závislá od úlohy.
Skúsenosť a kontext
Ako sa pojem používa v praxi
Pri plánovaní trasy môže byť heuristikou vzdušná vzdialenosť k cieľu; pri rozvrhovaní počet porušených obmedzení. Dobrá heuristika výrazne zníži počet rozvinutých stavov, ale jej výpočet nesmie stáť viac než ušetrené hľadanie. Návrh často vzniká relaxáciou pôvodnej úlohy a porovnáva sa s nulovou heuristikou podľa času, pamäte a kvality riešenia. Ak sa vyžaduje optimálnosť, testuje sa prípustnosť a konzistentnosť; ak postačí približné riešenie, možno použiť agresívnejší odhad, no treba merať medzeru od optima a zlyhania na protikladoch.
Overiteľnosť
Odborné zdroje
Praktické odpovede
Často kladené otázky
Je heuristika obyčajné pravidlo?
Je to praktické pravidlo alebo funkcia používaná na usmernenie voľby; nemusí poskytovať presný ani optimálny výsledok.
Čo je prípustná heuristika?
Odhad, ktorý nikdy neprekročí skutočné minimálne zostávajúce náklady. Pri A* je kľúčom k záruke optimálnosti.
Čo je konzistentná heuristika?
Spĺňa trojuholníkovú nerovnosť voči nákladom prechodu; pri grafovom A* bráni potrebe opakovane otvárať uzly.
Je nulová heuristika platná?
Áno, pri nezáporných nákladoch je prípustná, ale neposkytuje usmernenie a A* sa správa ako rovnomerné nákladové vyhľadávanie.
Ako sa porovnávajú heuristiky?
Presnosťou odhadu, nákladom výpočtu, počtom rozvinutých uzlov, časom, pamäťou a zachovaním požadovaných záruk.