Resolução de Problemas
Sistemas de Produção
Prof. Cláudio M. N. A. Pereira
Sumário
1. Espaço de Estados
2. Jogo das 8 peças
3. Grafos de Estado
4. Sistemas de Produção
5. Técnicas de Busca
Espaços de Estados
Na abordagem de solução de problemas através do Espaço de Estados, considera-se
um estado inicial (condição de partida) e deseja-se chegar a um estado final, através
da aplicação de um conjunto de operações de transformação de estados.
Um Espaço de Estados contêm todos os possíveis estados que o problema pode
assumir, dadas as operações de transformações de estados disponíveis.
Estado
Inicial
Operações de
transformação de estados
Estado
Final
O Jogo das 8 Peças
Considere o Jogo das 8 peças, onde a partir de uma dada configuração (ou estado)
inicial, deseja-se atingir uma configuração final, movimentando-se as peças de um
tabuleiro, conforme exemplo abaixo.
5 7 4
Sequência de
movimentos
1 2 3
8 2
8
3 6 1
7 6 5
Estado Inicial
4
Estado Final
O Jogo das 8 Peças
Dados os estados inicial e final, deseja-se descobrir a sequência de movimentos
(operações de transformação de estado) a ser executada.
Para tal, poderíamos definir uma Estratégia de Busca que utiliza-se de forma
sistematizada as possíveis operações em cada estado (situação) do jogo.
5 7 4
Movimento 2
Movimento 1
5 7 4
8 2
3 6 1
Estado Inicial
8
2
1 2 3
3 6 1
8
5 7 4
Estado 1
8 6 2
3
1
Estado 2
4
7 6 5
Estado Final
Grafo de Estados
É uma forma de representação
gráfica do espaço de estados,
onde os vértices são os estados e
as arestas são as operações de
transformação.
5
7
8
3
5
7
4
8
6
2
3
1
6
5
7
8
2
3
6
1
4
5
7
4
5
7
2
8
2
1
8
2
4
1
3
6
3
6
1
5
7
4
8
2
1
...
3
4
6
...
Sistemas de Produção
São técnicas de solução de problemas baseadas na manipulação de regras (operações)
de transformação de estado.
Um Sistema de Produção é composto basicamente por:
- Uma base de dados que representa os diversos estados que o problema pode
assumir;
- Um conjunto de regras ou operadores que modificam os estados;
- Um mecanismo de controle que define uma maneira sistemática para aplicação das
regras
Sistemas de Produção
Exemplo: Jogo das 8 peças
- Base de dados:
Matriz 3x3 com inteiros de 0 a 8 onde o 0 simboliza o espaço vazio
5 7 4
8 2 0
3 6 1
Sistemas de Produção
Exemplo: Jogo das 8 peças
- Regras ou operadores:
Pode-se abstrair a movimentação do espoaço em branco (zero).
Assim, poderíamos usar apenas 4 regras.
R1: 0 para cima
R2: 0 para baixo
R3: 0 para direita
R4: 0 para esquerda
Sistemas de Produção
Exemplo: Jogo das 8 peças
- Sistema de controle
1. Inicializa BD com configuração inicial
2. Inicializa condição de término com configuração final
3. Até que a BD seja igual a condição de término, faça
3.1. Selecione a regra a ser aplicada
3.2. Aplique a regra, alterando BD
3.3. Guarde a regra aplicada em uma lista
4. Fim. A solução é a lista de regras.
Sistemas de Produção
A seleção da regra
As formas de se selecionar as regras podem ser desde o
simples estabelecimento de uma ordem ( Ex: R1, R2, R3,
R4) até a utilização de heurísticas (conhecimento que
norteia o processo de busca).
Sistemas de Produção
Estratégias de busca:
- Busca em profundidade com “backtracking”
- Busca em largura
- Busca com heurísticas
Sistemas de Produção
Busca em profundidade com “backtracking
Aplica-se sempre a primeira regra disponível (regra da vez).
Caso sejam encontrados cenários (estados) inválidos ou
repetidos, volta-se ao ponto anterior e aplica-se a próxima regra
5
7
8
2
3
6
4
Sistemas de Produção
1
R1
R1
Estado
Inexistente
5
7
8
2
4
3
6
1
R2
Estado
Repetido
R3
Busca em profundidade com “backtracking
R1: 0 para cima
R2: 0 para baixo
R3: 0 para direita
R4: 0 para esquerda
R4
Estado
Inexistente
R1
Estado
Inexistente
5
7
8
2
4
3
6
1
R2
5
2
4
8
3
7
6
1
R1
Sistemas de Produção
Busca em largura
Aplica-se todas as regras em cada nó.
Despreza-se os vértices repetidos mais longe da raíz.
R1
Estado
Inexistente
7
8
2
3
6
R2
7
8
2
3
6
1
R2
7
8
2
3
6
Busca em largura
4
1
R3
5
7
4
4
8
2
1
1
3
6
Estado
Inexistente
3
R1
5
7
5
6
7
4
5
7
6
2
8
2
1
3
6
4
8
7
2
8
3
6
1
3
6
1
3
...
...
1
R4
R3
5
2
4
2
4
8
...
7
R2
...
Estado
Inexistente
5
8
R4
R3
5
Sistemas de Produção
4
R4
R1
5
5
4
1
5
3
7
4
8
2
6
1
...
Sistemas de Produção
Busca com heurística
Uma heurística é um conhecimento que pode nortear o processo
de busca, provendo uma forma de avaliar as regras e aplicar a
que seja mais interessante.
Sistemas de Produção
Uma heurística para o jogo das 8 peças:
Um exemplo de heurística no caso do jogo das 8 peças poderia
ser:
- Escolha a regra que faz com que mais peças fiquem na posição
final desejada.
Sistemas de Produção
7
8
2
3
6
7
8
2
3
6
Uma heurística para o jogo das 8 peças:
4
1
R4
R1
5
5
R3
R2
5
7
4
4
8
2
1
1
3
6
Estado
Inexistente
5
7
8
3
4
2
6
1