FGA0221 – Inteligência
Artificial
Resolvendo problemas por busca
continuação
Algoritmos de Busca
Estratégias de pesquisa cega (cont.)
➢Um algoritmo de busca cega não recebe nenhuma pista sobre o quão próximo
um estado está do(s) objetivo(s);
➢Como resolver o problema se as ações tiverem custos diferentes e não
soubermos os custos de cada ação?
Uniform-cost search
➢Usa best-first Search onde a função de avaliação é o custo do caminho da raiz até
o nó atual;
➢Exemplo: Sibiu para Bucharest
➢ Sibiu-Fagaras-Bucharest: Custo = 310;
➢ Sibiu-Rimicu Vilcea-Pitesti-Bucharest: Custo = 278
Uniform-cost search
Uniform-cost search
➢Exemplo 2: partir de S para G, qual o menor caminho?
Uniform-cost search
➢Exemplo 2: partir de S para G, qual o menor caminho?
Uniform-cost search
➢É ótimo;
➢É completo;
➢a complexidade de tempo e espaço do pior caso do algoritmo é
Onde é o custo da solução ótima e é o menor valor de custo onde ;
Esse custo pode ser muito maior que .
Depth-first search
➢Sempre explora o nó mais profundo primeiro;
➢Pode ser implementado como uma chamada ao Best first search onde a função f
é valor negativo da profundidade;
➢Não é ideal em termos de custo; ele retorna a primeira solução encontra, mesmo
que não seja a de menor custo;
➢Pode ficar preso a um loop infinito se houverem loops;
➢Pode ficar preso em um caminho infinito;
➢Utiliza muito menos memória;
Depth-first search
➢Complexidade de memória: onde b é a quantidade de ramificações e m é
a profundidade;
➢A complexidade de tempo é proposicional à quantidade de estados;
Depth-first search
Depth-first search
➢Exemplo:
Depth-first search
➢Exemplo:
Estratégias de pesquisa cega
➢Outros algoritmos de procura cega:
➢Depth-limited search – Limita a profundidade da procura;
➢Iterative deepening search – Testa várias profundidades até encontrar a solução;
➢Bidirectional search – Procura simultaneamente pelo estado inicial e pelo estado
objetivo;
Estratégias de pesquisa cega
Estratégias de pesquisa informadas
➢Usa dicas específicas de domínio sobre a localização das metas;
➢Pode encontrar soluções com mais eficiência do que uma estratégia
desinformada;
➢As informações vêm na forma de uma função heurística h(n);
➢h(n) = custo estimado do caminho mais econômico do estado no nó n para um
estado objetivo.
Estratégias de pesquisa informadas
➢Por exemplo, em problemas de localização de rotas, podemos estimar a distância
do estado atual até um objetivo calculando a distância em linha reta no mapa
entre o objetivo e todos os outros pontos;
Greedy best-first search
➢é uma forma de busca que expande primeiro o nó com o menor valor h(n);
➢A função f(n) = h(n);
➢A solução que ele encontra não é necessariamente a ótima;
➢O algoritmo é chamado de “ganancioso” pois em cada iteração ele tenta chegar o
mais próximo possível de um objetivo, mas a ganância pode levar a resultados
piores do que ser cuidadoso;
➢É completa em espaços de estados finitos, mas não em infinitos;
➢A complexidade de tempo e espaço do pior caso é O(|V|).
Greedy best-first search
➢Exemplo 1: Sibiu para Bucharest
Greedy best-first search
➢Exemplo 2:
Greedy best-first search
➢Exemplo 2:
A∗ search
➢O algoritmo de busca informada mais comum é A∗ search (pronunciado A-star
search);
➢É um best-first search que utiliza a função de evolução:
f(n) = g(n)+h(n)
onde g(n) é o custo do caminho do estado inicial para o nó n, e h(n) é o custo
estimado do caminho mais curto de n para um estado objetivo;
➢f(n) = custo estimado do melhor caminho que continua de n até um objetivo.
A∗ search
➢Exemplo:
A∗ search
➢Exemplo:
A∗ search
➢ É completa;
➢Ser ótimo em termos de custo depende de certas propriedades da heurística.
Uma propriedade chave é a admissibilidade: uma heurística admissível é aquela
que nunca superestima o custo para atingir uma meta;
Obrigado!
