Resolução de problemas por meio de algoritmos de busca
Busca heurística
Universidade Estadual do Oeste do Paraná
Curso de Bacharelado em Ciência da Computação
Inteligência Artificial
Roteiro
Retomada do A*
AIA*: A* de aprofundamento interativo
BRPM : Busca Recursiva pelo Melhor
LMSA*: A* Limitado pela Memória
A* (Revisão)
A* é o algoritmo mais conhecido dentro da classe
dos algoritmos de “busca pela melhor escolha”;
Ele avalia nós combinando:
g(n) : o custo para alcançar o nó, ou seja, o custo do
caminho desde o nó inicial até o nó n;
h(n) : o custo para ir do nó até o objetivo, ou seja, o custo
estimado do caminho de custo mais baixo desde n até o
objetivo (distância em linha reta).
Então: f(n) = g(n) + h(n)
A*
A* será ótimo se for utilizada uma heurística
admissível, ou seja, desde que nunca
superestime o custo para alcançar o objetivo –
nunca tenha uma heurística mais custosa do que
uma solução.
O exemplo de heurística admissível é a distância
em linha reta, ou seja, toma-se como heurística um
percurso menor que a realidade.
Comentários sobre A*
Durante a busca, os nós são inseridos em uma lista
que deve ser ordenada de acordo com o custo total
dos nós, que são mantidos na memória.
Assim, geralmente A* esgota o espaço bem antes
de esgotar o tempo.
Portanto, A* não é prático para muitos problemas de
grande escala.
Outras buscas
Alguns algoritmos foram propostos visando
superar o problema do espaço sem sacrificar o
caráter ótimo, buscando também um custo menor
no tempo de execução.
Buscas heurísticas
Alguns desses algoritmos são (Russell e Norvig,
cap. 4 pg. 94 e seguintes):
AIA*: A* de Aprofundamento Interativo
BRPM : Busca Recursiva pelo Melhor
LMSA*: A* Limitado pela Memória
Busca heurística Limitada pela Memória
AIA* (A* de aprofundamento interativo)
O caminho mais simples para reduzir requisitos de memória de A* é adaptar a ideia de aprofundamento iterativo ao contexto de busca heurística, resultando no algoritmo A* de aprofundamento iterativo AIA*.
A cada interação, o valor de corte é o menor custo de f de qualquer nó que tenha excedido o corte na interação anterior.
Busca de aprofundamento iterativo (revisando)
Esta estratégia tenta limites com valores
crescentes, partindo de zero, até encontrar a
primeira solução
fixa profundidade = i, executa busca
se não chegou a um objetivo, recomeça busca com
profundidade = i + n (n qualquer)
AIA*
No caso da busca de custo uniforme, as faixas serão circulares em torno do estado inicial.
Com heurísticas mais precisas, as faixas se alongarão em direção ao estado objetivo e se tornarão mais estreitamente concentradas em torno do caminho ótimo.
C*= custo do caminho da solução ótima Ex.: 420
AIA* expande todos os nós com f(n) < C*, onde f(n)=g(n) + h(n)
Busca heurística com limite de memória
BRPM – Busca recursiva pelo melhor
Algoritmo recursivo que tenta limitar a operação de busca pela melhor escolha.
É um pouco mais eficiente que AIA*, mas retém todas as informações em memória.
Semelhante a busca recursiva em profundidade;
Diferença: controla a recursão pelo valor de f. Se existir algum nó em um dos ancestrais que ofereça melhor estimativa que o nó atual, a recursão retrocede e a busca continua no caminho alternativo.
BRPM Arad
Sibiu Arad
Fagaras Oradea R. Vilcea
Pitesti Sibiu
366
393
450
526
417
447
417
553
Bucareste R. Vilcea
418 607
A* Limitado pela memória simplificado (LMSA*)
O LMSA* prossegue exatamente com A*,
expandindo a melhor folha até completar a
memória (utiliza toda a memória disponível);
Quando a memória está cheia, ele elimina o pior nó
folha (maior custo de f) para continuar a busca.
Nesse ponto, ele não poderá adicionar um novo nó
à árvore de busca sem descartar um nó antigo.
A* Limitado pela memória simplificado (LMSA*)
Diferença: o LMSA* sempre descarta o pior nó de
folha (com pior valor de f);
LMSA* copia o valor do nó esquecido em seu pai.
Desse modo, o ancestral de uma sub árvore
esquecida conhece a qualidade do melhor
caminho nessa sub árvore.
Com essas informações, o LMSA* só regenera a
sub árvore quando todos os outros caminhos se
mostram piores que o caminho esquecido.
A* Limitado pela memória simplificado (LMSA*)
É completo, se a profundidade do nó objetivo mais raso for menor que o tamanho da memória.
É ótimo se qualquer solução ótima for alcançável.
Atividade com trabalho prático Proposta de trabalho:
Nomes (individual ou em dupla)
Descrição do problema (enunciado)
Identificação dos algoritmos de busca cega a serem implementados Amplitude/largura; profundidade; profundidade limitada; profundidade
de custo uniforme; aprofundamento iterativo; Busca bidirecional; outro??
Identificação dos algoritmos de busca informada a serem implementados
Guloso, A*, AIA,*BRPM, LMSA, Outro?
Avaliação de desempenho Comparação em termos de Tempo, Memória, Outro?
Proposta de prazo Quando (considerando disponibilidade de aulas de IA)?
Referências
RICH, ELAINE, KNIGHT, KEVIN, 1993.
Inteligência Artificial. São Paulo: McGrw-Hill
RUSSEL, S.; NORVIG, P.; 1995. Inteligência
Artificial. 3. ed. Rio de Janeiro: Campus, 2003.
RABUSKE, R. Inteligência Artificial. Florianópolis:
Editora da UFSC, 1995.
GUDWIN, R. Representação e solução de
problemas. São Paulo: Unicamp, sd. (lâminas)