Hledání do hloubky, šířky či za nejlepším řešením
Jako příklad nám poslouží úloha obecného hledání, např. hledání nejkratší cesty grafem nebo hledání postupu, jak vyřešit hlavolam. Můžeme přitom řešení hledat studováním problému do hloubky (dokud to jde, pokračuj stanoveným směrem, až narazíš, udělej krok zpátky a zkus jiný směr), do šířky (z počátečního místa zkus udělat krok do všech směrů najednou, tím prověříš všechny cesty délky 1; v následujícím kroku zkus pokračovat do všech směrů o krok dál, tím prověříš všechny cesty délky 2 atd.), nebo za použití přípustné heuristické funkce optimálně (algoritmus A*). Pro bližší seznámení s problematikou umělé inteligence a konkrétně s definicí pojmů jako stavový prostor mohu doporučit např. tuto prezentaci. Pro obecnou charakterizaci všech popsaných způsobů hledání stačí popsat:
- Jak vypadá počáteční stav úlohy (na kterém políčku v místnosti se nacházíme).
- Jak je možné z jednoho stavu přejít do jiného (jakými směry je povoleno z daného políčka udělat krok).
- Když máme více možností na výběr, kudy se vydat dál (kterým směrem vyrazit nejdříve).
- Jak se pozná, že jsme našli koncový stav (stojíme už na cílovém políčku?).
Budeme-li stavy reprezentovat strukturou typu T, implementovat skořápku řešícího algoritmu je hračka:
:- pred generuj_reseni(
pred(T, T), % generátor následujícího dostupného stavu
pred(T), % kontrola, zda je je daný stav cílový
pred(list(T), list(T), list(T)),
% máme-li nové možnosti postupu na výběr, je
% žádoucí tyto možnosti promíchat a uspořádat
% s možnostmi již nalezenými a zatím neprověřenými
list(T), % seznam startovních stavů
T % výsledný nalezený stav
).
:- mode generuj_reseni(
pred(in, out) is nondet,
% generátor z aktuálního stavu může být schopen
% vyrobit následných dostupných stavů více, nebo
% také žádný, pokud jsme ve slepé uličce
pred(in) is semidet,
% kontrola koncového stavu uspěje, pokud stav
% odpovídá platnému řešení úlohy (jsme na cílovém
% políčku), a selže, pokud ještě stav koncový
% není a je třeba zkoušet z něj pokračovat dále
pred(in, in, out) is det,
% úkolem "třídiče" dosud rozpracovaných stavů je
% deterministicky podle stanovených pravidel spojit
% a urovnat stavy starší se stavy právě nalezenými.
% Třídič tedy nesmí selhat.
in, % seznam startovních stavů je vstupním parametrem
out % nalezený cílový stav je výstupem řešiče
) is semidet.
% řešič v této obecnosti nemůže zaručit, že najde
% nějaké řešení (žádné nemusí existovat).
% Implementujeme řešič ovšem tak, že hned po
% nalezení prvního vhodného řešení skončí.
generuj_reseni(Generator, JeStavKoncovy, SpojNoveAStareStavy,
VstupniStavy, NalezenyCilovyStav) :-
VstupniStavy = [],
fail % není žádný stav, z něhož bychom mohli
% zkusit vyjít, všechny cesty k řešení už
% dříve selhaly, řešení neexistuje
; % nebo
VstupniStavy = [NejvhodnejsiKandidat|DalsiKandidati],
% první ve frontě rozpracovaných stavů je ten,
% který v minulém kroku označil náš třídič za
% nejnadějnější
(
if JeStavKoncovy(NejvhodnejsiKandidat)
then NalezenyCilovyStav = NejvhodnejsiKandidat
else
% musíme zkusit z nejvhodnějšího kandidáta
% pokračovat dále, když kandidát sám zatím
% koncovým stavem nebyl
solutions(
(pred(JednoZMoznychPokracovaniZKandidata::out) is nondet:-
Generator(NejvhodnejsiKandidat,
JednoZMoznychPokracovaniZKandidata)
), PrijatelniNasledniciKandidata),
% všechny bezprostřední následníky daného
% stavu vygenerujeme, tj. vyrobíme seznam
% možných pozic po dalším kroku
SpojNoveAStareStavy(PrijatelniNasledniciKandidata,
DalsiKandidati,
NoviKandidati),
% podle daných pravidel promícháme čerstvě
% získané kandidáty s kandidáty staršími
generuj_reseni(Generator, JeStavKoncovy,
SpojNoveAStareStavy, NoviKandidati,
NalezenyCilovyStav)
% a rekurzivně necháme nové kandidáty
% prověřit/rozpracovat
). Doufám, že z popsaného vynikla abstrakce druhého řádu zřetelně: nejen, že náš řešič problémů dává plnou volnost v tom, o jaký problém jde (stav je reprezentován prostě datovou strukturou typu T, pro kterou jsou dodány dvě pomocné operace: generátor dalšího možného kroku a kontrola, zda je stav koncový), ale dokonce dává i plnou volnost v tom, jak při řešení úlohy postupovat.
Bude-li predikát spojující čerstvé a starší kandidáty řadit tak, že napřed půjdou čerství a pak starší, bude algoritmus prohledávat stavový prostor do hloubky. (Napřed postupuj ještě o krok dál s novým řešením, teprve až nebude žádný další krok možný, použij posledního staršího kandidáta). Pro tento účel stačí použít jako spojovač standardní predikát list__append/3.
:- type muj_typ_stavu.
:- func vytvor_poc_stav = muj_typ_stavu.
:- pred muj_generator(muj_typ_stavu::in, muj_typ_stavu::out) is nondet.
:- pred muj_kontrolor_konce(muj_typ_stavu::in) is semidet.
:- pred existuje_reseni is semidet.
existuje_reseni :-
PocStav = vytvor_poc_stav,
generuj_reseni(muj_generator, muj_kontrolor_konce, list__append,
[ PocStav ], CilovyStav). Bude-li naopak predikát spojující čerstvé a starší kandidáty upřednostňovat kandidáty starší, bude náš řešič postupovat ve stavovém prostoru do šířky. Implementace pak musí prohodit argumenty predikátu list__append/3:
existuje_reseni :-
PocStav = vytvor_poc_stav,
generuj_reseni(muj_generator, muj_kontrolor_konce,
(pred(A::in, B::in, C::out) is det:-list__append(B, A, C)),
[ PocStav ], CilovyStav). (Pro jednoduchost jsme nekontrolovali, zda generátor nedoporučuje udělat zase krok zpět, mezi už jednou navštívené stavy. Při nevhodné kombinaci a hledání do hloubky se může řešič zacyklit. Při hledání do šířky se jen nesmírně zpomalí a spotřebuje mnohem víc paměti.)
Jak správně implementovat takový třídič stavů, který spolehlivě najde nejlepší řešení nejdřív, už bohužel přesahuje cíl našeho příkladu.
