IA_Aula05

Prévia do material em texto

*
PUCC
Inteligência Artificial
*
PUCC
Agenda - Aula 05
 Buscas 
Heurísticas
*
PUCC
Função de Avaliação
O processo de busca que vamos estudar é parecido com o de busca em amplitude, exceto pelo fato de não ser uniforme a partir do nó inicial. Ao invés disso, ele dá preferência para determinados nós onde informações específicas do problema indicam que eles podem levar a soluções melhores.
Esses processos são chamados BUSCAS HEURÍSTICAS
*
PUCC
Idéia Básica
1. Temos uma função de avaliação, função heurística ĥ, a qual ajuda a decidir qual nó é o melhor para ser expandido.
Valores menores dessa função são melhores
Esta função é baseada em informações específicas do domínio do problema.
2. Expanda o nó n que possui o menor valor de ĥ(n). Empates são resolvidos arbitrariamente.
3. Termine quando o nó a ser expandido é o nó ALVO.
*
PUCC
Quebra Cabeças
Qual seria uma função heurística adequada?
Tendo como nó inicial o estado abaixo, desenho o grafo resultante da aplicação da sua função heurística.
 
 2 8 3
 1 6 4
 7 b 5
*
PUCC
Função Melhorada
Este exercício mostra que devemos influenciar a busca em favor de retornos para explorar passos anteriores a fim de prevenir buscas muito profundas.
Então podemos alterar a nossa função para levar em conta a profundidade do nó:
				 ĥ: ĥ(n)= ĝ(n) + ŝ(n)
	onde: ĝ(n) é a profundidade do nó no grafo
	 ŝ(n) avaliação heurística do nó n
 (número de peças fora do lugar)
*
PUCC
Função Avaliação
Duas questões importantes:
Como devemos escolher funções de avaliação para guiar as buscas heurísticas que utilizam o melhor primeiro?
Esse tipo de busca sempre nos leva a resultados interessantes? Quais são suas propriedades?
*
PUCC
Algoritmo de Busca em Grafo
1. Crie uma árvore que possui somente o nó inicial, n0. Coloque n0 numa lista ordenada chamada ABERTA.
2. Crie a lista FECHADA - vazia
3. Se ABERTA estiver vazia - erro
4. Selecione o primeiro nó de ABERTA, tire ele de lá e coloque em FECHADA. Chame este nó n.
5. Se n é o nó alvo PARE. Encontre o caminho da árvore de n para n0.
6. Expanda n. Coloque o conjunto de sucessores na árvore criando arcos de n para cada sucessor. Coloque todos os sucessores em ABERTO.
7. Reordene ABERTO de acordo com algum critério.
8. Volte para 3.
*
PUCC
Algoritmo A*
Vamos particularizar o algoritmo anterior fazendo uma ordenação, no passo 7, dos nós que estão na lista ABERTA, para valores crescentes da função ĥ. Vamos chamar esse algoritmo de A*.
Seja s(n), o custo real do caminho mínimo entre o nó n e um nó alvo (calculado para todos os nós alvos e todos os caminhos possíveis entre n e eles) 
*
PUCC
Algoritmo A*
Seja g(n), o custo do caminho mínimo entre o nó inicial n0 e o nó n.
Então, h(n)= g(n)+s(n) é o custo do menor caminho entre o nó inicial n0 e um nó ALVO com a restrição de que esse caminho passe por n. 
Note que h(n0)= s(n0) é o caminho mínimo irrestrito.
*
PUCC
Algoritmo A*
Para cada nó n, seja ŝ(n) uma estimativa de s(n) e ĝ(n) o menor custo encontrado por A* para chegar a n.
Para o algoritmo A* nós utilizamos:
 ĥ(n)= ĝ(n) + ŝ(n)
Onde ^ significa estimativa
*
PUCC
Algoritmo A*
Como funcionaria o algoritmo de busca no caso de não estarmos trabalhando com uma árvore e sim com um grafo? Isto é, existe mais de uma seqüência de ações que levam ao mesmo estado partindo do estado inicial.]
*
PUCC
Algoritmo A*
Existem condições sobre o grafo e sobre s as quais garantem que o A* encontra a solução ótima:
Cada nó do grafo tem que ter um número finito de sucessores
Os arcos tem que ter custo positivo
Para todos os do grafo: s(n) <= s(n) 
^
^
*
PUCC
Algoritmo A* Iterativo
Redução do uso de memória grande mas muitas vezes não suficiente.
Método Iterativo: executar uma série de buscas em profundidade. Pode ser realizada em paralelo.
	1.) estabeleça um custo de corte inicial: h(n0)= g(n0)+s(n0)
				h(n0) = s(n0)
	2.) Melhor situação esse é o valor do ótimo. s(n0)<=s(n0)
	3.) Backtracking: sempre que h(n) > custo de corte
	4.) Se encontrou o ALVO solução ótima. Se não: custo da solução ótima maior que o custo de corte.
 5.) Custo de corte= menor h de nó não expandido.
^
^
^
^
^
^
^
^