Hlavní navigace

Mercury: Složitější abstrakce nad algoritmy

Ondřej Bojar 25. 3. 2004

Minulý díl seriálu představil velmi jednoduché typy abstrakce nad algoritmy. Konkrétně jsme představili pouze abstrakci for-cyklu dvou typů. Dnes si ukážeme, jak je možné a pohodlné provádět i abstrakce složitější.

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.

Našli jste v článku chybu?

5. 5. 2004 10:34

Štěpán Kasal (neregistrovaný)

V článku se píše: "Při hledání do šířky se jen nesmírně zpomalí a spotřebuje mnohem víc paměti."

Není to pravda, pokud řešení neexistuje, i hledání do šířky se zacyklí.



29. 3. 2004 16:10

Ondřej Bojar (neregistrovaný)

Titulek článku neodpovídá obsahu. O typových třídách bude příští díl. Stalo se tak bohužel proto, že jsem na týden mizel mimo dosah Internetu a článek jsem původně připravil jako celek: příklady abstrakce+typové třídy. Tenhle celek byl však příliš masivním soustem, a tak jej v redakci (na můj mírný podnět) rozdělili. Já už neměl možnost rozdělení spatřit. Díl poslední, tj. druhá část původního textu, bude uveden ve čtvrtek, a titulek už nezklame.

Tak promiňte.

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

120na80.cz: Bojíte se encefalitidy?

Bojíte se encefalitidy?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život