2 3 Resolução de Problemas Custo Uniforme

Prévia do material em texto

04/03/2015
1
Inteligência Artificial 
Aula: 
Resolução de Problemas
Busca Cega 
Custo Uniforme
DECOM/UFOP
Custo em Ações (arestas)
BFS não é ótimo: caminho de custo mínimo tem 5 arestas e o mais raso
4 arestas.
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9 2
81
8
2
3
1
4
4
1
5
1
3
2
2
04/03/2015
2
Custo Uniforme
3
Busca de Custo Uniforme
(ou mais barato primeiro)
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
Estratégia: Expanda o nó de custo mínimo
primeiro
Fronteira: fila de prioridade
Nó deve conter o custo do caminho.
S
G
d
b
p
q
c
e
h
a
f
r
3 9 1
164
11
5
713
8
1011
17 11
0
6
3
9
1
1
2
8
8 2
15
1
22
3
4
04/03/2015
3
UCS
• Completo? Garante que acha solução se existe?
• Ótimo? Garante achar o caminho de menor custo?
• Complexidade de tempo?
• Complexidade de espaço?
Variáveis:
n Número de estados (representação)
b Fator médio de ramificação
(número médio de sucessores - expansão)
C* Custo da solução ótima
d Profundidade da solução mais curta
m Maior profundidade da árvore
5Inteligência Artificial
UCS: Avaliação
Algoritmo Completo Ótimo Tempo Espaço
DFS S N
BFS S S
UCS custo > 0 S S
…
b
C*/ε
camadas
O(bd) O(bd)
O(bC*/ε) O(bC*/ε)
O(bm) O(bm)
04/03/2015
4
Algoritmo UCS
7Inteligência Artificial
Exercício
8BCC 325/2012-2
04/03/2015
5
Para onde ir?
• O bacana: 
▫ UCS é completa e ótima!
• O ruim:
▫ Explora opções em todas as 
direções
▫ Não leva em conta
localização do alvo
▫ Exponencial em tempo…
▫ Exponencial em espaço?
Início Objetivo
…
c ≤ 3
c ≤ 2
c ≤ 1