Reprezentace stavového prostoru

Definici stavového prostoru a možnosti jeho kódování si objasníme na příkladu řešení hlavolamu „Hanojské věže“.

Princip úlohy spočívá v tom, že máme k dispozici tři tyčky a na nich navlečeny tři disky různých průměrů.

Obr. 1. Hlavolam „Hanojské věže“.

Úkolem řešitele je přemístit všechny kotouče z první věže na druhou a to za pomoci dočasného odkládání kotoučů na třetí věž. Pro uspořádání a přesuny disků platí následující pravidla:

• V jednom tahu lze přemístit jen jeden kotouč.
• Jeden tah je složen z uchopení kotouče z vrcholu jedné věže a z jejího přemístění na vrchol věže jiné.
• Je zakázáno položit větší kotouč na menší.

Počátečním stavem je tedy konfigurace, kdy máme všechny kotouče na první věži seřazené od největšího po nejmenší. Množina cílových stavů zde obsahuje právě jeden stav a to stav, kdy jsou všechny kotouče korektně uspořádány na druhé věži.

Zaveďme si kódování, které bude vyjadřovat konkrétní stav řešení úlohy pomocí uspořádané trojice čísel, kde pozice čísla v závorce určuje disky od největšího k nejmenšímu a hodnota čísla na dané pozici vyjadřuje, na které věži se daný disk nachází. Počáteční stav tedy můžeme zapsat jako (111), pokud přesuneme nejmenší kotouč na druhou věž, bude stav kódován jako (112), cílový stav pak jako (2,2,2).

Celkově se úloha může pro tři tyčky nacházet v  stavů, kde n představuje počet disků. Každý z disků musí nacházet na jedné ze tří tyček. V našem případě tedy dostáváme pro tři disky, kdy každý musí být najedné ze tří tyček (tři možnosti umístění na tyčky pro každý disk, rozkládáme celkově tři disky) pro počet možných stavů 3x3x3. Množina všech možných stavů  je tedy přestavována 27 prvky.

Množina operátorů má v našem případě 6 prvků „přesuň vrchní disk z věže k na věž i“, tedy

Jednotlivé stavy je možné uspořádat do podoby orientovaného grafu, kdy kořenovým uzlem je počáteční stav a z něj jsou pak aplikací všech přípustných operátorů generovány postupně stavy následující. Přípustný operátor je takový, jehož aplikaci nezakazují pravidla úlohy, například „Je zakázáno položit větší kotouč na menší“.

Obr. 2. Stavový prostor hlavolamu „Hanojské věže“.