Aula 2- Estratégias de buscas em grafos com e sem custos

Question 1

O que é uma Estratégia de Busca?

Answer 1

É 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.

Question 2

Quais são as principais estratégias de busca?

Answer 2

• Busca em profundidade
• Busca irevogável
• Busca backtracking
• Busca em largura
• Buscas com custos
• Baseadas somente nos custos
• Baseadas em heurísticas (estimativas)

Question 3

Algoritmo da busca em profundidade irrevogável

Answer 3

1. Escolher um dos operadores possíveis
2. Aplicar o operador e mudar para um novo estado
3. 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)

Question 4

Algoritmo da busca em profundidade com backtracking

Answer 4

• 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.

Question 5

Características da busca em profundidade irrevogável

Answer 5

Simplicidade

Não garante que encontrará a solução

Question 6

Características da busca em profundidade com backtracking

Answer 6

Garante que encontrará a solução, não garante se será a melhor solução
Garante que percorrerá todo o grafo

Question 7

Algoritmo da busca em largura

Answer 7

1. 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
2. Alterar nível atual para próximo nível e retornar ao passo 1

Question 8

Características da busca em largura

Answer 8

• 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)

Question 9

Como um problema para buscas com custos se caracteriza

Answer 9

• 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.

Question 10

Estratégias de buscas com custos

Answer 10

Busca gulosa (vizinho mais próximo)
Busca ordenada (algoritmo de Dijkstra)

Question 11

Algoritmo da busca gulosa

Answer 11

1. escolha o operador (caminho) que apresente o menor custo e leve a um vizinho ainda não visitado
2. Se o novo estado não for o estado final, retorne ao passo 1

Question 12

Características da busca gulosa

Answer 12

não garante encontrar um caminho

Encontrando um caminho, não garante ser o de menor custo

Question 13

Algoritmo da busca ordenada

Answer 13

1. 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ó
2. Marque o nó que teve os seus caminhos expandidos como nó fechado
3. Calcule o custo total dos novos nós como o custo do nó anterior mais o custo da ligação entre os nós
4. Abandone os nós com custo total maior que os nós equivalentes encontrados em outros ramos da árvore
5. Caso haja algum nó aberto da árvore de busca com custo total menor que o custo do nó final encontrado, retorne ao passo 1

Question 14

Características da busca ordenada

Answer 14

A busca ordenada encontra garantidamente o menor caminho

Entretanto, a busca ordenada pode ter que investigar muitos caminhos para encontrar o melhor caminho

Question 15

Qual o objetivo da busca heurística

Answer 15

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*

Question 16

Algoritmo de busca A*

Answer 16

Para que a busca A* funcione e também encontre o menor caminho (como a busca ordenada), apenas é necessário que:

1. 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)
2. 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

Question 17

Características da busca A*

Answer 17

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

Question 18

Como se estima o custo h(N)

Answer 18

• 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