Módulo VI - Busca Heuristica (A)

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/3
 
Busca Heuristica ­ A*
 
A busca A* avalia os nós que combina o custo para alcançar cada nó (g(n)) com o
custo estimado para ir deste nó até o nó Objetivo (h(n)).
Heuristica:  f(n) = g(n) + h(n)
 
Custo mais baixo = f(n) com valor mais baixo
 
Exemplo:
 
 
Neste exemplo, pode­se observar o caminho que a heurística determinou tendo
como base o calculo realizado em cada cidade com o intuito de se obter o melhor
caminho em comparação com o a busca gulosa. A busca poderia ser melhora
levando em consideração o conhecimento do problema em formular uma heurística
mais consistente.
Busca A* ­ Avaliação
• COMPLETA: Sim. Mas somente se a heuristica for admissível
• ÓTIMA: Heuristica adimissivel = heuristica ótima (função ótima)
• TEMPO: O(bm) • ESPAÇO: O(bm), mantem todos os nós na memória
 
Ex: H. Admissivel = Distância entre dois pontos (nós no espaço de estados) sempre é uma reta.
 
 
 
 
 
 
 
Exercício 1:
A busca A* é uma pesquisa em árvore que considera informações globais e locais. A busca A*´somente é
completa se:
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/3
A ­ A heuristica é persistente 
B ­ A heuristica é global 
C ­ A heuristica é local 
D ­ A heuristica é consistente 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
Escolha a alternativa correta referente a heuristicas:
A ­ (1) h(n) = distância de uma curva  (2) h(n) = número de átomos de uma comando SQL (3) h(n) =
Divisão pela velocidade máxima   
B ­ (1) h(n) = distância em linha reta de n até o objetivo mais próximo (2) h(n) = número de átomos da
query (3) h(n) = distância até o objetivo, dividida pela velocidade máxima   
C ­ (1) h(n) = distância em linha reta de n até o objetivo mais próximo (2) h(n) = número de variáveis
(3) h(n) = distância até o nó objetivo 
D ­ (1) h(n) = distância entre dois pontos (2) h(n) = número de diagramas UML (3) h(n) = distância até
o objetivo, dividida pela velocidade máxima   
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
O algoritmo A* pode ser implementado através de uma estrutura de dados do tipo árvore.
juEscolha a alternativa correta que demonstre esta estrutura de dados.
A ­ struct node{ int item; struct node *prox }; 
B ­ struct node{ int item; struct node *esq, *dir }; 
C ­ struct node{ int item; struct node *esq }; 
D ­ struct node{ int item; struct node *dir }; 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 4:
Considere as buscas informadas(Gulosa e A*) e não informadas (Profundidade, Largura)  e analise os itens a
seguir.
I ­ A busca gulosa expande os nós próximos a superfície de maior custo
II ­ A* expande os nós de acordo com a heurística f(n) = g(n) + h(n)
III ­ Busca Gulosa é eficiente na maioria das vezes, mas não garante a escolha de menor custo
IV ­ A complexidade algoritmo da busca A* é exponencial mas pode melhorar de acordo com a heuristica
Estão certos apenas os itens:
 
A ­ I e II 
B ­ II e IV 
C ­ I e IV 
D ­ III e IV 
E ­ II e III 
Comentários:
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 3/3
Essa disciplina não é ED ou você não fez comentários
Exercício 5:
Abaixo encontra­se duas figuras que representam o Estado Inicial e o Estado Final respectivamente para o
problema 8 puzzle. 
Escolha a alternativa correta que informe quantos passos mínimos é possível resolver o problema com a heurística
da distância Manhattan 
e qual busca inteligente esta sendo utiliza.
 
Pasted Graphic.pdf
    Estado Inicial                    Estado Final
 
A ­ N. de passos: 18, busca: A*. 
B ­ N. de passos: 16, busca: gulosa   
C ­ N. de passos: 16, busca: A* 
D ­ N. de passos: 18, busca: gulosa 
E ­ N. de passos: 17, busca: gulosa 
Comentários:
Essa disciplina não é ED ou você não fez comentários