2 Resolução de Problemas Decomposição

Prévia do material em texto

Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 1
Princípio
Decompõe o problema original em subproblemas de complexidade menor 
e estes também são decompostos até não ser mais possível continuar.
Modelagem
� Descrição do problema inicial.
� Conjunto de operações de transformação de problemas.
� Conjunto de problemas primitivos (problemas que têm solução 
imediata, conhecida).
Solução
Conjunto de problemas primitivos encontrado durante a busca
Decomposição de Problemas
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 2
Problemas Conjuntivos
São decompostos em subproblemas em que todos devem compor a solução
final.
Problemas Alternativos
São decompostos em subproblemas em que apenas um deve compor a
solução final.
Busca de soluções
A busca é efetuada em um grafo (árvore) E/OU.
Os nodos “E” possuem apenas filhos contendo subproblemas conjuntivos e
são representados por uma elipse unindo os arcos de saída do nodo.
Os nodos “OU” possuem apenas filhos contendo subproblemas
alternativos e seus arcos não possuem elipse.
Tipos de Problemas e Busca
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 3
Espaço de Busca: Árvore E/OU
Legenda: = Problema Primitivo
= Problema sem Solução (NodoTerminal)
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 4
Um nodo é solúvel se:
� É um problema primitivo.
� É um nodo "E" cujos sucessores são todos solúveis.
� É um nodo "OU" onde pelo menos um dos sucessores é solúvel
Um nodo é insolúvel se:
� É um nodo terminal. 
� É um nodo "E" onde pelo menos um dos sucessores é insolúvel.
� É um nodo "OU" cujos sucessores são todos insolúveis.
Solubilidade dos nodos
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 5
Busca em Profundidade em Árvore E/OU
1
2
3 8
12
4 5
6 7
10
11
9
Legenda: = Problema Primitivo
= Problema sem Solução (NodoTerminal)
Os nos nos nodos indicam 
a ordem em que foram 
expandidos / visitados
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 6
Busca em Extensão em Árvore E/OU
1
2 3
4 5 7
128 9 1110
Legenda: = Problema Primitivo
= Problema sem Solução (NodoTerminal)
Os nos nos nodos indicam 
a ordem em que foram 
expandidos / visitados
6
13
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 7
Definição do problema
Qual é o tamanho da pilha de discos?
Qual é pino de origem?
Qual é o pino de destino?
Modelagem da Torre de Hanói
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 8
Definição do problema - problemas primitivos?
Modelagem da Torre de Hanói
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 9
Uma Linguagem de Representação de Problemas
Sintaxe: [<tamanho da pilha>, <pino de saída>, <pino de chegada>]
Problema inicial: [3,1,3]
Problemas primitivos: [ 1, <pino de saída>, <pino de chegada>]
Uma Linguagem de Operadores de Decomposição 
Para diferentes pinos I, J e K, o problema de mover uma pilha de discos 
de tamanho n, onde n>1, do pino I para o pino K pode ser substituído por 3 
subproblemas (conjuntivos):
• Mover uma pilha de tamanho n-1 de I para J.
• Mover uma pilha de tamanho 1 de I para K.
• Mover uma pilha de tamanho n-1 de J para K.
Modelagem da Torre de Hanói
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 10
Uma Linguagem de Operadores de Decomposição 
Para diferentes pinos I, J e K, o problema de mover uma pilha de discos 
de tamanho n, onde n>1, do pino I para o pino K pode ser substituído por 3 
subproblemas (conjuntivos):
• Mover uma pilha de tamanho n-1 de I para J.
• Mover uma pilha de tamanho 1 de I para K.
• Mover uma pilha de tamanho n-1 de J para K.
Modelagem da Torre de Hanói
Resolução de Problemas -DECOM – ICEB – UFOP Prof. Álvaro Guarda 11
[3,1,3]
[2,1,2] [2,2,3] [1,1,3]
[1,1,3] [1,3,2] [1,1,2] [1,2,1] [1,1,3] [1,2,3]
Grafo E / OU para a Torre de Hanói
Solução: Conjunto de todos os problemas primitivos encontrados