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é hledání 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šení

inputs: problem // problém

Eval-Fn // vyhodnocovací funkce

Queuing-Fn w funkce seøazující uzly pomocí Eval-Fn return General-Search(problem, Queuing-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 hledání 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ží se ji 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šení 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-

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:

-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 (ta je cílem, protože její vzdále- nost 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á o jeden ze sedmi smrtelných høíchù). Laènost pøináší jako positivum 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 O(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 f. 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 f:

Je-li h pøijatelná, pak f(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 f jako vyhodnocovací funkce a h jako pøijatelné funkce se nazývá hledání A*. Symbolický zápis funkce:

function A*-Search(problem) returns øešení 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í f = g+h, pøièemž hodnoty h jsou SLD vzdálenosti do Bucharesti z døíve uvedeného obrázku):

Vlastnosti hledání A*

Obrázek hledání pomocí A* demonstruje jednu základní vìc: podél libovolné cesty z koøene, f-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 n a n', 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(n') = 4 a h(n') = 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 n' 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 f- cena je menší než f-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')].

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 f 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 f nikdy cestou z koøene neklesá, lze ve stavovém prostoru vytvoøit tzv. obrysy:

-66-

Na mapce (stavovém prostoru) jsou obrysy pro f = 380, f =400 a f = 420, kde

Arad je poèáteèní stav. Uzly uvnitø daného obrysu mají f-ceny nižší než je hodnota daného obrysu.

A* expanduje uzly s nejnižší f, tedy hledání postupuje koncentricky v pásmech podle narùstání f.

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• f * 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) < f *.

!A* mùže dále expandovat nìkteré uzly pøímo na “cílovém obrysu”, kde platí f(n) = f *, pøed výbìrem cílového uzlu.

Intuitivnì je zøejmé, že první øešení musí být optimální, protože uzly ve všech následujících obrysech mají vyšší f-cenu a tudíž vyšší g-cenu (dùvodem je, že všechny cílové stavy mají h(n) = 0, takže zdražení zpùsobí g).

Dále je intuitivnì zøejmé, že A*-hledání je kompletní. Pøidáváním pásem s rostoucími hodnotami f se nakonec dostaneme do pásma, kde f je rovno cenì cesty do cílového stavu.

Kromì uvedeného stojí za zmínku, že mezi optimálními algoritmy tohoto typu—tj. algoritmy, které prodlužují vyhledávací cesty z koøene—je A* optimálnì úèinný pro jakoukoliv danou heuristickou funkci:

Libovolný algoritmus, který neexpanduje všechny uzly v pásmech mezi koøenovým a cílovým pásmem, musí poèítat s rizikem opominutí optimálního øešení (rozsáhlý dùkaz byl podán v r. 1985).

-67-

Dùkaz optimality A*

Nech• G je optimální cílový stav s cenou cesty f *. Nech• G2 je suboptimální cílové øešení, tj. cílový stav s cenou cesty g(G2) > f *. 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 øešení 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 expando- vána—zde by ovšem bylo vráceno G). Protože h je pøijatelná heuristika, pak:

f * $ f(n).

Dále, pokud n není vybrán pro expansi pøes G2, platí:

f(n) $ f(G2).

Z toho plyne:

f * $ f(G2).

-68-

Protože G2 je cílovým stavem, platí:

h(G2) = 0, z èehož zjevnì plyne f(G2) = g(G2).

Tím bylo s použitím pøedpokladù dokázáno, že

f * $ g(G2).

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ùkaz úplnosti A*

A* expanduje uzly v poøadí vzrùstající f, 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ù s f(n) < f *. Dùvod k existenci nekoneèného poètu uzlù je buï: a) existuje uzel s nekoneènì velkým poètem vìtvení, nebo b) existuje cesta s koneènou cenou, ale s nekoneèným poètem uzlù podél ní (starý paradox typu “zajíc nikdy nedožene želvu”). Z toho plyne, že A* je kompletní v lokálnì koneèných grafech (tj. grafech s koneèným faktorem vìtvení) za pøedpokladu, že existuje nìjaká kladná konstanta * taková, že každý operátor stojí nejménì *.

Složitost A*

Z hlediska kompletnosti, optimálnosti a optimální efektivnosti A* není odpovì- dí na všechny požadavky hledání—pro vìtšinu problémù je totiž poèet cílových uzlù uvnitø obrysu, vymezujícího cílový prostor vyhledávání, stále exponenciální vzhledem k délce øešení. Komplikovaný dùkaz byl však vytvoøen pro to, že exponenciální nárùst se objevuje, pokud ovšem chyba heuristické funkce neroste rychleji než logaritmus skuteèné ceny cesty. Podmínka pro sub-exponenciální nárùst je:

*h(n) ! h*(n)* # O(log h*(n)),

kde h*(n) je skuteèná cena cesty z n do cíle. Pozn.: pro A* není rozhodující èas, nýbrž pamì•, protože udržuje v pamìti všechny generované uzly.

-69-

Heuristické funkce

Hlavolam s posouváním osmi ètvereèkù v devíti polích patøí k nejstarším problémùm s heuristickým vyhledáváním:

Typické øešení má zhruba 20 krokù (závisí to na poèáteèním stavu). Faktor vìtvení je cca 3 (je-li prázdné pole uprostøed, pak b = 4; v rohu je b = 2; podél hran je b = 3). Prohledávání vyèerpávající všechny možnosti do hloubky 20 zkoumá pøibližnì 320 = 3.5×109 stavù.

Pokud by se dùslednì testovaly stavy opakování, lze redukovat poèet stavù radikálnì, nebo• existuje pouze 9! = 362 880 rùzných rozmístìní pro 9 polí. To je stále velmi mnoho, proto je vhodné najít dobrou heuristiku. Pokud je cílem nalezení nejkratšího øešení, je zapotøebí mít heuristickou funkci, která nikdy nepøecení poèet krokù do cíle. Dvì možnosti:

!h1 = poèet ètvereèkù na chybných pozicích. Na obrázku je umístìno 7 z 8 chybnì, takže poèáteèní stav má h1 = 7; je to pøijatelná heuristika, protože každý chybnì umístìný ètvereèek musí být alespoò jednou posunut.

-70-

!h2 = souèet vzdáleností ètvereèkù od jejich koncových pozicí. Ètvereèky se nemohou pohybovat diagonálnì, takže se seètou vzdálenosti vertikální a horizontální (tento typ výpoètu vzdáleností je znám jako vzdálenost mìstských blokù nebo manhattanská

vzdálenost). h2 je rovnìž pøijatelná, protože jakýkoliv posun pohne pouze jedním ètvereèkem o jeden krok smìrem k cíli. Ètvereèky 1 až 8 z poèáteèního stavu na obrázku mají celkovou délku manhattanské cesty h2 = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18.

Vliv pøesnosti heuristiky na efektivitu

Jednou možností pro stanovení kvality heuristiky je efektivní faktor vìtvení, oznaèovaný b*. Je-li N celkový poèet uzlù expandovaných pomocí A* a hloubka øešení je d, pak b* je faktor vìtvení, který by mìl rovnomìrnì vyvážený strom hloubky d, aby obsahoval N uzlù:

N = 1 + b* + (b*)2 + . . . + (b*)d.

Napø. když A* najde øešení v hloubce 5 za použití 52 uzlù, pak b* = 1.91. Dobrá heuristika by se mìla blížit b* = 1. Pro 100 náhodnì vygenerovaných pozic hlavolamu s 8 ètvereèky (a za použití iterativního hloubkového hledání

Iterative-Deepening-Search IDS s A*, h1 a h2) lze získat srovnání pro prùmìrné hodnoty poètu expandovaných uzlù:

d		cena hledání			efektivní faktor vìtvení
	ID S		A* (h1)	A*(h2)	ID S	A* (h1)	A*(h2)
2	10		6	6	2.45	1.79	1.79
4	112		13	12	2.87	1.48	1.45
6	680		20	18	2.73	1.34	1.30
8	6384		39	25	2.80	1.33	1.24
10	47127		93	39	2.79	1.38	1.22
12	364404		227	73	2.78	1.42	1.24
14	3473941		539	113	2.83	1.44	1.23
16	—		1301	211	—	1.45	1.25
18	—		3056	363	—	1.46	1.26
20	—		7276	676	—	1.47	1.27
22	—		18094	1219	—	1.48	1.28
24	—		39135	1641	—	1.48	1.26

-71-

Otázkou mùže být, zda h2 je vždy lepší než h1. Protože z definic obou heuristik platí pro libovolný uzel, že h2(n) $ h1(n), pak odpovìï zní ano, tedy h2 dominuje h1. Dominace je pøevedena do efektivnosti pøímoèaøe, protože A* s h2 expanduje prùmìrnì ménì uzlù než s h1. Napø. pro již uvedený problém:

Bylo již døíve uvedeno, že expandovány budou uzly, pro nìž platí f(n) < f *. To je totéž jako tvrzení, že budou expandovány uzly s h(n) < f * - g(n) vzhledem k definici f(n). Protože h2 je pøinejmenším tak velká jako h1 pro všechny uzly, pak každý uzel expandovaný pomocí hledání A* s h2 bude rovnìž expandován s h1 a h1 mùže ještì zpùsobit expanzi jiných uzlù. Z toho plyne urèitý závìr èi doporuèení: Je lépe použít heuristiku s vyššími hodnotami, nebo• nedojde k pøecenìní (koneèný výsledek jednoduše mùže být takový nebo lepší).

Hledání vhodné heuristiky vyžaduje velmi èasto experimentování, napø. náhodné generování poèáteèních konfigurací, z nichž se vyzkouší vyhledávání s rùznými možnými heuristikami, a výsledná statistika doporuèí nejvhodnìjší z nich. Vzhledem k zavedení pravdìpodobnosti výbìru ovšem dochází ke ztrátì záruky na pøijatelnost heuristiky ve výše zmínìném smyslu, výhodou je šance expandovat ménì uzlù, tj. levnìjší øešení.

Pomìrnì èasto je možné nalézt vlastnosti nutné pro øešení, což mùže pøispìt k heuristické vyhodnocovací funkci (v šachu k dosažení matu je zapotøebí mít urèitý poèet urèitých figur apod.).

-72-

Algoritmy iterativního vylepšování

Pro øadu tzv. dobøe definovaných problémù (8 dam, VLSI) platí, že popis stavu sám o sobì obsahuje veškerou informaci potøebnou pro øešení. Konkrétní cesta k øešení (zda je øešení dosaženo tak èi jinak) nemusí být (a èasto není) rele- vantní. V tìchto pøípadech poskytují algoritmy s iterativním vylepšováním nejpraktiètìjší pøístup.

Napø. lze zaèít se všemi 8 dámami na šachovnici nebo všemi vodièi v konkrét- ních spojovacích kanálech øešeného obvodu. Pak mùžeme pohybovat dámami ve snaze redukovat poèet vzájemného napadání, nebo pøemís•ovat vodiè z jednoho kanálu do druhého ve snaze redukovat zahlcení.

Obecnou ideou je zaèít s kompletní konfigurací a modifikacemi zlepšit kvalitu.

Pro pøedstavu lze uvažovat o stavech umístìných na povrchu nìjaké krajiny. Výška povrchu v nìjakém místì odpovídá vyhodnocovací funkci (evaluation) pro stav v daném bodì (current state):

-73-

Podle myšlenky iterativního vylepšování je vhodné se v krajinì pohybovat a hledat nejvyšší vrcholek, tj. optimální øešení. Iterativní vylepšování obvykle udržuje údaje pouze o cestì aktuálního uzlu a nehledí dále než k bezprostøed- ním sousedùm daného stavu (hledání vrcholku hory v mlze zároveò s postiže- ním zapomnìtlivostí). Pøes zmínìné nedostaky je tento postup v øadì velmi obtížných pøípadù praktický—typickou ukázkou použití zmínìného postupu jsou umìlé neuronové sítì.

Jednou ze skupin zmínìných algoritmù je tzv. slézání kopce (v originále hill- climbing, nìkdy pojmenované také jako gradient descent, tj. gradientní sestup). Další skupinou jsou algoritmy tzv. simulovaného žíhání (simmulated annealing). Zde se zmíníme o lezení po kopcích.

Slézání kopce (gradientní sestup)

Algoritmus je symbolicky popsán následovnì:

function Hill-Climbing(problem) returns stav øešení

inputs: problem // problém

local variables: current // aktuální stav-uzel next // další stav-uzel

current w Make-Node(Initial-State[problem]) loop do

next w následný uzel s nejvyšší hodnotou

if Value[next] < Value[current] then return current current w next

end

Ve smyèce se hledající jednoduše pohybuje smìrem ke vzrùstající hodnotì (do kopce). Algoritmus nepracuje s vyhledávacím stromem, takže datová struktura pro uzel musí pouze zaznamenávat stav a jeho hodnotu Value. Je-li na cestì vzhùru nìkolik ekvivalentnì nejlepších uzlù, pak se obvykle vybírá náhodnì jeden z nich.

-74-

Uvedený jednoduchý postup má tøi známé nedostatky:

–Lokální maxima: po dosažení lokálního maxima se algoritmus zastaví, pøestože globální maximum (neznámo kde v krajinì je) je mnohem lepší.

–Roviny: ve všech smìrech poskytuje vyhodnocovací funkce stejnou hodnotu, takže postup krajinou vede k náhodné cestì.

–Høebeny: høeben má strmì klesající strany, takže se na nìj lze dostat snadno, ale další stoupání høebenu k vrcholku je velmi mírné a dochází k oscilaci hledání ze strany na stranu se zanedbatelným pokrokem v pøibližování se k maximu.

V každém pøípadì se algoritmus dostane do bodu, odkud se nelze dostat výš. V takových pøípadech se lze pokusit znovu z jiného startovacího bodu—k to- mu se používá metoda zvaná slézání kopce s náhodným poèátkem, takže dochází k sérii hledání z náhodnì vybraných rùzných míst, a nejlepší dosažené øešení se uchovává. Ukonèení vyhledávání pak závisí na tom, zda byl stanoven maximální pøedem stanovený poèet tìchto hledání nebo zda doposud dosažený nejlepší výsledek nebyl po nìjaký poèet iterací zlepšen.

Pro dostateèný poèet iterací mùže (ovšem i nemusí) hledání s náhodným restartem nakonec najít optimální øešení.

Úspìch zmínìného typu hledání velmi silnì závisí na tvaru povrchu, který je dán prostorem uvažovaných stavù. S malým poètem lokálních maxim je øešení nalezeno rychle. Realistické problémy však pøedstavují spíše podobu povrchu dikobraza.

Pro NP-kompletní problémy nelze dosáhnout lepší než exponenciální èasové závislosti. Pøesto jsou takto založené metody velmi èasto úspìšné proto, že poskytují velmi dobré øešení, i když to nemusí být zrovna optimum (a èasto není možné ani zjistit, jaké to optimum vlastnì je). Proto se použije pøijatelný výsledek dosažený po nepøíliš velkém poètu iterací—praktické hledisko hraje èasto výraznou roli.

-75-

Aplikace pro problémy vyhovující omezením (CSP)

Problémy vyhovující omezením (Constraint Satisfaction Problems) mohou být øešeny metodami iterativního zlepšování tak, že napøed jsou všem promìnným dosazeny nìjaké hodnoty a pak za použití modifikaèních operátorù se konfigurace pohybuje smìrem k øešení. Modifikaèní operátory jednoduše pøiøazují jiné hodnoty promìnným.

Napø. pro problém 8 dam je poèáteèním stavem 8 dam nìjak rozestavených na šachovnici a modifikaèní operátor mùže dámou pohnout o políèko vedle.

Tyto algoritmy se nazývají heuristické opravování, nebo• napravují nekon- sistence aktuální konfigurace. Pøi výbìru nové hodnoty promìnné se (heuris- ticky) vybírají takové hodnoty, které jako výsledek dávají minimální konflikty s ostatními promìnnými—tzv. heuristika min-konflikt:

Problém je zde vyøešen ve dvou krocích. Èísla ve sloupci s dámou, jejíž posta- vení se vylepšuje (Dh1 v pravém dolním rohu), udávají, s kolika jinými dámami je v konfliktu. Dáma je pøesunuta na pole h6 (prostøední diagram), kde má konflikt s Df6. Dáma z pole f6 našla nekonfliktní místo na poli f1 a protože další konflikty nejsou, úloha je vyøešena. Pøekvapivì je metoda min- konflikt úspìšná pro mnoho problémù s omezením (CPS) , napø. problém s milionem dam má prùmìrné øešení v ménì než 50 krocích.

V nedávné dobì byla min-konflikt použita pro plánování pozorování vesmír- ného teleskopu Hubble (HST, Hubble Space Telescope), kde redukovala èas nutný pro naplánování týdenního pozorování ze tøí týdnù na pøibližnì 10 minut (astronomové si mohou podávat žádosti o pozorování pomocí HST a velké množství velmi rùzných žádostí vyžaduje velmi dobrý rozvrh).

-76-