Aula 3 - Resolução de Problemas - Buscas Desinformadas

Prévia do material em texto

Resolução de 
Poblemas: 
Buscas Desinformadas
PROF. RICARDO P. MESQUITA
Sumário
Resolução de Problemas
Sistemas de Produção
Estratégia de Busca
Busca em Largura (ou Extensão)
Busca de Custo Uniforme
Prof. Ricardo Mesquita 02/14
Resolução de Problemas
O primeiro passo para a resolução de problemas é 
a formulação de objetivos, que é feita de acordo 
com a situação atual e a medida de desempenho 
do agente
A formulação de problemas é o processo de se 
decidir que ações e estados devem ser 
considerados, dado o objetivo a ser alcançado
A resolução de problemas se dá por meio de 
estratégias de busca
Prof. Ricardo Mesquita 03/14
Resolução de Problemas
A tarefa do agente é descobrir que sequência de 
ações o levará a um estado objetivo
Um agente com várias opções imediatas de valor 
desconhecido pode decidir o que fazer examinando 
primeiro as diferentes sequências de ações 
possíveis que levam a estados de valor conhecido 
e, então, escolher a melhor sequência 
Prof. Ricardo Mesquita 04/14
Sistema de Produção
Definido como
◦ Um estado inicial (e um estado final)
◦ Uma descrição das ações possíveis que estão disponíveis 
para o agente, implementada através de uma função 
sucessor (regra de produção)
◦ O estado inicial e a função sucessor definem o espaço de estados
◦ Um teste de objetivo, que determina se um dado estado 
é um estado objetivo
◦ Uma função de custo de caminho, que atribui um custo 
numérico a cada caminho
Prof. Ricardo Mesquita 05/14
Estratégia de Busca
Na busca desinformada não há nenhuma 
informação sobre o problema além de sua 
definição
Existem várias tipos de busca desinformada. As 
mais elementares são:
◦ Busca em Largura
◦ Busca em Profundidade
Prof. Ricardo Mesquita 06/14
Busca em Largura 
(ou Extensão)
BFS (Breadth-First Search)
O nó raiz é expandido primeiro
Todos os sucessores do nó raiz são expandidos
Todos os sucessores desses sucessores são expandidos
E assim por diante.
Prof. Ricardo Mesquita 07/14
Busca em Largura 
(ou Extensão)
Pode ser implementado com um algoritmo de 
busca em árvore
Os nós gerados são armazenados em uma fila FIFO, 
garantindo que sejam visitados em ordem de 
geração
Prof. Ricardo Mesquita 08/14
Busca em Largura 
(ou Extensão)
A busca em largura encontrará uma solução, se 
esta existir
A solução encontrada é ótima
Problemas de grande arborecência podem 
inviabilizar esta estratégia em função da 
necessidade de grande quantidade de memória
Prof. Ricardo Mesquita 09/14
Busca de grande complexidade espacial
Exemplo
O Problema dos Jarros de Água
◦ Suponha que tenhamos 2 jarros de água, um com 
capacidade para 4 litros e outro com capacidade para 3 
litros. Não há qualquer marcação nos jarros que 
possibilite inferir a quantidade de água em seu interior. 
Suponha que há uma fonte com a qual se possa encher os 
vasos e um ralo onde a água pode ser descartada. Como 
devemos proceder para colocarmos exatamente 2 litros 
na jarra de 4 litros?
Prof. Ricardo Mesquita 10/14
Exemplo
Solução
◦ Estabeleça uma base de dados
◦ Qual é o estado inicial?
◦ Como seria um estado final?
◦ Defina a função sucessor (regras de produção) 
◦ Essa função modela bem o que seria o espaço de estados?
◦ Estabeleça um método para testar o objetivo
◦ É possível estabelecer alguma heurística para reduzir o 
espaço de busca?
◦ Defina uma função para calcular o custo do caminho
◦ Esse problema tem custo uniforme?
Prof. Ricardo Mesquita 11/14
Busca de Custo Uniforme
A Busca em Largura é ótima quando os custos de 
todos os passos são iguais, porque sempre se 
expande o nó mais raso não expandido
Na Busca de Custo Uniforme, ao invés de 
expandirmos o nó mais raso, expande-se o nó com 
caminho de custo mais baixo
Obs: se todos os custos forem iguais, essa busca 
será idêntica à busca em largura!
Prof. Ricardo Mesquita 12/14
Exercício
O Problema dos Missionários e Canibais
◦ Três canibais e três missionários estão viajando juntos e chegam à 
margem de um rio. Eles desejam atravessar para a outra margem 
para, desta forma, continuar a viagem. O único meio de transporte 
disponível é um barco que comporta no máximo duas pessoas. Há 
uma outra dificuldade: em nenhum momento o número de canibais 
pode ser superior ao número de missionários pois desta forma os 
missionários estariam em grande perigo de vida. Como administrar a 
travessia?
Prof. Ricardo Mesquita 13/14
Dúvidas?