Definice stavového prostoru

Stavovým prostorem můžeme rozumět dvojici

(1)

kde  je množina všech možných stavů, ve kterých se může úloha nacházet a je množina operátorů pro přechod mezi jednotlivými stavy. Platí, že -tého stavu dosáhneme aplikací operátoru přechodu na stav     je tedy předchůdcem stavu a je naopak následníkem stavu

(2)

Počáteční stav úlohy, ve kterém se nachází při zahájením hledání řešení, označujeme jako

Dále definujeme množinu  cílových stavů, které představují hledané řešení. To může být jedno jediné, cílových stavů představujících řešení však může být i více.  Množina je podmnožinou množiny