Komerční prezentace
Registrace uživatele

Přihlašte se k odběru informací, novinek, získejte přístup do diskuzního fóra.

Vesmír č. 10
Vesmír č. 10
Toto číslo vychází
2. 10. 2017
Novinky
Zdarma jedno celé číslo Vesmíru v pdf.
• Říjnové číslo Vesmíru
reklama

Stavy a stavy

Publikováno: Vesmír 89, 503, 2010/9
Rubrika: Úvodníky

Kdo nejde vpřed, jde vzad: neexistuje nehybný stav.

V. G. Bělinskij

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á.1) 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ů.2)

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ích3) stavových prostorech; ty si můžeme vizuálně představovat (a kreslit) jako grafy s vrcholy pro stavy a hranami pro přechody.4)

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ů5) 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čátku6) 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ů.7) 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?

Poznámky

1) Připomíná to rozdíl mezi přímým viděním malých počtů a postupným počítáním prvků velkých souborů; psal jsem zde o tom právě před rokem („Vidět počty a čísla“, Vesmír 88, 527, 2009/9).

2) V matematice (hlavně od 20. stol.) ztratilo slovo „prostor“ svůj původní, čistě geometrický nebo fyzikální význam a začalo být užíváno pro daleko obecnější struktury.

3) S konečným nebo spočetně nekonečným počtem stavů.

4) Naproti tomu v teorii dynamických systémů a v matematické fyzice hrají velkou roli kontinuální stavové (či fázové) prostory.

5) Konečné automaty jsou v jistém pohledu totéž co stavové prostory s konečným počtem stavů.

6) Např. program STRIPS ze začátku 70. let. Srov. I. M. Havel, Robotika – úvod do teorie kognitivních robotů, SNTL, Praha 1980.

7) K úvaze na cestu domů: Co když se druhý bludič bude pohybovat extrémně pomalu?

Soubory

článek ve formátu pdf: 201009_503.pdf (242 kB)

Diskuse

Žádné příspěvky