Metoda informovaného vyhledávání

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. června 2018; kontroly vyžadují 3 úpravy .

Informované vyhledávání (též heuristické vyhledávání , angl.  informované vyhledávání , heuristické vyhledávání ) je strategie pro hledání řešení ve stavovém prostoru , která využívá znalosti související s konkrétním úkolem. Informované metody obecně poskytují efektivnější vyhledávání než neinformované metody .

Informace o konkrétní úloze jsou formulovány jako heuristická funkce . Heuristická funkce v každém kroku vyhledávání vyhodnocuje alternativy na základě doplňujících informací, aby se rozhodla, kterým směrem pokračovat v hledání [1] .

Heuristické funkce

V kontextu prohledávání stavového prostoru je heuristická funkce h ( n ) definována na uzlech iteračního stromu takto:  

h ( n ) = odhad nákladů na nejlevnější cestu z uzlu n do cílového uzlu.

Pokud n  je cílový uzel, pak h ( n ) = 0.

Uzel , který má být nasazen, je vybrán na základě vyhodnocovací funkce 

f ( n ) = odhad nákladů na cestu nejlevnějšího řešení procházející uzlem n , f ( n ) = g ( n ) + h ( n ),

kde funkce g ( n ) určuje cenu již projeté cesty z počátečního uzlu do uzlu n .

Pokud heuristická funkce h ( n ) nikdy nepřeceňuje skutečné minimální náklady na dosažení cíle (tedy jde o nižší odhad skutečných nákladů), pak se taková funkce nazývá přípustná . 

Pokud heuristická funkce h ( n ) splňuje podmínku

h ( a ) ≤ náklady ( a , b ) + h ( b ) ,

kde b  je potomkem a , pak se taková funkce nazývá postupná ( anglicky  konzistentní ).

Jestliže f ( n ) = g ( n ) + h ( n ) je vyhodnocovací funkce, h ( n ) je následnická funkce, pak je funkce f ( n ) monotónně neklesající podél jakékoli studované cesty. Postupné funkce se proto také nazývají monotónní ( angl.  monotónní ).

Jakákoli následnická funkce je přípustná, ale ne každá přípustná funkce je následnicí.

Jestliže h 1 ( n ), h 2 ( n ) jsou platné heuristické funkce a pro jakýkoli uzel n platí nerovnost h 1 ( n ) ≥ h 2 ( n ), pak h 1 je informovanější heuristika nebo dominuje h 2 .

Pokud má problém přípustné heuristiky h 1 a h 2 , pak je heuristika h ( n ) = max ( h 1 , h 2 ) přípustná a dominuje nad každou z původních heuristik [1] [2] .

Porovnání heuristických funkcí

Při porovnávání přípustných heuristik záleží na stupni informovanosti a na prostorové a časové složitosti výpočtu každé z heuristiky. Informovanější heuristika může snížit počet nasazených uzlů, i když náklady na to může být čas, který zabere výpočet heuristiky pro každý uzel.

Faktor efektivního větvení je průměrný počet  následníků uzlů ve výčtovém stromě po aplikaci heuristických metod ořezávání [1] [2] . Podle efektivního faktoru větvení lze posuzovat kvalitu použité heuristické funkce.

Ideální heuristická funkce (jako je vyhledávací tabulka ) vždy vrací přesné hodnoty pro délku nejkratšího řešení, takže výčtový strom obsahuje pouze optimální řešení. Efektivní faktor větvení ideální heuristické funkce se blíží 1 [1] .

Příklady vyhledávacích úloh

Jako modely pro testování vyhledávacích algoritmů a heuristických funkcí se často používají permutační hádanky  - Fifteen 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [ 10 ] , 6×6 [11] , Rubikova kostka [9] [12] , Hanojská věž se čtyřmi tyčemi [11] [13] .

V hádance "Patnáct" lze použít heuristiku h m založenou na vzdálenosti Manhattanu . Přesněji řečeno, pro každou destičku se vypočítá vzdálenost na Manhattanu mezi její aktuální a počáteční pozicí; získané hodnoty jsou shrnuty.

Lze ukázat, že tato heuristika je přípustná a postupná: její hodnota se nemůže během jednoho tahu změnit o více než ±1.

Konstrukce heuristických funkcí

Uvolněný úkol

Heuristická funkce h m použitá k řešení hádanky "Patnáctka" je nižší odhad délky optimálního řešení. Navíc h m ( n ) je přesná délka optimálního řešení zjednodušené verze hádanky, ve které lze dlaždice posouvat na své pozice. V původní hádance je omezení "v jedné buňce by neměly být dvě nebo více dlaždic", které ve zjednodušené verzi není. Problém s menším počtem omezení možných akcí se nazývá uvolněný problém ; cena řešení uvolněného problému je platnou heuristikou pro původní problém [1] , protože jakékoli řešení původního problému je také řešením uvolněného problému.  

Dílčí úkol

Přípustná heuristika může být založena na nákladech na řešení dílčího problému původního problému . Jakékoli řešení hlavního problému je současně řešením každého jeho dílčího úkolu [1] .  

Dílčím úkolem problému řešení hádanky "Patnáctka" může být úkol přesunout na svá místa dlaždice 1, 2, 3 a 4. Náklady na vyřešení tohoto dílčího problému jsou platnou heuristiky pro původní problém.

Databáze šablon

Databáze vzorů [ 1] jsou typem  platné heuristiky založené na myšlence ukládat přesnou hodnotu nákladů na řešení pro každou možnou instanci dílčího problému [1] [6] [12] .

Příklad šablony pro hádanku "Patnáctka" je na obrázku vpravo: definice dílčího úkolu zahrnuje pozice sedmi žetonů umístěných v prvním sloupci a v prvním řádku. Počet konfigurací pro tuto šablonu je . Pro každou z konfigurací obsahuje databáze minimální počet pohybů potřebných k převedení této konfigurace do cílové konfigurace dílčího úkolu zobrazeného na obrázku. Databáze je sestavena pomocí metody obráceného vyhledávání do šířky [2] [6] .

Vyhledávací algoritmy

Hledat podle první nejlepší shody

Hledání typu Best -first je přístup, ve kterém se uzel k nasazení vybírá na základě vyhodnocovací funkce f ( n ) .  K nasazení je vybrán uzel s nejnižším skóre.

Hledat A*

Vyhledávání A*  je nejznámějším typem vyhledávání první nejlepší shody. Používá odhad f ( n ) nákladů na cestu nejlevnějšího řešení přes uzel n :

f ( n ) = g ( n ) + h ( n ), kde g ( n ) je cena cesty od počátečního uzlu k uzlu n , h ( n ) je odhad nákladů na cestu od uzlu n k cíli.

Pokud h ( n ) nikdy nepřeceňuje náklady na dosažení cíle (tedy je cenově dostupné), pak je hledání A* optimální.

IDA*

Algoritmus A* s iterativním prohlubováním A* ( IDA* ) je aplikací myšlenky iterativního prohlubování v kontextu heuristického vyhledávání.

Neinformovaný iterativní prohlubovací algoritmus zastaví expanzi, když hloubka hledání d překročí aktuální hloubkový limit l . Informovaný algoritmus IDA* zastaví nasazení, když odhad f ( n ) nákladů na cestu přes aktuální uzel n překročí limit nákladů na aktuální cestu .

Algoritmus IDA* se vyznačuje minimální pamětí ve srovnání s A* a relativně malým (v případě úspěšné volby heuristiky) počtem nasazených uzlů ve srovnání s IDDFS.

Pseudokód

[čtrnáct]

uzel aktuální uzel g náklady na spuštění řešení kořen..uzel f odhad minimálních nákladů cesty prostřednictvím uzlu h ( uzel ) heuristický odhad nákladů pro zbytek cesty uzel.. náklady cíle ( uzel , succ ) funkce nákladů na cestu is_goal ( uzel ) cíl kontrola následníků funkce ( node ) funkce nasazení uzlu procedura ida_star ( root , cena (), is_goal (), h ()) bound  := h ( root ) loop t  := search ( root , 0, bound ) if t = FOUND pak return FOUND if t = ∞ then return NOT_FOUND bound  := t end loop end procedura funkce hledání ( uzel , g , vázaná ) f  := g + h ( uzel ) pokud f > vázaná tak vrať f if je_cíl ( uzel ) pak vrať FOUND min  := ∞ pro succ v následnících ( uzel ) do t  := hledat ( succ , g + cena ( node , succ ), bound ) if t = FOUND pak return FOUND if t < min then min  := t end for return min end funkce

MA*

SMA*

SMA  *

RBFS

Viz také

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 Stuart Russell, Peter Norvig. Kompilace přípustných heuristických funkcí // Umělá inteligence: moderní přístup = Artificial Intelligence: A Modern Approach. - 2. vyd. - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .
  2. ↑ 1 2 3 Stefan Edelkamp, ​​​​Stefan Schrödl. Heuristické vyhledávání: teorie a aplikace. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
  3. ↑ Alexander Reinfeld. Kompletní řešení Osmi-puzzle a výhoda řazení uzlů v IDA*. — 1993.
  4. ↑ Daniel R. Kunkle. Řešení 8 hádanek v minimálním počtu tahů: Aplikace algoritmu A*. — 2001.
  5. ↑ Richard E. Korf. Iterativní prohloubení do hloubky: Optimální přípustné stromové vyhledávání. — 1985.
  6. ↑ 1 2 3 4 Joseph C. Culberson, Jonathan Schaeffer. Databáze vzorů. — 1998.
  7. ↑ Richard E. Korf, Peter Schultze. Paralelní vyhledávání ve velkém měřítku. — 2005.
  8. ↑ Richard E. Korf, Larry A. Taylor. Hledání optimálních řešení hádanky 24 . — 1996.
  9. ↑ 1 2 Richard E. Korf. Nedávný pokrok v návrhu a analýze přípustných heuristických funkcí. — 2000.
  10. ↑ Richard E. Korf, Ariel Felner. Heuristika databáze nesouvislých vzorů . — 2002.
  11. ↑ 1 2 Ariel Felner, Richard E. Korf, Sarit Hanan. Heuristika databáze aditivních vzorů . — 2004.
  12. ↑ 1 2 Richard E. Korf. Hledání optimálních řešení pro Rubikovu kostku pomocí databází vzorů. — 1997.
  13. ↑ Richard E. Korf, Ariel Felner. Nedávný pokrok v heuristickém vyhledávání: Případová studie problému čtyřkolíkových věží v Hanoji. — 2007.
  14. ↑ Na základě poznámek z přednášky: IDA* Archivováno 22. června 2012 na Wayback Machine

Literatura

  • Stefan Edelkamp, ​​Stefan Schrödl. Heuristické vyhledávání: teorie a aplikace. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
  • Stuart Russell, Peter Norvig. Kompilace přípustných heuristických funkcí // Umělá inteligence: moderní přístup = Artificial Intelligence: A Modern Approach. - 2. vyd. - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .

Odkazy

 Algoritmy pro vyhledávání grafů
Neinformované metody
Informované metody
Zkratky
Minimální kostra
jiný