Instruções

  1. Forme grupos de 3 alunos.
  2. Trabalhem apenas com papel e caneta.

Relembrando

Elemento Busca Gulosa Busca A*
Função de Avaliação f(n) = h(n) f(n) = g(n) + h(n)
Custo acumulado g(n) Não considerado na escolha do próximo nó Fundamental para garantir optimalidade
Heurística admissível Simples: distância em linha reta (ou 0). Deve ser admissível e preferencialmente consistente.

Exercício – Consistência de heurística em grade bidimensional

Um robô deve se mover em uma grade 5 × 5 (células numeradas de (1,1) até (5,5)). O objetivo está na célula (5,5). Existem obstáculos nas células: (2,3), (3,3), e (4,3). O robô pode se mover apenas em quatro direções (Norte, Sul, Leste, Oeste). Cada movimento tem custo 1.

Defina a heurística h(n) como a distância Manhattan do nó atual ao objetivo: h((x, y)) = |5 − x| + |5 − y|.

  1. Verificar se essa heurística é admissível (não sobreestima o custo real). Justifique.
  2. Checar se a heurística é consistente, ou seja, para quaisquer nós adjacentes n e m, verifica-se h(n) ≤ c(n, m) + h(m). Faça essa verificação apenas para os quatro pares de nós que envolvem o obstáculo na coluna 3 (ex.: (2,2)-(2,4), (1,3)-(2,3), etc.).
  3. Usando A*, determinar manualmente o caminho ótimo do robô a partir da célula inicial (1,1) até (5,5). Anotar os valores g(n), h(n) e f(n) = g(n) + h(n) para cada nó expandido.
  4. Se você alterasse a heurística para a distância Euclidiana (arredondada para cima), discutir se ela seria admissível e consistente, e como isso afetaria o caminho resultante de A*.
                                    +---+---+---+---+---+
                                    | S |   |   |   |   |
                                    +---+---+---+---+---+
                                    |   |   | X |   |   |
                                    +---+---+---+---+---+
                                    |   |   | X |   |   |
                                    +---+---+---+---+---+
                                    |   |   | X |   |   |
                                    +---+---+---+---+---+
                                    |   |   |   |   | G |
                                    +---+---+---+---+---+

Exercício Extra – Comparação entre GBFS e A* em um grafo ponderado

Enunciado

Considere o grafo abaixo (arestas pesadas). O nó inicial é S e o objetivo é T. A heurística h(n) para cada nó está indicada.

Nó h(n)
S 12
A 10
B 8
C 6
D 4
E 2
T 0

As arestas e pesos são:

Tarefas

  1. Executar Busca Gulosa a partir de S, registrando a ordem dos nós expandidos e o caminho final que chega em T.
  2. Executar A* a partir de S, calculando f(n) = g(n) + h(n) para cada nó expandido, onde g(n) é o custo acumulado do caminho inicial ao nó n. Registrar a ordem de expansão e o caminho final encontrado.
  3. Comparar os caminhos obtidos: qual deles tem menor custo total? Justificar por que um algoritmo pode ter superado ou não o outro neste caso.
  4. Identificar se a heurística h(n) é admissível (não sobreestima o custo real ao objetivo). Se for, qual algoritmo garante optimalidade?
  5. Propor uma pequena modificação na estrutura do grafo (alterar pesos de arestas) que faça com que GBFS encontre um caminho diferente daquele obtido por A*. Descrever a nova configuração e prever qual caminho cada algoritmo encontrará.

Boa sorte!