1
Hledání řešení
Základem celé řady implementací inteligentních systémů je hledání řešení. Obvykle jsou pro mnoho problémů známé výpočetní metody, které hledají řešení deterministicky podle algoritmu, popisujícího toto řešení. V reálném světě je ale řada aplikací, kde není znám algoritmus popisující řešení problému, nebo je pro svou prostorovou či časovou složitost v praxi nepoužitelný. V těchto situacích si tedy člověk musí poradit na základě intuice, zkušenosti, analogie s jinými problémy, nebo v nejjednodušším případě „hrubou silouÿ, tedy metodou pokus - omyl. Tyto nedeterministické medoty pak v oblasti umělé inteligence nazýváme řešením úloh.
1.1
Klasické problémy
Stalo se tradicí, zkoušet a demonstrovat metody umělé inteligence na skupině dobře známých, a dalo by se říci tradičních, problémech. Do tédo skupiny známých problémů řadíme např. tyto: • Hanojské věže. • 15 puzzle. • Problém obchodního cestujícího. • Problém rezervace letenek. Pro vysvětlení základních principů a myšlenek si zde zvolíme jen příklad problému rezervace letenek. Tento problém nabízí asi nejširší škálu analogií s mnohými reálnými problémy a dává řešiteli možnost s tímto úkolem libovolně nakládat, podle aktuálních požadavků zadání.
1.2
Problém rezervace letenek
Pro popis problému můžeme zvolit zavedené konvence z teorie grafů. Tyto principy se využívají v mnoha oborech, jde tedy o postupy dobře známé a ověřené. Za uzly grafu si dosadíme jednotlivá letiště a hrany mezi nimi budou tvořit přímé linky. Každé hraně také můžeme přiřadit cenu, tady vzdálenost mezi dvěma místy. Příkladem může být situace na obr. 1. Zadání pro daný popis problému pak zní: najděte spojení z místa X do místa Y. Takovéto zadání je samozřejmě asi to nejjednodušší, jaké jsme schopni v dané chvíli uvést. Pokud ale budeme muset takovýto problém skutečně řešit, okamžitě se objeví řada omezujících kritérií. A navíc u každého zákazníka jiná. Např. můžeme hledat taková spojení, která nejméně zatíží naši peněženku. Nebo 1
G 110
F
500
200
A
210
B
90
D
230 190
C 180
220 100
E
Obrázek 1: Graf popisující problém rezervace letenek
budeme muset transportovat nadměrné zavazadlo, a to budou schopni překládat jen na některých letištích. Dalším příkladem může být snaha omezit počet přestupů. A určitě se najdou tací, kteří budou mít naspěch a chtějí být v cíli co nejrychleji, bez ohledu na cenu. Stačí krátké zamyšlení a už se objevují první nedostatky našeho jednoduchého popisu z obrázku 1. Jen informace o vzdálenosti dvou míst asi v praxi stačit nebude. Musíme určitě přidat cenu letenky a čas, jak dlouho se poletí. A to jsme ještě nezmínili možnost přidat informace i k jednotlivým uzlům. Jaký bude čas na přestup, zda bude o zákazníka postaráno, zda se nebude muset v jednom městě přesunout mezi dvěma letišti taxíkem, což může být v dopravní špičce akce velmi riskantní a tak bychom mohli úlohu rozvíjet do dalších podrobností. Vraťme se ovšem na zem, do úvodního kursu umělé inteligence. Náš obrázek 1 je přehledný, obsahuje všechny potřebné údaje a pro vysvětlení základních principů nám v něm nic nechybí. A navíc můžeme náš příklad snadno zobecnit na „rezervaci jízdenekÿ, což nám bude v našich zeměpisných šířkách daleko bližší.
1.3
Zobecnění grafové reprezentace
Teorie grafů nás určitě nemusí svazovat jen s místy na mapě a jejich spojnicemi. Grafem lze i popsat řadu dalších problémů. Stačí zmínit stavový automat, kdy uzly grafu mohou být stavy systému a hrany budou přechody mezi stavy. Budeme pak hledat takovou posloupnost akcí, kterou dostaneme systém do požadovaného stavu (a přitom se budeme muset vyvarovat „slepýmÿ ramenům, kdy bychom se mohli dostat do situací, ze kterých už není 2
A
G
B
F
E
C
F
C
D
D
F
E
F
E
C
D
F
B
F
F
B
D
F Obrázek 2: Strom řešení pro spojení z bodu A do F.
návratu, nebo by mohly náš systém poškodit). S myšlenkou popisu stavového automatu musíme zmínit ještě jednu vlastnost grafů, dosut neuvedenou: hrany grafu mohou být orientované, tedy jednosměrné. Mohou být i vícenásobné, či s rozdílnou cenou v obou směrech. Grafem také lze popsat pracovního postupu při řešení havarijní situace např. ve vodní elektrárně nebo obecně u jakéhokoliv zařízení. Postup odpojování různých zařízení podléhá určitým předpisům a také zcela určitě fyzikálním zákonům (jinak budeme muset reagovat v případě výpadku mazání a jinak v okamžiku výpadku synchronizace). Řadu zařízení nelze zastavit v nekonečně krátkém čase a doba zastavení také nemusí být dána pevnou časovou konstantou. A proto v závislosti na typu poruchy mohou být proveditelné postupy jiné a je třeba rozhodnout na základě aktuálně naměřených hodnot a ověřených stavů.
1.4
Strom řešení
Mějme problém na obrázku 1 a dostaneme konkrétní zadání: najděte spojení s bodu A do bodu F. Pro dané zadání není jediné řešení a pokud si řekneme, že se nechceme nikdy na naší cestě vracet na místo, kde jsme již byli, můžeme všechna řešení zakreslit do grafu, kterému říkáme strom řešení a je na obrázku 2. Jde o 3
výsledek aplikace grafového algoritmu pro hledání cesty v grafu. Kořenem stromu je uzel A a jednotlivé dosažené cíle jsou listy tohoto stromu. Výchozí a cílové místo je označeno silným kolečkem, ostatní místa zůstavají v kolečku tenkém. Na obrázku 2 je i vidět, že se během řešení vyskytlo několik slepých cest, které vidíme jako listy, jež nejsou řešením pro dané zadání. Je jasné, že pro složitější úlohy je grafická reprezentace zobrazující všechna řešení mnohdy nemožná pro své celkové rozměry, ale na druhé straně je názorná a dostatečně vysvětluje, jaká jsou možná řešení, jak a kudy bylo cíle dosaženo a ukazuje i slepé cesty. Jen je třeba upozornit, že často dochází k zaměňování pojmu graf problému a strom řešení. Strom řešení je grafickým znázorněním všech řešení pro zadaný graf a požadovaný výchozí a cílový uzel. V některých vyjímečných případech může graf problému vypadat téměř stejně, jako strom řešení. Ale popisují něco jiného!
1.5
Algoritmy hledání řešení
V předchozí podkapitole jsme se zmínili o algoritmech hledání cestu v grafu. Zde si popíšeme dvě metody pro slepého hledání – hledání do hloubky a hledání do šířky. Dále se pak zmíníme o možných heuristických metodách. 1.5.1
Hledání do hloubky
Při tomto hledání vybíráme uzly tak, že pokud neexistuje elementární řešení - přímé spojení výchozího a cílového uzlu, vybíráme prostředníky, abychom co nejrychleji dospěli k vzdálenému cíli (opět jen připomeneme, že při hledání cesty v grafu se nevracíme do již navštívených uzlů). Jak takový postup vypadá, je názorně vidět na obrázku 3. Opět hledáme cestu z A do F v grafu 1 a do známého stromu řešení 2 jsme jen čárkovanými čarami naznačili postup řešení (a tedy postup vzniku stromu řešení). 1.5.2
Implementace hledání do hloubky
Nejprve nadefinujeme všechny hrany grafu. % zadani hran grafu - orientovanych! hrana( hrana( hrana( hrana( hrana(
a, a, a, b, b,
g, b, c, d, e,
500 ). 210 ). 230 ). 90 ). 190 ).
4
A
G
B
F
E
C
F
C
D
D
F
F
E
E
C
D
F
B
F
F
B
D
F Obrázek 3: Hledání do hloubky - pro hledání cesty z bodu A do F.
hrana( hrana( hrana( hrana( hrana(
c, d, d, e, f,
e, e, f, f, g,
180 100 200 220 110
). ). ). ). ).
Takto zadané informace ovšem spíše reprezentují orientované hrany hrafu. Proto pokud chceme používat hrany jako obousměrné, museli bychom každou hranu zadat i s opačným výchozím a cílovým uzlem. Elegantnější samozřejmě bude, pokusit se vyřešit obousměrný průchod přes hranu programově: % hledani neorientovane hrany spoj( X, Y, C ) :hrana( X, Y, C ). spoj( X, Y, C ) :hrana( Y, X, C ). Tímto máme zadaný celý graf z obrázku 1, kde jsou všechny hrany neorientované. Teď už můžeme napsat, jak bude vypadat implementace algoritmu 5
pro hledání do hloubky. Pro zajištění průchodu každým uzlem jen jednou, použijeme pomocný predikát z předchozí kapitoly - assertb. :-dynamic( uzel/1 ). % algoritmus hledani do hloubky hloubka( X, Y, C ) :assertb( uzel( X ) ), spoj( X, Y, C ), assertb( uzel( Y ) ), write( ’Nalezene reseni ’ ), nl, listing( uzel ). hloubka( X, Y, C ) :assertb( uzel( X ) ), spoj( X, Z, C1 ), Z \= Y, hloubka( Z, Y, C2 ), C is C1 + C2. hloubka( X, Y, C ) :write( ’Slepa cesta z ’ ), write( X ), write( ’ - ’ ), write( Y ), nl, fail. Upozornění: algoritmu si do databáze ukládá informaci i prošlých uzlech. Chcete-li po nalezení jednoho řešení pokračovat v hledání pro jiné zadání, musíte ostranit z databáze fakty uzel(X). Nejlépe následujícím příkazem: retractall( uzel( _ ) ). 1.5.3
Hledání do šířky
Postup hledání do šířky můžeme opět znázornit graficky ve stromu řešení. Hledání postupuje po „vrstváchÿ, kdy pro výchozí uzel nejprve projdeme všechny jeho nejbližší sousedy. Pro všechny tyto sousedy opět hledáme jejich sousedy. Tento postup opakujeme tak dlouho, dokud v dané vrstvě není obsažen požadovaný cíl. Názorně je to vidět na obrázku 4. 1.5.4
Implementace hledání do šířky
Základ implementace, tedy popis grafu, můžeme použít z předchozího algoritmu hledání do hloubky.
6
A
G
B
F
E
C
F
C
D
D
F
E
F
E
C
D
F
B
F
F
B
D
F Obrázek 4: Hledání do šířky - pro hledání cesty z bodu A do F.
Musíme jen navrhnout, jak budeme postupovat. Předchozí algoritmus pracoval vždy jen maximálně se dvěma uzly grafu současně. Zde ovšem musíme postupovat po vrstvách a tak se automaticky nabízí použití seznamů. Nejprve si sestavíme dva pomocné predikáty. Jeden pro nalezení všech sousedů zadaného uzlu. Nazveme jej okoli. Druhým pomocným predikátem bude vrstva, kdy pro již známou vrstvu sestavíme vrstvu následující. Postup je jednoduchý, nalezneme okolí pro každý prvek vrstvy a všechny takto získané seznamy spojíme do jediného. Jako pomocné predikáty použijeme již známé ověření, zda je prvek obsažen v seznamu - predikát prvek a pro spojení dvou seznamů predikát spoj seznamy. % nalezeni okolnich uzlu pro zadany uzel okoli( U, SI, SO ) :spoj( U, X, _ ), not( prvek( X, SI ) ), okoli( U, [ X | SI ], SO ). okoli( _, S, S ). % nalezeni nasledujici vrstvy
7
vrstva( [], [] ). vrstva( [ H | T ], VO ) :okoli( H, [], OK ), vrstva( T, V ), spoj_seznamy( OK, V, VO ). S těmito pomocnými predikáty je sestavení algoritmu snadné. Vstupem do řešení je predikát sirka. Ten volá hlavní predikát sirka vrstvy, kde probíhá vlastní postup po vrstvách. % algoritmus hledani do sirky % - cesta z uzlu S do C - nalezeneho ve vrstve V % sirka( Start, Cil, Vrstva ) sirka( S, C, V ) :sirka_vrstvy( C, [S], L ), write( ’Nalezena vrstva: ’ ), nl, write( L ). % sirka_vrstvy( Cil, Vrstva, Vysledek ) sirka_vrstvy( C, V, V ) :prvek( C, V ). sirka_vrstvy( C, VI, VO ) :vrstva( VI, V ), sirka_vrstvy( C, V, VO ). Je nutno dodat, že algoritmus neeviduje již jednou prošlé uzly a tak se ve vrstvách objevují některé uzly duplicitně a nebere se ani ohled na uzly již prošlé. Jednoduchým, ale ne zcela korektním řešením by mohlo být vyloučení duplicit ve vrstvě. Úplné řešení tohoto problému ale není triviální a nebude zde rozebíráno.
1.6
Heuristika
Dvě již uvedené metody hledání řešení - hledání do hloubky a do šířky - jsou metody slepé, postupující čistě mechanicky. Pro zlepšení efektivity hledání je dobré využít nějaké heuristiky. Mnozí si asi ihned položí otázku, co to heuristika je. Nemá smysl hledat jen jedno slovo, kterým bychom tento pojem vysvětlili. Ale určitě můžeme říci, že použití zkušenosti, intuice, zdravého rozumu a (lokální) znalosti problému, může přispět ke zefektivnění postupu hledání řešení. Představíme si dva takové jednoduché algoritmy: 8
• Hill-Climbing - metoda největšího gradientu. • Least-Cost - cesta nejmenších nákladů.
1.7
Hill–Climbing
Jak už samotný název metody napovídá, je tato metoda inspirována reálnou situací. Chceme-li dosáhnout vrcholu kopce, bude nejrychlejší postup po spádnici, tedy cestou nejvyššího gradientu (pokud použijeme analogii z matematiky). Na našem příkladu s jízdenkami by mohlo jít o úvahu, že nejlepší bude koupit v každém místě jízdenku do nejvzdálenějšího místa, čímž urazíme největší kus cesty a přiblížíme se tak nejvíce k cíli. V praxi má tato úvaha smysl, pokud půjde o spojení ve velmi rozlehlé síti míst. Při aplikaci na hromadnou dopravu do města je podobné rozhodnutí naopak asi velmi nevhodné, neboť bychom již prvním použitým spojem vycestovali na konečnou stanici za město. V počítačové síti bychom si mohli aplikaci metody Hill-Climbing představit v situaci implicitního směrování paketů v síti, kdy budeme pakety odesílat tím spojem, který má v dané chvíli nejvyšší propustnost. Následná implementace bude jen rozšířením prohledávání do hloubky o vyhledání „nejvzdálenějšíhoÿ souseda. Pomocný predikát pro tento úkol by mohl vypadat asi následovně: hillclimb( X, Y, C ) :spoj( X, Y, C ), not( ( spoj( X, _, C2 ), C2 > C ) ), !. Predikát nalezne nejvzdálenějšího souseda pro zadané X. Ač může predikát na první pohled vypadat nesrozumitelně, jeho význam je zřejmý: hledáme takový spoj z X, aby neexistoval jiný spoj z X, který by měl vyšší cenu. Teď můžeme predikát přidat k slepému prohledávání do hloubky. Postup hledání bude takový, že se pokusíme jít v každém uzlu metodou nejvyššího gradietu a bude-li tato cesta slepá, tak se vrátíme a budeme postupovat klasickým způsobem - hledáním do hloubky. Výsledný algoritmus bude vypadat následovně: hloubka( X, Y, C ) :assertb( uzel( X ) ), spoj( X, Y, C ), assertb( uzel( Y ) ), write( ’Nalezene reseni ’ ), nl, listing( uzel ). hloubka( X, Y, C ) :9
assertb( uzel( X ) ), hillclimb( X, Z, C1 ), Z \= Y, hloubka( Z, Y, C2 ), C is C1 + C2. hloubka( X, Y, C ) :assertb( uzel( X ) ), spoj( X, Z, C1 ), Z \= Y, hloubka( Z, Y, C2 ), C is C1 + C2. hloubka( X, Y, C ) :write( ’Slepa cesta z ’ ), write( X ), write( ’ - ’ ), write( Y ), nl, fail.
1.8
Least–Cost
Druhou ukázkou použití heuristiky bude příklad postupu tím směrem, který bude vyžadovat nejmenší náklady, režii nebo energii. Určitě se také nabízí ne zcela přesné, ale výstižné vysvětlení: „postupovat cestou nejmenšího odporuÿ. V praxi by to mohlo znamenat, že např. při rozvozu zboží se budeme snažit od každého zákazníka pokračovat k nejbližšímu dalšímu. Tím ovšem neříkáme, že jsme postupovali optimálně! Dalším příklad by mohl být opět z počítačové sítě, kdy se budeme snažit imlicitně všechna data směrovat tím spojem, za který platíme nejnižší cenu za množství přenesených dat. Implementace bude i v tomto případě jen rozšířením slepého hledání do hloubky. Potřebujeme jen pomocný predikát pro nalezení „nejbližšíhoÿ souseda pro zadaný výchozí bod. Predikát bude vypadat následovně: leastcost( X, Y, C ) :spoj( X, Y, C ), not( ( spoj( X, _, C2 ), C2 < C ) ), !. Stačí letmý podled a je jasné, že se jedná o již známé řešení metody Hill–Climbing, jen použijeme opačnou podmínku a hledáme tak spoj, jehož cena je nejnižší. Výsledný program také bude stejný jako u předchozí metody, jen se predikát hillclimb nahradí predikátem leastcost.
10
2
Cvičení
Téma hledání řešení bude probíráno ve dvou cvičeních.
2.1
Ověření funkcionality algoritmů
Každý student si nakreslí vlastní souvislý graf s minimálně 10 vrcholy a 15 hranami. Každá hrana musí mít svou cenu a je možno mít i hrany orientované. Pro kontrolu správného fungování algoritmů je vizuální kontrola velmi důležitá a je možno rychleji hledat chyby v reprezentaci dat i v programu. Nepodceňujte význam obrázků! Přepiště si algoritmy pro hledání řešení do šířky i do hloubky a ověřte jejich funkcionalitu nad vlastním grafem.
2.2
Hledání optimálního řešení, použití heuristiky
Rozšiřtě algoritmus hledání do hloubky o možnost nalezení všech řešení pro každé zadání. Nalezená řešení ukládejte postupně do databáze prologu. Z nalezených řešená vyberte optimální řešení. Musíte si ovšem sami rozhodnout, co je v dané chvíli chápáno, jako „optimálníÿ řešení. Zda nejkratší, nebo nejdelší cesta, případně cesta s nejměnším počtem vrcholů. Do hledání je také možno zapojit heuristiku a porovnat pořadí nalezených řešení.
11
