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.

A* (revisando)

F(n)=g(n) + h(n)

Heurística: linha reta

Distância exata já percorrida

140

KM

A*

A*

A*

A*

Solução ótima

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)

Busca de aprofundamento iterativo (revisando)

AIA* define Contornos

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)

AIA* - < 420

A*

A*

AIA* - < 420

Solução ótima

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

BRPM Arad

Sibiu Arad

Fagaras Oradea R. Vilcea

Pitesti Sibiu

366

393

415

526

417

447

413

553

BRPM Arad

Sibiu Arad

Fagaras Oradea R. Vilcea

Pitesti Sibiu

366

393

415

526

417

447

413

553

BRPM Arad

Sibiu Arad

Fagaras Oradea R. Vilcea

366

393

415

526

447

417

Sibiu Bucareste

591

450

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)