1.3. Az állapottérgráf

Legyen a probléma az állapottér-reprezentációval megadva. Ez a reprezentáció egy irányított gráfot határoz meg.

Az

Equation 1.. 


irányított gráfot a probléma állapottér-reprezentációjához tartozó állapottérgráfjának vagy reprezentációs gráfjának nevezzük.

Lemma:

Legyen a probléma állapottér-reprezentációjához tartozó állapottérgráfja. Pontosan akkor vezet az állapottérgráf csúcsából az ettől különböző csúcsba irányított út, ha az állapotból az állapot elérhető.

Bizonyítás:

  1. Tegyük fel, hogy (). Ez azt jelenti, hogy van olyan (véges) állapotsorozat, hogy

    Equation 1.. 


    Tehát a reprezentációs gráfban minden -re az csúcsból irányított él vezet az csúcsba, azaz

    Equation 1.. 


    Ez viszont azt jelenti, hogy csúcsból irányított út vezet az csúcsba.

  2. Tegyük fel azt, hogy az állapottérgráf csúcsából az ettől különböző csúcsba irányított út vezet. Ez azt jelenti, hogy van olyan irányított élsorozat az állapottérgráfban, hogy és . Ekkor

    • egyrészt és ,

    • továbbá csak akkor, ha .

    Ez azt jelenti, hogy , tehát az állapotból az állapot elérhető.

Tétel:

Legyen a probléma állapottér-reprezentációjához tartozó állapottérgráfja. Pontosan akkor megoldható , ha van az állapottérgráfban a startcsúcsból valamelyik terminális csúcsba vezető irányított út.

Bizonyítás:

  1. Egyrészt ha megoldható, van olyan célállapot, hogy . De ekkor az állapottérgráfban irányított út vezet az startcsúcsból az terminális csúcsba.

  2. Másrészt ha van az állapottérgáfban az startcsúcsból valamely terminális csúcsba vezető irányított út, a állapotból elérhető ezen terminális csúcs által szemléltetett állapot. De a terminális csúcsok célállapotokat szemléltetnek. Tehát megoldható.

A probléma állapottér-reprezentációjában vegyük figyelembe az operátorok alkalmazási költségeit. Rendeljünk ekkor minden élhez költséget: ha , akkor legyen ezen él költsége (jelölve: ). Egy

Equation 1.. 


irányított út költsége a benne szereplő élek költségösszege

Equation 1.. 


Ha minden él költsége egységnyi, az irányított út költsége éppen az út éleinek a száma.

Egy állapottér-reprezentált probléma megoldásának sikerét jelentősen befolyásolja a reprezentációs gráf bonyolultsága:

Ezért célszerű minden lehetséges egyszerűsítést végrehajtani. Lehetséges egyszerűsítések: