Embed Size (px)
Citation preview
SMA*Fernando Simeone
Mestrado em Ciência da Computação Universidade Federal de Lavras
!Projeto e Análise de Algoritmos (2014/2)
Tópicos • Introdução
• O algoritmo
• Desempenho
• Considerações finais
• Referências
Introdução
Introdução
Introdução• O problema de memória do algoritmo A*;
Introdução• O problema de memória do algoritmo A*;
• SMA* (Simplified Memory-Bounded);
Introdução• O problema de memória do algoritmo A*;
• SMA* (Simplified Memory-Bounded);
• Principais dificuldades:
Introdução• O problema de memória do algoritmo A*;
• SMA* (Simplified Memory-Bounded);
• Principais dificuldades:
• Garantir a solução ótima;
Introdução• O problema de memória do algoritmo A*;
• SMA* (Simplified Memory-Bounded);
• Principais dificuldades:
• Garantir a solução ótima;
• Evitar expansão repetida de nós esquecidos.
Introdução• O algoritmo estima o custo de uma solução
A
B
C
D
E
G H
K
10
10
10
10
10
8
8
168
8
f(n) = g(n) + h(n)
O algoritmo
EntradasSMA*(grafo, v_inicial, v_final)
A
B
C
D
E
G H
K
10
10
10
10
10
8
8
168
8
HeurísticaDistância mínima entre dois pontos:
A
B
C
D
E
G H
K
10
10
10
10
10
8
8
168
8
12
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12A
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12A
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12A
n
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12
n
A
B10 + 5 = 15
s
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12
n
A
B15
s
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
12
n
A
B15
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
A
B G
1215
s
8 + 5 = 13
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila A G B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
A
B G
1315
s
13
(15)
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
A
A
G
13 (15)
n
13
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
s
A
G
H
13 (15)13
+∞
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B H
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
s
A
G
H
13 (15)
+∞
13 (∞)
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B H
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
A
G
13 (15)
13 (∞)
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B H
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
s
A
G
D
13 (15)
13 (∞)
24 + 0 = 24
SMA* (grafo, v_inicial, v_final) 1 adicionar v_inicial na fila 2 loop do 3 if fila está vazia return falha 4 n = nó mais profundo de menor custo na fila 5 if n == v_final return sucesso 6 s = próximo sucessor de n 7 if s != v_final and está na maxima profundidade 8 f(s) = +∞ 9 else 10 f(s) = max( f(n), g(s) + h(s) )
11 if todos sucessores de n gerados 12 atualizar custo dos ancestrais de n 13 if todos os sucessores de n estão na memória 14 remover n da fila 15 if memoria está cheia 16 deletar nó mais raso com maior custo 17 removê-lo da lista de sucessores de seu pai 18 inserir seu pai na fila, se necessário 19 20 inserir s na fila 21 end
O algoritmo
Fila G B D H
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Sucessores
An
s
A
G
D
13 (15)
24 (∞)
24
O algoritmo
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
O algoritmo
A
B G
13 (15)15 24 (∞)
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
O algoritmo
A
B G
13 (15)15 24 (∞)
A
B
C
15
∞
13 (24)
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
O algoritmo
A
B G
13 (15)15 24 (∞)
A
B
C
15
∞
13 (24)
A
B
D
13 (24)20
20
A
B
C
D
E
G H
K
10
10
10
10
10
88
168
8
Desempenho
Desempenho
Nós expandidos X memória
Desempenho
Nós expandidos X memóriaCom +/- 32% da memória gasta pelo A* consegue efetuar o mesmo número de expansões
Considerações Finais
Considerações Finais A
B G
C D
E D
H D
D K
Considerações Finais • Solução deve caber na memória;
A
B G
C D
E D
H D
D K
Considerações Finais • Solução deve caber na memória;
• Consequentemente, nem sempre a solução será ótima;
A
B G
C D
E D
H D
D K
Considerações Finais • Solução deve caber na memória;
• Consequentemente, nem sempre a solução será ótima;
• Utiliza no máximo a memória gasta pelo A*;
A
B G
C D
E D
H D
D K
Considerações Finais • Solução deve caber na memória;
• Consequentemente, nem sempre a solução será ótima;
• Utiliza no máximo a memória gasta pelo A*;
• Quando houver memória para armazenar toda a árvore, executará otimamente eficiente;
A
B G
C D
E D
H D
D K
Considerações Finais • Solução deve caber na memória;
• Consequentemente, nem sempre a solução será ótima;
• Utiliza no máximo a memória gasta pelo A*;
• Quando houver memória para armazenar toda a árvore, executará otimamente eficiente;
• Em uma implementação real, há outros pontos a serem considerados.
A
B G
C D
E D
H D
D K
Referências
Russell, S. (1992). Efficient memory-bounded search methods. In Proceedings of the 10th European Conference on Artificial Intelligence, ECAI ’92, pages 1–5, New York, NY, USA. John Wiley & Sons, Inc.!!Russell, S. J. and Norvig, P. (2003). Artificial intelligence: A modern approach. pages 101–111. Pearson Education, 2 edition.!!
ObrigadoDúvidas?
