Apresentação Sistemas de Produção

Prévia do material em texto

Sistemas de Produção 
Estado: situação em que os objetos se 
encontram em dado instante. 
Estado Inicial: situação dos objetos no início 
do problema. 
Estado Final: situação na qual se deseja por 
os objetos. Como devem estar os objetos 
para que o problema seja resolvido. 
Operações: Transformação de um estado em 
outro. 
Operações 
 
Estado 
Inicial 
 
Estado1 
Estado Final 
(...) 
operação 1 
Sistema de Produção é um formalismo 
computacional que descreve as partes de um 
sistema inteligente: base de dados, operações e 
controle. 
 
 Base de Dados: Estruturas utilizadas para representar os 
estados do problema. 
 
 Regras de Produção: Operações que são aplicadas na 
base de dados. Cada regra tem uma pré-condição que 
quando é satisfeita a regra é aplicável e altera a base de 
dados. 
 
 Sistema de Controle: Escolhe que regra deve ser aplicada 
a cada instante e termina a computação quando a meta é 
atingida. 
Puzzle – 8 Peças 
Puzzle – 8 Peças 
 Espaço de Estados: 181.440 possíveis estados; 
 Estado Inicial: Qualquer estado; 
 Estado Final: Figura ao lado – Goal State; 
 Ações Possíveis: Mover o quadrado vazio para 
 direita, para esquerda, para cima ou para baixo; 
 Custo: Cada passo tem o custo 1, assim o custo 
do caminho é definido pelo número de passos; 
 
 15-puzzle (4x4) – 1.3 trilhões estados possíveis. 
 24-puzzle (5x5) – 10²⁵ estados possíveis. 
Para representar o problema das oito peças 
usamos os conceitos: 
 
 Estado do problema: cada configuração das 8 
peças. 
 Espaço do problema: conjunto de todos os 
estado. 
 Movimentos (operações): transforma um 
estado em outro. 
 Objetivo: estado final. 
Sistema de Controle 
 é a parte de um programa inteligente 
responsável pela seleção das regras dentro 
de um sistema de produção. 
Tipos de estratégias de controle: 
 Irrevogável- Uma regra é selecionada e 
aplicada sem possibilidade de reconsideração. Por 
exemplo: definir uma fórmula que aplicada a 
cada estado devolve um valor a cada estado. 
 Tentativas- (backtracking ou busca em árvore) 
Regras são tentadas até chegar a uma solução. 
Por exemplo: processo usado para resolver o 
problema dos quadros. 
Busca em Árvore 
 Costuma-se representar os estados de 
um problema com o auxílio de diagramas 
em forma de árvores de cabeça para baixo. 
 
 B 
F D C 
G H P Q 
1 2 3 
Fichas 
Problema das fichas 
B B P P 
B B P P B B P P B B P P 
B B P P B P B P B B P P B P B P 
B P B P B P B P B P B P B P B P 
B P P B P B P B B P B P 
s d d s 
d s d s 
d d d d 
s s d 
B B P P 
s = operação 
saltar 
d = operação 
deslizar 
B = ficha branca 
P = ficha preta 
solução é 
apresentada 
por 
linhas grossas na 
árvore 
Torre de Hanói 
 Espaço de Estados: Todas as possíveis 
configurações de argolas em todos os pinos (27 
possíveis estados). 
 Ações Possíveis: Mover a primeira argola de 
qualquer pino para o pino da direita ou da 
esquerda. 
Resolução Torre de Hanói 
Busca em Árvore - Largura primeiro 
 
 
 Examina-se o nó raiz, depois os nós 
separados da raiz por um ramo, 
depois os nós separados da raiz por 
dois ramos e assim por diante . 
Analisando a seguinte árvore: 
 
B 
C D E 
G I 
N M 
H J K 
1 2 3 
4 5 6 7 8 
9 10 
Segundo o processo já descrito o computador terá que efetuar a 
busca do estado final nos seguintes níveis: visita-se B (nó raiz), 
visita-se C, D, E (nível 1), depois visita-se G, H, I, depois J e K, 
e por último visita-se N e M. Suponhamos que a meta seja o nó H. 
 Cada trajetória pode ser representada por 
uma lista de estruturas do tipo r(R,N), 
onde R é o ramo (operação) que liga o nó 
N (estado) ao pai dele. 
 
Digamos que o nosso objetivo é o nó 
H: