***************************
* UMĚLÁ INTELIGENCE *
* 3. část *
***************************
Takovou velmi často využívanou částí aplikací AI jsou programy, které
řeší nějaké hlavolamy. Existuje spousta algoritmů, jež se dají k něčemu
takovému použít, ovšem pravdou je, že jejich skutečná oblast
aplikovatelnosti je mnohem širší. Tedy, ne všech. Některé jsou totiž
tak jednoduché, že v podstatě nepoužitelné. Ovšem těch, co jsou
jednoduššího ražení a jejichž hranice pochopitelnosti nevyžaduje IQ286 a
vyšší je taky dost, takže tenhle článek nebude 2x nejkratší. No nic.
Ještě než začnu blábolit o těch algoritmech, musím vysvětlit pár
drobností. Příklad ze života. Máme systém měst (viz. obrázek) a chceme se
dostat z města (to označené písmenkem S) do města G a zapomněli jsme
cestu. A tak použijeme počítač. Schématu na obrázku se řiká síť (net) a
jednotlivým spojům (v tomhle případě to jsou ta města) nadáváme uzly
(nodes). Pro ty méně chápavé (zdravím Markyho a Milouše X): jednotlivá
slova v závorkách jsou anglickými ekvivalenty k těm, co jsou před nimi.
Síť musíme pro naše potřeby přepracovat do podoby tzv. stromu (tree),
což je v podstatě síť, u níž byly odstraněny smyčky (v našem případě tedy
třeba S-A-D-S-A-D-..). Výsledkem je pak něco takového (viz. obrázek 2).
Horní uzel, který jako jediný nemá žádného vlastníka se jmenuje kořenový
(root node). Jeho opakem jsou uzly bezdětné, neboli koncové (terminal
nodes). Hrany mezi uzly se nazývají větve (branches). Uzel je předkem
(ancestor) jiného, je-li mezi nimi spojitý systém větví. Opakem předka je
potomek, alias descendant. Expanzí uzlu je myšleno vytvoření všech jeho
dětí (children). Pokud mají všechny uzly ve stromu stejný počet dětí, pak
je toto číslo nazýváno faktorem větvení (branching factor).
Toliko k terminologii. Ty algoritmy, které tady teďkonc popíšu, dělají
pouze jednu jedinou věc: PROHLEDÁVAJÍ síť uzlů. Je tedy na nás, chudácích
programátorech, abychom udělali onen strom co nejlepší a na tom pak bude
záviset úspěšnost výpočetního procesu. V knihách o AI (mimochodem, česky
vyšlo o umělé inteligenci asi tolik knih, jako přečetl Marky za celý svůj
život - čili zhruba 3) se nejvíce na demonstraci vytváření stromu používá
puzzle (značně boží slovo, akorát to přesně nejde přeložit), které se
v anglickém originále jmenuje 8, v naší zemičce se tomu říká 15. To máte
spoustu čísel a ty máte za úkol pouhým přesouváním (pěkná blbost -
nejrychlejší způsob je ty kostky přemisťovat vzduchem) dostat do nějakého
uskupení. Může to vypadat třeba takhle:
1 2 8 1 2 3
4 5 # ---> 4 5 6
7 6 3 7 8 #
Znáček # označuje prázdné místo. Takže úkolem prográtora je pak už
jenom napsat algoritmus a vytvořit strom, který bude obsahovat všechny
pozice dosažitelné z výchozího stavu korektními operacemi. Kořenovým uzlem
je výchozí stav, koncovým pak řešení. Kousek stromu vypadá nějak tak:
a 1 2 8
4 5 #
7 6 3
/ | \
/ | \
/ | \
/ | \
/ | \
b 1 2 # c 1 2 8 d 1 2 8
4 5 8 4 # 5 4 5 3
7 6 3 7 6 3 7 6 #
| / | \ |
| / | \ |
| / | \ |
Pozn.: dětmi nějakého uzlu mohou být jenom stavy, které nás nevracejí
do již prozkoumané pozice. Tedy uzel "b" má pouze jednoho
potomka, neboť ten druhý, který jde vytvořit, je totožný s uzlem
"a". Závěrem jest, že žádný uzel se v jedné větvi ( a - b - ..,
nebo a - c - .., atd.) nesmí vyskytovat více jak jedenkrát.
Jedním z nejjednodušších algoritmů je tzv. DEPTH-FIRST SEARCH proces
(česky to znamená prohledávání do hloubky). Začne se u kořenového uzlu.
Pokud není cílovým uzlem, vezme se jedno z jeho dětí (libovolně) a znovu
se otestuje. Když ani tento uzel není cílový, pokračuje se jeho dětmi,
test, děti, atd. Když dospějeme ke koncovému uzlu a nebylo nalezeno
řešení, nastává tzv. mechanismus navracení (back-tracking). Je to de facto
testování zůstatkových dětí. Opět se prohledají potomci. A tak furt
dokola. Pokud je prohledán celý strom a cílový uzel v nedohlednu, lze
konstatovat, že řešení neexistuje. Popis algoritmu následuje.
ALGORITMUS 1: DEPTH-FIRST SEARCH
-------------------------------------
1) vytvoř seznam a do něj umísti kořenový uzel
2) dokud není seznam prázdný nebo se nenašlo řešení prováděj
2a) otestuj první uzel v seznamu. Je-li cílový, pokračuj bodem 3,
jinak vymaž první element ze seznamu a na jeho místo dosaď
všechny jeho děti (pokud existují, když ne, jenom vymaž) v
libovolném pořadí a vrať se do bodu 2
3) pokud nebyl nalezen cílový uzel, řešení neexistuje
Lehkým vylepšením lze z tohoto algoritmu vybudovat o dost více
použitelný postup. Jde o to, že budete preferovat některé uzly a ty budete
prohledávat dříve, než ostatní sourozence. Pro následující proces se
používá funkce, která NĚJAKÝM způsobem vypočítává tzv. zůstatkovou
vzdálenost (remaining distance) od cíle. Je skutečně fuk, jak. To už
závisí na autorovi. Dostáváme HILL-CLIMBING (česky můžeme říct asi
slejzání kopců, ale to zní děsivě).
ALGORITMUS 2: HILL-CLIMBING
-------------------------------
1) vytvoř seznam a do něj vlož kořenový uzel
2) dokud není seznam prázdný nebo se nenašlo řešení prováděj
2a) otestuj první uzel v seznamu. Je-li cílový pokračuj bodem 3, jinak
vymaž první element, setřiď jeho děti v rostoucím pořadí je umisti
na předek seznamu. Vrať se do bodu 2.
3) když nebyl nalezen cílový uzel, řešení neexistuje.
Ve srovnání s prohledáváním do hloubky je slejzání značně efektivnější
(viz. screena č. 3).
Oba popsané algoritmy patří do skupiny, která zahrnuje postupy
hledající NĚJAKOU cestu k řešení. Jak dospějí do koncového stavu, ukončují
činnost (mimo ty dva tam patří ještě BREADTH-FIRST SEARCH {prohledávání do
šířky}, BEAM-SEARCH {takový depth-first, ale s omezením maximálního
zanoření} a nakonec BEST-FIRST SEARCH {používá také zůstatkovou
vzdálenost, ale třídí se celý seznam}). Další skupina je na implementaci o
hodně složitější, ovšem značně efektivní, neboť všechny procesy se
specializují na hledání IDEÁLNÍ cesty. Je tam: BRITISH MUSEUM PROCEDURE,
BRANCH & BOUND, DYNAMIC PROGRAMMING a A*. O těch se můžu rozepsat někdy
jindy, stejně jako o tzv. herních algoritmech používaných v programech na
hraní deskových her, převážně dámy a šachů, kam byly umístěny tyto kousky:
MINIMAX PROCESS, ALPHA-BETA PRUNING, PROGRESSIVE DEEPENING, HEURISTIC
PRUNING a HEURISTIC CONTINUATION. Překlady neuvádím, neboť mě žádné
uspokojivé nenapadly.
A aby nebyla jenom samá teorie, po stisknutí tohodle ČUDLU se vám na
hadru (nebo někde jinde) objeví soubor DEPTH.PAS, což je paskaloidní forma
depthu.
Nashle
Fatal Error
výheň