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