Metody informovaného hledání Podstatou metod informovaného vyhledávání je snaha zabránit hledacím algoritmům, aby zabloudily. Neinformované hledání, diskutované dříve, je schopno najít řešení problémů systematickým generováním nových stavů a testováním, zda splňují cílové podmínky. Potíž je v tom, že ve většině případů jsou vysoce neefektivní (čas, prostor, optimalita, ...). Informované hledaníje založeno na strategii, která využívá znalost specifickou pro daný problém, a nalezení cíle je mnohem efektivnější, včetně lepší možnosti dosáhnout optimálního řešení. Hledání prvního nejlepšího Doposud bylo obecně možné, po formulaci problému v termínech stavů a operátorů, nějakým způsobem určitou znalost aplikovat pro hledání cíle. Avšak pokud je problém tzv. dobře definovaný, volby jsou omezené. Např. při použití algoritmu General-Search se dá znalost použít na jediném místě—ve funkci zařazování do fronty, kde se určuje, který uzel má být expandován jako příští. Obvykle se znalost toho, jak určit uzel, stanovuje vyhodnocovací funkcí (evaluation function), která vrací číslo určující míru (nebo nedostatek) potřeby expandovat uzel. Pokud jsou uzly uspořádány tak, že ty s nejlepším ohodnocením jsou expandovány jako první, nazývá se tato strategie jako hledání prvního nejlepšího (best-first search). Ilustrace možné implementace této funkce je na následujícím obrázku. -59- function Best-First-Search(problem, Eval-Fn) returns sekvence řešeni inputs: problem II problém Eval-Fn II vyhodnocovaci funkce Queulng-Fn <— funkce seřazujici uzly pomoci Eval-Fn return General-Search (problem, Queulng-Fn) Pozn.: Název "vyhledej první nejlepší" ve skutečnosti znamená jen to, že získáme uzel, ketrý se zdá být nejlepším (jinak by cesta k řešení byla snadná přímočará, což obecně neexistuje). Vzhledem k tomu, že funkce hledání nejlepšího uzlu není vševědoucí, může být hledání samozřejmě svedeno z cesty. Správný název by tedy měl být spíše hledaní zdánlivě prvního nejlepšího. Obdobně, jako existuje skupina algoritmů General-Search pro různé funkce zařazování do fronty, je k dispozici skupina Best-First-Search algoritmů s různými vyhodnocovacími funkcemi. Tyto Best-First-Search algoritmy se snaží najít nenákladná řešení, typicky používají nějakou odhadovací míru pro cenu řešení a snaží seji minimalizovat. Jednou z již ukázaných možností byla cena cesty g k rozhodnutí, kterou cestu prodloužit (viz předchozí diskuse k tzv. dobře definovaným problémům a řešením). Míra g však přímo nesměřuje k cíli. Aby bylo hledání přímo zaměřeno na cíl, musí použitá míra v sobě zahrnovat nějaký odhad ceny cesty z nějakého stavu do nejbližšího cílového stavu. Lze použít nejméně dva základní přístupy k uvedenému řešení: pokus expandovat uzel nejbližší k cíli a pokus expandovat uzel na nejlevnější cestě k řešení. -60- Lačné vyhledávání minimalizující odhadovanou cenu dosažení cíle Jednou z nejjednodušších strategií hledání prvního nejlepšího je minimalizace odhadované ceny dosažení cíle. Znamená to, že vždy je prvně expandován uzel, který se zdá být nejblíže cíli. Pro většinu (reálných) problémů lze náklady na dosažení cíle z nějakého okamžitého stavu jen odhadnout, nikoliv určit přesně. Funkce, která počítá takové odhady nákladů, se nazývá heuristická funkce, obyčejně označovaná jako h: h(n) = odhadnutá cena nejlevnější cesty ze stavu v uzlu n do stavu cílového. Hledání prvního nejlepšího, které používá h k výběru dalšího expandovaného uzlu, se nazývá lačné hledání (greedy search). Symbolický kód pro lačné hledání s danou funkcí h: function Greedy-Search{problem) returns řešeni nebo neúspěch return Best-First-Search (problem, h) Formálně vzato, h může být jakoukoliv funkcí. Jediným požadavkem je, aby h(n) = 0 jestliže n je cíl. Heuristické funkce jsou vždy specifické pro daný problém, tj. aplikačně závislé. Pro příklad uvažme opět cestování z města Arad do Bucharest. Mapka je stejná jako dříve, avšak přídavná informace je zde k dispozici ve formě kilometrové vzdálenosti tras mezi jednotlivými městy. Pro obdobné problémy je dobrou heuristickou funkcí přímočará vzdálenost v řadě k cíli, neboli SLD (Straight-Line Distance): hSLD(n) = přímočará řadová vzdálenost mezi n a cílovým místem. -61- Arad Dobreta Giurgiu Eforie Straight-line distance to Bucharest Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 98 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 hSLD lze zde spočítat jen tehdy, jsou-li známy souřadnice měst v Rumunsku. Kromě toho zde platí, že cesta z A do B je převážně vždy správným směrem, takže tento druh přídavné informace umožňuje heuristice pomoci v redukci ceny vyhledávání. Další obrázek ukazuje pokrok lačného vyhledávání při hledání cesty z Aradu do Bucharesti: Arad ^ h=366 Sibiu (j Timisoara U X) Zerind b=253 b=329 h=374 Aradri Sibju^Q^' Timisoara O ^Q Zerind ^^^/ \^^~~~^ h=329 h=374 Arad (JT Fagaras U Oradea (J Rimnicu^ h=366 h=178 h=380 h=193 Arad, Sibiy^QCT Timisoara 0 X) Zerind ^yS \^^^^ h=329 h=374 Arad 9f Fagaras! K. Oradea O RimnicuO h=366 / ^\ h=380 h=193 Sibiu O Bucharest O h=253 h=0 -62- Pomocí heuristiky SLD se expanduje jako první uzel z Aradu do Sibiu, protože je bližší (dle přídavné informace) Bucharesti než Zerind nebo Timisoara (viz vzdálenosti různých měst od Bucharesti). Dalším uzlem je ze stejného důvodu Fagaras, a odtud už to je přímo do Bucharesti (taje cílem, protože její vzdálenost od sebe sama je nula). V tomto příkladě funguje heuristika skvěle, protože našla řešení bez expanse uzlů, které nejsou na cestě. Je však cesta optimální? Optimální není, protože nalezená cesta je o 32 km delší než cesta přes Rimnicu Vilcea a Pitesti. Optimální cesta nebyla heuristikou nalezena, protože Faragas je Buchuresti blíže z hlediska SLD než Rimnicu Vilcea, proto cesta přes Faragas byla expandována jako první. Ukázaná heuristická strategie preferuje největší nalezený kus cesty k cíli vzhledem k tomu, že tento velký kus odebere největší část ze zbývající cesty do cíle (Fagaras-Bucharest = 211 km, Rimnicu Vilcea-Pitesti-Bucharest = 97+101 km, a 97 odebere méně ze zbytku než 211), aniž by se starala o to, zda je to nejlepší vzhledem k délce cesty—proto je název hledání "lačné, hltavé" (greedy). Přesto praxe ukazuje, že lačnost přináší velmi dobré výsledky (i když se jedná ojeden ze sedmi smrtelných hříchů). Lačnost přináší jako positivům rychlé nalezení cíle, i když ne vždy optimální. Optimalita by vyžadovala důkladnější analýzu z hlediska uvažování o celé dlouhé vzdálenosti, nikoliv pouze bezprostřední nejlepší výběr. Lačné hledání je citlivé na chybný počátek. Uvažme problém cesty z Iasi do Fagarasu: heuristika nabízí první expansi uzlu Neamt, což je ovšem slepá ulička. Řešením je expanze Vaslui, což je ale z hlediska heuristiky do cíle dále. Z Vaslui pak do Urziceni, Bucharesti a Fagarasu, což z hlediska heuristiky jsou zbytečné expanse uzlů, pokud je okamžitý stav v Neamtu. Navíc, při zanedbání opatrnosti vzhledem k detekci opakovaných stavů, může dojít k nekonečným oscilacím mezi Neamtem a Iasi. Lačné hledání připomíná hledání prvně do hloubky v tom, že preferuje jednu cestu do cíle, ale při objevení slepé uličky se vrací zpět. Rovněž má stejné neduhy: není optimální a není kompletní (může se vydat na nekonečnou cestu a nikdy se nevrátit k vyzkoušení odlišné možnosti). Nejhorší časová složitost je 0(bm), kde m je max. hloubka hledání. Stejná je i prostorová složitost (uzly jsou uchovávány v paměti). Podstatná redukce složitosti vyžaduje kvalitní heuristiku h a také závisí na konkrétním problému. -63- Minimalizace celkové ceny cesty: hledání A* Lačné hledání h(n) má uvedené přednosti a nedostatky. Uniformně-cenové hledání g(n) minimalizuje cenu cesty do daného okamžiku; je optimální a kompletní, ale může být velmi neefektivní. Kombinací výhod obou strategií lze získat alternativní funkci, přičemž postačuje prostě jejich hodnoty sečíst: f(n)=g(n)+h(n). Protože g(n) dává cenu cesty od startu do n a h(n) odhaduje cenu nejlevnější cesty z n do cíle, pak platí f(n) = odhadnutá cena nejlevnějšího řešení přes n. Při hledání nejlevnějšího řešení je tedy rozumné prvně zkusit uzel s nejmenší hodnotou/ Existuje dokonce důkaz, že tato strategie je kompletní a optimální za předpokladu určitého omezení pro h: Omezením je výběr funkce h takové, která nikdy nepřecení cenu dosažení cíle. Taková funkce h se nazývá přijatelná heuristika. Přijatelné heuristiky jsou v principu optimistické, protože předpokládají, že cena řešení problému je menší než je ve skutečnosti. Tento předpoklad se přenáší do funkce/ Je-li h přijatelná, pakf(n) nikdy nepřecení skutečnou cestu nejlepšího řešení přes n (při přecenění ceny by pak cesta nebyla vybrána, i když je správným řešením). Hledání prvního nejlepšího s použitím/j ako vyhodnocovací funkce a h jako přijatelné funkce se nazývá hledání A*. Symbolický zápis funkce: function A*-Search(problem) returns řešeni nebo neúspěch return Best-First-Search (problem, g+h) Příkladem přijatelné heuristiky je výše uvedená hSLD (nejkratší cesta mezi dvěma body je přímá cesta—úsečka). -64- Obrázek ukazuje několik prvních kroků hledání A* při použití heuristiky hSLD. Za povšimnutí stojí, že A* preferuje expansi z Rimnicu Vilcea před expansí z Fagarasu. Přestože Fagaras je blíže Bucharesti, cesta do Fagarasu není tak efektivní v přiblížení se Bucharesti jako cesta do Rimnicu Vilcea (uzly mají označení/ = g+h, přičemž hodnoty h jsou SLD vzdálenosti do Bucharesti z dříve uvedeného obrázku): Sibiu Qf Timisoara O \JZerind 1=140+253 f=118+329 f=75+374 Aradj =393 Zerínd Arad W Fagaras U Oradea U Rimnicu f=280+366 f=239+178 f=146+380 f=220+193 =646 =417 =526 =413 Arad Zerind Fagaras ( (=280+366 r=239+178 1=146+380 =646 =417 =526 Craiova f=366+160 =526 Pitesti ř=317+98 =415 • Sibiu f=300+253 =553 r r L * Vlastnosti hledání A Obrázek hledání pomocí A* demonstruje jednu základní věc: podél libovolné cesty z kořene, /cena nikdy neklesá. To není náhodou a heuristiky, které tuto vlastnost nenarušují, se nazývají monotónní (v r. 1984 bylo dokázáno, že heuristika je monotónní tehdy a jen tehdy, pokud splňuje pravidlo tzv. trojúhelníkové nerovnosti—přímočaré vzdálenosti tuto podmínku samozřejmě splňují, takže SLD je monotónní). -65- Pokud by heuristika nebyla monotónní, lze ji upravit na monotónnost: Uvažujme dva uzly nan', kde n je rodičovský uzel n'. Dále nechť např. g(n) = 3 a h(n) = 4, takže f(n) = g(n)+h(n) = 7. Víme tedy, že skutečná cena cesty k řešení je nejméně 7. Předpokládejme ještě, že g(rí) = 4 a h(rí) = 2, takže f(n') = g(n')+h(n') = 6. Z uvedeného je zřejmé, že se jedná o nemono-tónní heuristiku h. Je ale zřejmé, že libovolná cesta přes rí je také cestou přes n, tedy hodnota 6 je bezvýznamná, neboť již víme, že skutečná cena musí být nejméně 7. Musíme tedy kontrolovat při generování nového uzlu, zda jeho/ cena je menší než/cena jeho rodiče; pokud je cena u potomka menší, použije se prostě cena rodiče: f(n')=max[f(n),g(n')+h(n')J. Takto se ignorují hodnoty, které se mohou vyskytnout s nemonotónními heuristikami a uvedený stav se nazývá rovnice max-cesty (pathmax equation). Pokud vztah max-cesty použijeme, pak/bude vždy neklesající podél každé cesty z kořene, za předpokladu přijatelnosti h. Z toho vyplývá další vlastnost A*, tj. pokud/nikdy cestou z kořene neklesá, lze ve stavovém prostoru vytvořit tzv. obrysy: -66- Na mapce (stavovém prostoru) jsou obrysy pro/= 380, /=400 a /= 420, kde Arad je počáteční stav. Uzly uvnitř daného obrysu mají/ceny nižší než je hodnota daného obrysu. A* expanduje uzly s nejnižší/ tedy hledání postupuje koncentricky v pásmech podle narůstání/ Při hledání s uniformní cenou (A*-hledání za použití h = 0) jsou pásma "cirkulární" kolem počátečního stavu. Se vzrůstající přesností heuristiky se pásma začínají protahovat směrem k cílovému stavu a zužují se kolem optimální cesty. Nechť/* je cena optimální cesty k řešení. Pak lze o A* říci následující: • A* expanduje všechny uzly, pro něž platí f(n) /*. Uvažujme situaci, kdy A* vybral G2 z fronty. Protože G2 je cílovým stavem, ukončí hledání se suboptimálním řešením (viz obrázek—uzel n je uzel na cestě k optimálnímu reseni G). Start n gO G Ukážeme, že k uvedenému závěru—suboptimálnímu výběru—nemůže dojít. Předpokládejme, že uzel n je v daném okamžiku listem na optimální cestě do G (nějaký takový uzel musí existovat, ledaže by již cesta byla zcela expandována—zde by ovšem bylo vráceno G). Protože /zje přijatelná heuristika, pak: f">-f(n). Dále, pokud n není vybrán pro expansi přes G2, platí: Z toho plyne: r>-f(G,j. -68- Protože G2 je cílovým stavem, platí: hfG^) = 0, z čehož zjevně plyne/(GJ = g(GJ. Tím bylo s použitím předpokladů dokázáno, že /* >- g(GJ. To je ale v rozporu s předpokladem, že G2 je suboptimální, takže A* nikdy nevybere pro expansi suboptimální cíl. Protože vrací jedině řešení vybrané pro expansi, musí A* být optimálním algoritmem. D Důkaz úplnosti A* A* expanduje uzly v pořadí vzrůstající/, takže nakonec musí dojít k expansi k dosažení cílového stavu. To platí s výjimkou případu, kdy je nekonečně mnoho uzlů sf(n) hj(n), pak odpověď zní ano, tedy h2 dominuje hj. Dominace je převedena do efektivnosti přímočaře, protože A* s h2 expanduje průměrně méně uzlů než s hj. Např. pro již uvedený problém: AradQ f=0+366 Arad =366 Sibiu j=14(h-253 =393 Zerind J=75+374 =449 Arad CT Fagarasö Oradea O Rimnicu f=28 Zerind Arad f=28(h-366 =646 Sibiu f=366+160 J=317+98 f=300+253 =526 =415 =553 Bylo již dříve uvedeno, že expandovány budou uzly, pro něž platí f(n)