Stavy a stavy

Bludiště není k chození, nýbrž k bloudění. Chůze bloudícího (říkejme mu bludič) je totiž komplikována tím, že se od něj vyžaduje časté rozhodování, které navíc může být podřízeno nějakému jeho záměru. Třeba se chce dostat k místu, kde čeká odměna (laboratorní potkani to znají), jindy mu jde zase o to, jak z bludiště uniknout. Anebo chce jen tak bloudit. Obecně jsou bludiště docela zajímavé objekty jak pro hádankáře, tak pro matematiky, ba i pro filosofující teoretiky.

Představte si velmi jednoduché bludiště (viz obrázek) a sebe sama v roli bludiče. Je tu ovšem jistá dichotomie perspektiv: buď jste uvnitř a vidíte jen, co máte v přímém dohledu, anebo hledíte na bludiště jakoby shora (jako zrovna teď) a máte je celé před očima. V druhém případě je hledání jednodušší, správnou cestu můžete spatřit takříkajíc na jeden pohled. Tento rozdíl perspektiv (nikoliv prožitků při bloudění) nicméně zaniká, jsou-li bludiště velmi rozsáhlá a složitá.¹⁾ U těch už není pohled shora tolik výhodný, cestu lze stěží najít jedním pohledem a nakonec nezbude, než si prstem ukazovat na předpokládanou pozici bludiče (proto zde nebudu obě perspektivy nijak zvlášť rozlišovat).

Právě zmínka o „pozici bludiče“ v předešlé větě může být motivací k dalším úvahám, ale s tím rozdílem, že místo o pozicích budeme mluvit o stavech (uvidíte proč). Řekněme, že každému důležitému místu v bludišti odpovídá jeden stav – za „důležitá“ považujme taková místa, v nichž se bludič rozhoduje, kudy dál (popřípadě, zda se raději nevrátit). Chodby se třeba rozvětvují nebo se otevírá pohled na dosud neznámou část bludiště. Vágnost definice nevadí, stavy lze nasázet i jinam – důležité je, že v každém prostorově omezeném bludišti (našeho typu) vystačíme s konečnou množinou stavů (pro naše bludiště stačí 14). Tato množina tvoří stavový prostor bludiště.

Musím být přesnější: ke stavovému prostoru patří nejen stavy, ale též všechny elementární přechody mezi nimi, odpovídající přípustným pohybům bludiče mezi sousedními místy. Proto mluvíme o prostoru, nikoliv jen o množině stavů.²⁾

Stavový prostor typu bludiště je velmi speciálním případem daleko obecnějšího pojetí stavového prostoru, jaké je užíváno vždy, když statický (situační, konfigurační) aspekt nějakého systému je svázán s aspektem dynamickým (pohybovým, akčním, evolučním) – prvého aspektu se týkají stavy, druhého přechody. Zde ovšem mluvím výhradně o diskrétních³⁾ stavových prostorech; ty si můžeme vizuálně představovat (a kreslit) jako grafy s vrcholy pro stavy a hranami pro přechody.⁴⁾

Typickým problémem u diskrétních stavových prostorů je nalézt (co nejlepší) cestu k nějakému cílovému stavu, popřípadě určit strategii, jak se (co nejlépe) chovat v kterémkoli stavu (šach je dobrým příkladem). S diskrétními a často jen konečnými stavovými prostory se setkáme hlavně v kombinatorické matematice, v teorii automatů⁵⁾ a algoritmů a v teorii řešení úloh.

V tomto čísle si všimněte článku Radka Pelánka o Hanojských věžích (Vesmír 89, 544, 2010/9). Jde o manipulační hlavolam, jehož stavy odpovídají všem dovoleným rozmístěním různě velkých disků na kolících. Doporučuji si všimnout zajímavého rozdílu mezi stavovým prostorem pro Hanojské věže a pro bludiště. V případě bludiště je stavový prostor přirozeným korelátem reálného geometrického prostoru (v našem případě dvourozměrného) – stavy jsou místa v bludišti a přechody jsou cesty mezi (sousedními) místy. Naproti tomu stavový prostor pro Hanojské věže (viz obr. 2, Vesmír 89, 544, 2010/9) je abstraktní a s reálným prostorem přímo nesouvisí: stavy představují různá rozmístění disků a přechody odpovídají jejich možným změnám.

Abstraktní stavové prostory můžeme konstruovat pro rozličné jiné hlavolamy, skládačky, hry (jako šach) a pro různé mechanické agregáty. Ba i programy pro „inteligentní“ roboty byly již od samého počátku⁶⁾ založeny na obdobném principu: prostředí, v němž se robot pohybuje a manipuluje s předměty, je charakterizováno množinou „situací“, tj. možných konfigurací předmětů včetně robota samotného. Ten je vybaven repertoárem elementárních „akcí“, pomocí nichž může přesně definovaným způsobem transformovat jednu situaci v jinou tím, že manipuluje s předměty anebo mění svou pozici. Ze známé počáteční situace je pak schopen si „sám“ naplánovat posloupnost akcí k dosažení zadaného cíle.

Podobně jako u Hanojských věží (a jak výše zmíněno, na rozdíl od bludiště) mají abstraktní stavové prostory zpravidla jen velmi málo společného s reálným geometrickým prostorem (což ještě neznamená, že nemají vztah k realitě jako takové – to by však byla už jiná otázka).

Na závěr ještě malý příklad, na němž lze právě ztrátu přímé korelace s reálným prostorem předvést takříkajíc (a vlastně doslova) „v pohybu“. Vzpomeňme na naše bludiště a představme si, že se v něm vedle prvého vyskytne i druhý bludič. Pokud se nebude hýbat, nic se nezmění, bludiště bude mít stejný stavový prostor jako prve. Jakmile se však i druhý bludič začne pohybovat (nezávisle na prvním), nelze než si představit nový stavový prostor, v němž pro každou dvojici pozic bludičů bude existovat jeden (nový) stav. Pokud původní stavový prostor měl (řekněme) n stavů, nový stavový prostor bude mít n × n stavů.⁷⁾ A co teprve, když bloudících bude velmi mnoho? Formálně trivialita, ale kam se poděla naše jednoduchá reálně geometrická intuice?