Aula 2- Estratégias de buscas em grafos com e sem custos Flashcards
O que é uma Estratégia de Busca?
É uma forma sistemática de percorrer um grafo de estados à procura de um estado final. Cada estratégia é caracterizada, portanto, por uma sequência de aplicação de operadores que levam o problema do estado inicial a um estado final.
Quais são as principais estratégias de busca?
- Busca em profundidade
- Busca irevogável
- Busca backtracking
- Busca em largura
- Buscas com custos
- Baseadas somente nos custos
- Baseadas em heurísticas (estimativas)
Algoritmo da busca em profundidade irrevogável
- Escolher um dos operadores possíveis
- Aplicar o operador e mudar para um novo estado
- Se o novo estado não é final, retornar ao passo 1 (não o estado 1, mas ao passo 1, ou seja, escolhe um possível operador)
Algoritmo da busca em profundidade com backtracking
- Caso cheguemos a um estado sem solução (F, por ex.), retornamos ao estado anterior e escolhemos um outro operador possível.
- A busca backtraking garante que encontra a solução, caso haja.
Características da busca em profundidade irrevogável
Simplicidade
Não garante que encontrará a solução
Características da busca em profundidade com backtracking
Garante que encontrará a solução, não garante se será a melhor solução
Garante que percorrerá todo o grafo
Algoritmo da busca em largura
- Enquanto houver estados não investigados no nível atual
I - Escolher um dos estados não investigados do nível atual
II - Aplicar todos os operadores possíveis ao estado escolhido
III - Se não foi atingido um estado final, retornar ao passo I - Alterar nível atual para próximo nível e retornar ao passo 1
Características da busca em largura
- Se houver solução, esta será garantidamente encontrada
- Se não houver solução, a busca indicará que todos os caminhos foram investigados e não há solução
- Se houver mais de uma solução, a busca em largura encontrará primeiramente a solução que demanda menos passos (a mais próxima da raiz)
Como um problema para buscas com custos se caracteriza
- A maioria do problemas reais possui custos distintos para escolha de cada operador
- Podemos sintetizar essa situação em um problema de roteamento que consiste em partir de uma cidade de origem e chegar a uma cidade de destino, em um mapa que possui ligações entre as cidades com distâncias conhecidas (custos)
- Queremos encontrar o caminho para ir da origem ao destino ao menor custo possível.
Estratégias de buscas com custos
Busca gulosa (vizinho mais próximo) Busca ordenada (algoritmo de Dijkstra)
Algoritmo da busca gulosa
- escolha o operador (caminho) que apresente o menor custo e leve a um vizinho ainda não visitado
- Se o novo estado não for o estado final, retorne ao passo 1
Características da busca gulosa
não garante encontrar um caminho
Encontrando um caminho, não garante ser o de menor custo
Algoritmo da busca ordenada
- Escolha o nó aberto (que ainda não teve seus caminhos investigados) de menor custo total e expanda todos os possíveis caminhos desse nó
- Marque o nó que teve os seus caminhos expandidos como nó fechado
- Calcule o custo total dos novos nós como o custo do nó anterior mais o custo da ligação entre os nós
- Abandone os nós com custo total maior que os nós equivalentes encontrados em outros ramos da árvore
- Caso haja algum nó aberto da árvore de busca com custo total menor que o custo do nó final encontrado, retorne ao passo 1
Características da busca ordenada
A busca ordenada encontra garantidamente o menor caminho
Entretanto, a busca ordenada pode ter que investigar muitos caminhos para encontrar o melhor caminho
Qual o objetivo da busca heurística
a busca ordenada pode ter que investigar muitos caminhos para encontrar o melhor caminho, mas podemos usar uma estimativa sobre as perspectivas futuras de cada opção para a escolher o melhor caminho. Essa estimativa é a heurística (uma aproximação da realidade descoberta de alguma forma) que podemos então considerar.
Se levarmos em conta apenas as estimativas, teremos novamente uma busca gulosa que pode não encontrar o menor caminho
Se combinarmos as estimativas com os custos reais dos caminhos, teremos então uma busca chamada de A*
Algoritmo de busca A*
Para que a busca A* funcione e também encontre o menor caminho (como a busca ordenada), apenas é necessário que:
- Haja uma estimativa para cada nó N aberto, que equivalha ao custo estimado para ir de N até o final e que é chamada de h(N)
- Cada h(N) não seja maior que o custo real para ir de N até o final, ou seja, as estimativas devem ser otimistas
Características da busca A*
O algoritmo A* é igual à busca ordenada, exceto pelo fato que o custo total considerado nas decisões é o custo para chegar até aquele nó (o mesmo da busca ordenada) mais o custo estimado para ir daquele nó até o final.
Ou seja, C(N) = r(N) + h(N), onde:
C(N) → custo total para o nó N
r(N) → custo real para chegar até o nó N
h(N) → custo heurístico estimado para ir de N até final
Como se estima o custo h(N)
- Em problemas de roteamento, podemos usar como estimativa a distância entre os pontos, que será sempre, em uma geometria Euclidiana, necessariamente otimista (“ a menor distância entre dois ponto é uma reta”)
- Em outros tipos de problemas devemos encontrar uma forma qualquer de estabelecer estimativas otimistas