Tópicos em Sistemas
Inteligentes
PUCC
1
Agenda - Aula 04
• Buscas
•Largura
•Profundidade
•Mista
PUCC
2
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 procurase representar todo o espaço de busca num
grafo, tornam-se necessários.
PUCC
3
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
4
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
5
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
6
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
7
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
8
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
9
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
10
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
11
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
12
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
13
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
14
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
15
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
16
Aprofundamento Iterativo
PUCC
17
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?
PUCC
18