Busca Uniforme - Formalização do Problema

Formalização do Problema em

Espaço de Estados

Nesta página é apresentada a representação de espaço de estados utilizada para a implementação do problema das 7 fichas.

O problema das 7 fichas foi definido da seguinte forma:

* - indica ficha preta

o - indica ficha branca

i - indica espaço vazio

A seguir, de acordo com a sintaxe da linguagem prolog estão representados os estados de busca possíveis para o problema. Sendo definidos: o estado inicial, os estados intermediários e os estados finais. O estado final consiste em colocar todas as peças pretas antes de todas as peças brancas, sendo que o espaço em branco pode estar em qualquer posição, com isso tem-se 7 estados finais possíveis.

Estado inicial:

estado_inicial([*,*,*,o,o,o,i]).

Estados finais possíveis:

[o,o,o,*,*,*,i] e_uma_meta.

[o,o,o,*,*,i,*] e_uma_meta.

[o,o,o,*,i,*,*] e_uma_meta.

[o,o,o,i,*,*,*] e_uma_meta.

[o,o,i,o,*,*,*] e_uma_meta.

[o,i,o,o,*,*,*] e_uma_meta.

[i,o,o,o,*,*,*] e_uma_meta.

Declaração dos predicados que definem as ações de deslizar e saltar:

desliza: move uma ficha para o espaço vazio adjacente.
salta: desloca a ficha duas posições ocupando um lugar vazio. Equivale a saltar uma ficha.
salta2: desloca a ficha três posições ocupando um lugar vazio. Equivale a saltar duas fichas.
predicado operação(ação, custo) transforma estado1 em estado2

Estados intermediários:

operacao(desliza,1) transforma [A,B,C,D,E,F,i] em [A,B,C,D,E,i,F].

operacao(salta,1) transforma [A,B,C,D,E,F,i] em [A,B,C,D,i,F,E].

operacao(salta,2) transforma [A,B,C,D,E,F,i] em [A,B,C,i,E,F,D].

operacao(desliza,1) transforma [A,B,C,D,E,i,F] em [A,B,C,D,i,E,F].

operacao(desliza,1) transforma [A,B,C,D,E,i,F] em [A,B,C,D,E,F,i].

operacao(salta,1) transforma [A,B,C,D,E,i,F] em [A,B,C,i,E,D,F].

operacao(salta,2) transforma [A,B,C,D,E,i,F] em [A,B,i,D,E,C,F].

operacao(desliza,1) transforma [A,B,C,D,i,E,F] em [A,B,C,i,D,E,F].

operacao(desliza,1) transforma [A,B,C,D,i,E,F] em [A,B,C,D,E,i,F].

operacao(salta,1) transforma [A,B,C,D,i,E,F] em [A,B,i,D,C,E,F].

operacao(salta,1) transforma [A,B,C,D,i,E,F] em [A,B,C,D,F,E,i].

operacao(salta,2) transforma [A,B,C,D,i,E,F] em [A,i,C,D,B,E,F].

operacao(desliza,1) transforma [A,B,C,i,D,E,F] em [A,B,i,C,D,E,F].

operacao(desliza,1) transforma [A,B,C,i,D,E,F] em [A,B,C,D,i,E,F].

operacao(salta,1) transforma [A,B,C,i,D,E,F] em [A,i,C,B,D,E,F].

operacao(salta,1) transforma [A,B,C,i,D,E,F] em [A,B,C,E,D,i,F].

operacao(salta,2) transforma [A,B,C,i,D,E,F] em [i,B,C,A,D,E,F].

operacao(salta,2) transforma [A,B,C,i,D,E,F] em [A,B,C,F,D,E,i].

operacao(desliza,1) transforma [A,B,i,C,D,E,F] em [A,i,B,C,D,E,F].

operacao(desliza,1) transforma [A,B,i,C,D,E,F] em [A,B,C,i,D,E,F].

operacao(salta,1) transforma [A,B,i,C,D,E,F] em [i,B,A,C,D,E,F].

operacao(salta,1) transforma [A,B,i,C,D,E,F] em [A,B,D,C,i,E,F].

operacao(salta,2) transforma [A,B,i,C,D,E,F] em [A,B,E,C,D,i,F].

operacao(desliza,1) transforma [A,i,B,C,D,E,F] em [i,A,B,C,D,E,F].

operacao(desliza,1) transforma [A,i,B,C,D,E,F] em [A,B,i,C,D,E,F].

operacao(salta,1) transforma [A,i,B,C,D,E,F] em [A,C,B,i,D,E,F].

operacao(salta,2) transforma [A,i,B,C,D,E,F] em [A,D,B,C,i,E,F].

operacao(desliza,1) transforma [i,A,B,C,D,E,F] em [A,i,B,C,D,E,F].

operacao(salta,1) transforma [i,A,B,C,D,E,F] em [B,A,i,C,D,E,F].

operacao(salta,2) transforma [i,A,B,C,D,E,F] em [C,A,B,i,D,E,F].

Conteúdo