Problém rozestavění osmi dam na šachovnici:
alternativní řešení metodou hill-climbing
Úloha č. 4 pro cvičení k předmětu Vybrané kapitoly z umělé inteligence
Zadání: Implementujte v libovolném programovacím
jazyce heuristiku hill-climbing (slézání kopce), zmí-
něnou na přednášce, pro uspořádání osmi vzájemně se
nenapadajících dam na šachovnici 8x8. Své řešení
otestujte na příkladu uvedeném níže (levá šachovnice)
a dále navrhněte ještě nějakou jinou testovací pozici;
můžete např. využít data z minulé úlohy č. 3, kde byl
tentýž problém řešen pomocí metody min-konflikt.
Vyhodnoťte svá řešení--zjistěte průměrný počet kro-
ků pro nalezení výsledku, nárůst jejich počtu při vý-
skytu 2, 3 nebo více konfliktů, apod.
Pozn.: hill-climbing je v principu jednoduché hledání
cesty k řešení, kdy agent vidí pouze do omezené vzdá-
lenosti, které následující stavy má k dispozici, a zvolí
jako další stav ten, který momentálně vypadá nejslib-
něji z hlediska zlepšení situace, v níž se nachází
(greedy search, lačné vyhledávání). Metoda patří
k nejzákladnějším tzv. lokálním vyhledávacím techni-
kám: současný stav (uzel) je nahrazen stavem (uzlem)
tvořeným nejlepším viditelným sousedem (uzlem),
který má ze všech viditelných sousedů nejvyšší ho-
dnotu. Globální maximum vidět není, nejlepší mo-
mentálně viditelný soused může být maximem lokál-
ním a obecně hrozí uváznutí v lokálním extrému ne-
známé funkce. Další nebezpečí hrozí v případě, kdy
okolní nejbližší stavy mají všechy stejné vyšší hodno-
ty ("náhorní planina"), takže nelze jednoznačně určit,
kterým směrem se má agent vydat--cílem je "lézt do
kopce", tj. zvyšovat hodnotu dosud nalezeného řešení
(optimum je v globálním extrému, jehož nalezení není
zaručeno). Také když se objeví "hřeben" pohoří (smě-
řující velmi zvolna vzhůru), vede to obvykle k sek-
venci lokálních extrémů.
Hill-climbing je cyklus, který posouvá agenta neustále
do nějakého dalšího stavu s vyšší hodnotou. Konec
vyhledávání není jednoznačný--agent může skončit,
pokud nevidí nikde kolem sebe lepší stav, než v jakém
právě je, ale to nemusí znamenat, že lepší stav není:
např. ocitne-li se na "náhorní planině" a vlivem "za-
mlženosti" krajiny (prohledávaného prostoru) nevidí,
že někde je ještě možné šplhat dál vzhůru. Heuristika
nepoužívá vyhledávací strom (není zapotřebí rozsáhlá
paměť), je rychlá, ale často uvázne v lokálním extré-
mu. Existují různá vylepšení, např. pro umělé neuro-
nové sítě, ale odstranit všechny nedostatky nelze.
XABCDEFGHY
8-+-+-+-+(
7+-+-+-+-'
6-+-+-+-+&
5+-+ +-+-%
4 +-+ +-+$
3+ +-+ + #
2-+ +-+ +"
1+-+-+-+-!
xabcdefghy
Jedna z možných pozic s mnoha
napadajícími se dámami
(h = 17 napadajících se dvojic)
XABCDEFGHY
8-+-+-+ +(
7+-+- +-'
6- +-+-+&
5+-+ +-+-%
4-+-+- +$
3+-+-+-+ #
2-+ +-+-+"
1 +-+-+-!
xabcdefghy
Příklad uváznutí v lokálním extrému
po nalezení zlepšené pozice
(h = 1 napadající se dvojice)
Pozn.: Globální extrém je definován pro h = 0. Generování následných stavů je zde pohybem dam po sloupcích.
Všechny následné stavy, z nichž se vybírá další krok směrem k optimu, lze vytvořit změnami pozic dam
postupně: sloupec a, sloupec b, ..., sloupec h. Každý stav má 8 × 7 = 56 následníků. Je-li více ekvivalentních
nejlepších následných stavů, pak se následník zvolí náhodným výběrem (proto bývá vhodné vyzkoušet hill
climbing několikrát; jiný náhodný výběr se může později vyhnout uváznutí v lokálním extrému). Zelené krouž-
ky na levé šachovnici označují potenciální následníky s h = 12; tyto stavy vzniknou pro některé dámy (sloup-
ce b, e, f, g). Ostatní (zeleně neoznačené) možné následné stavy zde mají h mezi 13 a 18, tj. lokální extrém je
zde dán pro h = 12; do globálního extrému pak mohou vést další kroky. Na pravé šachovnici je červeně označe-
no dosažení lokálního extrému, v němž může systém uváznout.