IA_Aula04

Prévia do material em texto

*
PUCC
Inteligência Artificial
*
PUCC
Agenda - Aula 04
 Buscas
Largura
Profundidade
Mista
*
PUCC
Espaço de Busca
Muitos problemas de interesse prático possuem ESPAÇO de BUSCA tão grande que não podem ser representados por um grafo explícito.
Elaborações nos procedimentos de busca básicos vistos anteriormente, onde procura-se representar todo o espaço de busca num grafo, tornam-se necessários.
*
PUCC
Elaborações
Três pontos básicos são importantes:
necessitamos ser especialmente cuidadosos em COMO formulamos esses problemas para a busca
devemos ter métodos para representar buscas em grandes grafos de maneira IMPLÍCITA.
Devemos utilizar métodos eficientes para a busca nesses grafos enormes.
*
PUCC
Modelamento = Arte
No problema do empilhamento de blocos não é difícil conceber uma estrutura de dados para representar os diferentes estados do problema e as ações capazes de alterá-los.
Em problemas REAIS, isso é difícil. Requer uma profunda análise do problema
Simetrias
Ignorar detalhes irrelevantes
Encontrar abstrações apropriadas
*
PUCC
Quebra-Cabeças
Jogo de ordenar números. Vamos pensar no de 8 números e um espaço em branco.
Qual um forma interessante de representar esse problema? 
Quantos movimentos são possíveis?
Quantos estados existem?
*
PUCC
Representações
A parte do grafo de Estado que é “encontrável” a partir do estado inicial é representado implicitamente por uma descrição do estado inicial e pela descrição dos efeitos das ações que podem ser tomadas em cada estado.
É possível transformar, a princípio, uma representação implícita de um grafo em uma representação explícita.
*
PUCC
Representações
Para isso, geramos todos os descendentes do nó inicial (aplicando todos os operadores nesse nó) depois aplicamos o mesmo tipo de procedimento para cada um deles.
Como fica o caso do quebra cabeças dos números?
*
PUCC
Representações
Mais formalmente, três componentes básicos para a representação implícita:
Uma descrição através da qual rotulamos o nó inicial. Essa descrição é uma estrutura de dados que modela o estado inicial do ambiente.
Funções de transição de estado. Transforma a descrição do estado atual na descrição do estado resultante após a ação (OPERADORES)
A definição de um objetivo
*
PUCC
Buscas
Existem dois grandes grupos de busca:
não temos nenhuma razão para preferir uma parte do grafo de Estado em relação a outra para a busca do objetivo (buscas sem informações)
temos informações específicas que auxiliam a busca (Heurísticas).
*
PUCC
Buscas sem Informações
Essas buscas aplicam OPERADORES sem o uso de qualquer conhecimento específico especial do domínio do problema.
Esse procedimento gera um grafo de Estado explícito aplicando-se todos os operadores possíveis ao nó inicial, depois aplicando todos os OPERADORES possíveis a todos os sucessores diretos e assim por diante.
*
PUCC
Função Sucessora
Quando aplicada a um nó produz o conjunto total dos nós que podem ser produzidos ao se aplicar todos os operadores possíveis aquele nó.
Cada aplicação dessa função é denominada Expansão de um nó.
*
PUCC
Busca em Largura
Aplique a função sucessora ao nó inicial 
Repita o procedimento para cada nó descendente.
Propriedades
quando o nó alvo é encontrado, encontra-se também o caminho de comprimento mínimo até o objetivo
requer o armazenamento e a geração de uma árvore cujo tamanho é exponencial de acordo com o fator de ramificação da árvore.
*
PUCC
Busca em Profundidade
Gera os sucessores de um nó um de cada vez. Em cada nó existe uma decisão de que operador deve ser aplicado primeiro, qual o próximo e assim por diante.
Uma indicação é deixada em cada nó para indicar que operadores adicionais devem ser aplicados ao nó quando retornamos a ele caso seja necessário.
Backtracking
Limitador de Profundidade
*
PUCC
Busca em Profundidade
A busca em profundidade nos abriga a salvar apenas aquela parte da árvore que está sendo explorada mais as indicações dos nós que ainda não foram expandidos totalmente.
Os requerimentos de memória são portanto lineares com relação ao limitador de profundidade.
Quando encontra o alvo?
*
PUCC
Busca “Mista”
A técnica chamada Aprofundamento Iterativo, (Iterative Deepening) aproveita a linearidade da memória requerida pela busca em profundidade e garante que o nó alvo de menor profundidade é encontrado (como na busca em amplitude).
Nessa técnica, buscas em profundidades sucessivas são realizadas e, em cada uma, o limitante de profundidade é incrementado de 1, até que o nó alvo seja encontrado.
*
PUCC
Aprofundamento Iterativo
*
PUCC
Aprofundamento Iterativo
Calcule o número de nós expandidos para o pior caso em uma busca em árvore com fator de ramificação b e cujo nó alvo mais raso está no nível d e é o último nó a ser gerado nessa profundidade.
Para surpresa, o número de nós expandidos por esse método não é muito maior que o número utilizado pela busca em amplitude.
Qual é a diferença em relação à busca em amplitude?