ia4 Busca em Largura

Prévia do material em texto

Inteligência Artificial
Busca em Largura 
Aula 4 
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
1
Algoritmos de Busca são técnicas de Inteligência Artificial aplicadas a problemas de alta complexidade teórica que não são resolvidos com técnicas de programação convencionais, principalmente as de natureza puramente numérica;
 A "complexidade" de um problema está diretamente relacionada ao tamanho do seu "Espaço de Busca" correspondente.
Algoritmos de Busca
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
2
Completude (completeza):
a estratégia sempre encontra uma solução quando existe alguma?
Custo do tempo:
quanto tempo gasta para encontrar uma solução?
Critérios de Avaliação das Estratégias de Busca
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
3
 Custo de memória:
quanta memória é necessária para realizar a busca?
Qualidade/eficiência (optimality):
a estratégia encontra a melhor solução quando existem soluções diferentes?
menor custo de caminho
Critérios de Avaliação das Estratégias de Busca
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
4
Como procurar a solução de um problema?
Busca cega (ou exaustiva)
Não sabe qual o melhor nó da fronteira a ser expandido = menor custo de caminho desse nó até um nó final (objetivo)
Estratégias de Busca (ordem de expansão dos nós):
caminhamento em largura
caminhamento em profundidade
... e suas variações
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
5
Direção de Busca:
Do estado inicial para o objetivo (forward chaining)
Do objetivo para o estado inicial (backward chaining)
Ambos ao mesmo tempo (bidirecional)
Como procurar a solução de um problema?
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
6
Busca cega (ou exaustiva)
Estratégias
Busca em largura
Busca em profundidade
Busca com custo uniforme
Busca com profundidade limitada
Busca com aprofundamento iterativo
Como procurar a solução de um problema?
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
7
Busca cega (ou exaustiva)
Busca em largura
Ordem de expansão dos nós:
	1. Nó raiz
	2. Todos os nós de profundidade 1
	3. Todos os nós de profundidade 2, etc…
Como procurar a solução de um problema?
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Partindo de um vértice inicial, ela explora todos os vértices vizinhos. Em seguida, para cada vértice vizinho ela repete esse processo, visitando os vértices ainda inexplorados.
8
A busca cega não possui estimativas sobre qual sucessor é mais promissor para atingir a meta.
Fronteira: todos os nós gerados e ainda não expandidos (ou visitados) da árvore de busca.
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
9
Busca cega (ou exaustiva)
Busca em largura
Encontra a solução de menor custo de caminho
É completa sempre e ótima se condição 1 é satisfeita
	Condição 1: 
	n’,n 	profundidade(n’)  profundidade(n)  
		custo de caminho(n’)  custo de caminho (n)
Obs: sempre é a solução geral mais barata, devido ao custo de busca associado
Como procurar a solução de um problema?
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
10
Ordem de expansão dos nós:
1. Nó raiz
2. Todos os nós de profundidade 1
3. Todos os nós de profundidade 2, etc…
Fronteira = FIFO (first-in-first-out) 
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
11
Exemplo: Jogo dos 8 números
4
5
8
1
6
7
3
2
5
8
4
1
6
7
3
2
4
5
8
7
1
6
3
2
4
5
8
6
7
3
2
1
cima
baixo
direita
1
2
3
4
6
7
8
5
baixo
direita
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
12
Busca cega (ou exaustiva)
Busca em largura
Custo de memória: A fronteira do espaço de estados deve permanecer na memória
é um problema mais crucial do que o tempo de
execução da busca
Como procurar a solução de um problema?
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
13
Esta estratégia só dá bons resultados quando a profundidade da árvore de busca é pequena.
Exemplo:
fator de expansão b = 10
1.000 nós gerados por segundo
cada nó ocupa 100 bytes
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
14
Ordem de expansão dos nós:
	1. Nó raiz
	2. Todos os nós de profundidade 1
	3. Todos os nós de profundidade 2, etc…
Algoritmo:
	função Busca-em-Largura (problema) 
		retorna uma solução ou falha
 
 Busca-Genérica (problema, Insere-no-Fim)
Busca em Largura
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
15
Busca em Largura - Exercício
Imagine um labirinto que contenha as seguintes alternativas de caminho:
 
Z
C
D
E
I
J
H
G
B
Destino: ponto “B”
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Z
C
D
E
I
J
H
G
B
Z
C
D
H
E
I
J
G
B
Busca em Largura – Solução do Exercício
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Considere o seguinte grafo:
O custo do caminho de um nó para outro está indicado pelo número associado a cada arco/aresta. 
Considerando que pretende-se ir do nó A ao nó G com o menor custo, determine o caminho solução obtido após aplicada a estratégia de busca em largura.
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Inteligência Artificial
Prof Robson do Nascimento ‹nº›
Profundidade
Nós
Tempo
Memória
0
1
1 milissegundo
100 bytes
2
111
0.1 segundo
11 quilobytes
4
11111
11 segundos
1 megabytes
6
106
18 minutos
111 megabytes
8
108
31 horas
11 gigabytes
10
1010
128 dias
1 terabyte
12
1012
35 anos
111 terabytes
14
1014
3500 anos
11111 terabytes