Estratégias de Busca Heurística: A* e Gulosa

Empregando Algoritmos de Busca Informada para Otimizar a Resolução de Problemas

Autor

Márcio Nicolau

Data de Publicação

9 de outubro de 2025

Introdução

Nas aulas anteriores, exploramos as estratégias de busca cega (não-informada), como Busca em Largura (BFS) e Busca em Profundidade (DFS). Vimos que, embora sejam completas e, no caso da BFS, até ótimas sob certas condições, sua eficiência em espaços de estados grandes pode ser severamente limitada pela explosão combinatória. Elas não fazem uso de qualquer conhecimento sobre a “direção” do objetivo.

Nesta aula, introduziremos as estratégias de busca heurística (também conhecidas como busca informada). Esses algoritmos utilizam informações adicionais específicas do problema para guiar a busca de forma mais eficiente, otimizando o processo de encontrar uma solução. Focaremos em dois algoritmos proeminentes: a Busca Gulosa (Greedy Best-First Search) e a Busca A* (A* Search).

Objetivo de Aprendizagem

Ao final desta aula, você será capaz de:

  • Explicar as limitações dos algoritmos de busca cega e a motivação para a busca heurística.
  • Definir o conceito de função heurística e suas propriedades.
  • Compreender o funcionamento e aplicar o algoritmo de Busca Gulosa (Greedy Best-First Search).
  • Compreender o funcionamento e aplicar o algoritmo de Busca A* (A* Search).
  • Analisar as propriedades (completude, otimalidade, complexidade) de Busca Gulosa e A*.
  • Distinguir entre os conceitos de heurísticas admissíveis e consistentes.
  • Escolher a estratégia de busca informada mais apropriada para problemas específicos.

Problemas com Buscas Cegas (Não-Informadas): Uma Motivação

Algoritmos como BFS e DFS são métodos exaustivos que exploram o espaço de estados sem qualquer “inteligência” sobre onde o objetivo está.

  • BFS: Garante o caminho mais curto em número de passos, mas expande todos os nós em cada nível. A complexidade de tempo e espaço é \(O(b^d)\), o que se torna impraticável rapidamente para d (profundidade da solução) grande.

  • DFS: Mais eficiente em memória (\(O(bm)\)), mas pode se perder em caminhos infinitos e não garante a otimalidade ou completude sem modificações. A complexidade de tempo também é \(O(b^m)\) no pior caso.

Para muitos problemas do mundo real, o espaço de estados é vasto demais para ser explorado cegamente. Por exemplo, em um mapa de navegação com milhares de cidades ou em um jogo complexo, a busca cega seria ineficaz. Precisamos de uma maneira de direcionar a busca para as áreas mais promissoras do espaço de estados.

Heurísticas: Conhecimento para Guiar a Busca

A ideia central da busca informada é usar conhecimento específico do problema para guiar a exploração. Esse conhecimento é encapsulado em uma função heurística.

O que é uma Função Heurística (\(h(n)\))?

Uma função heurística, denotada por \(h(n)\), é uma estimativa do custo do caminho do nó n até o nó objetivo. Ela fornece uma “dica” de quão “próximo” um nó está do objetivo.

  • \(h(n) = 0\) se n é o nó objetivo.

  • A heurística ideal seria a verdadeira distância do nó n ao objetivo, mas isso geralmente é impossível de saber sem resolver o problema.

  • Uma boa heurística é aquela que fornece uma estimativa precisa sem ser muito custosa para calcular.

  • Exemplo: No problema do mapa da Romênia (de Arad para Bucareste), uma heurística natural é a distância em linha reta (straight-line distance) de qualquer cidade até Bucareste. Esta é uma estimativa da distância real, mas é fácil de calcular.

Por que Heurísticas são Importantes?

Heurísticas permitem que os algoritmos de busca se concentrem em caminhos mais promissores, reduzindo drasticamente o número de nós que precisam ser expandidos e explorados. Isso transforma problemas intratáveis em problemas solucionáveis.

graph TD
    A["Nó Atual (n)"] --> B{"Função Heurística h(n)"};
    B --> C["Estimativa do Custo para o Objetivo"];
    C --> D["Guia a Busca"];

    style A fill:#f0e68c,stroke:#333,stroke-width:2px;
    style B fill:#ffa07a,stroke:#333,stroke-width:2px;
    style C fill:#add8e6,stroke:#333,stroke-width:2px;
    style D fill:#98fb98,stroke:#333,stroke-width:2px;
Figura 1: Conceito de Função Heurística

Busca Gulosa (Greedy Best-First Search - GBFS)

A Busca Gulosa é o mais simples dos algoritmos de busca informada. Ela expande o nó que está mais próximo do objetivo, de acordo com a função heurística \(h(n)\).

Conceito e Funcionamento

A GBFS opera com a ideia de sempre seguir o caminho que parece ser o melhor no momento, sem considerar o custo já incorrido para chegar ao nó atual.

  • Função de Avaliação: \(f(n) = h(n)\)
  • Estrutura de Dados: Uma fila de prioridade (priority queue), que armazena os nós e os organiza com base no valor de \(h(n)\), expandindo sempre o nó com o menor \(h(n)\).
NotaAlgoritmo Básico da Busca Gulosa
  1. Crie uma fila de prioridade e adicione o estado inicial a ela, com prioridade \(h(\text{inicial})\).
  2. Crie um conjunto para armazenar estados visitados.
  3. Enquanto a fila de prioridade não estiver vazia:
    1. Remova o nó com a menor prioridade (\(h(n)\)) da fila (o nó atual).
    2. Se o nó atual for o estado objetivo, retorne o caminho para este nó.
    3. Adicione o nó atual ao conjunto de visitados.
    4. Para cada vizinho do nó atual:
      1. Se o vizinho não foi visitado e não está na fila:
        1. Adicione o vizinho à fila de prioridade, com prioridade \(h(\text{vizinho})\).
        2. Marque o nó atual como pai do vizinho.

Exemplo Prático com Python (Mapa da Romênia)

Usaremos o mapa da Romênia e as distâncias em linha reta até Bucareste como heurística.

Cidade Distância em linha reta até Bucareste
Arad 366
Bucareste 0
Craiova 160
Dobreta 242
Eforie 161
Fagaras 178
Giurgiu 77
Hirsova 151
Iasi 226
Lugoj 244
Mehadia 241
Neamt 234
Oradea 380
Pitesti 98
RimnicuVilcea 193
Sibiu 253
Timisoara 329
Urziceni 80
Vaslui 199
Zerind 374 
import heapq # Para fila de prioridade

# Mapa da Romênia (mesmo da aula de busca cega)
romania_map = {
    'Arad': {'Zerind': 75, 'Timisoara': 118, 'Sibiu': 140},
    'Zerind': {'Arad': 75, 'Oradea': 71},
    'Oradea': {'Zerind': 71, 'Sibiu': 151},
    'Timisoara': {'Arad': 118, 'Lugoj': 111},
    'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
    'Mehadia': {'Lugoj': 70, 'Dobreta': 75},
    'Dobreta': {'Mehadia': 75, 'Craiova': 120},
    'Craiova': {'Dobreta': 120, 'RimnicuVilcea': 146, 'Pitesti': 138},
    'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'RimnicuVilcea': 80},
    'RimnicuVilcea': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},
    'Fagaras': {'Sibiu': 99, 'Bucuresti': 211},
    'Pitesti': {'RimnicuVilcea': 97, 'Craiova': 138, 'Bucuresti': 101},
    'Bucuresti': {'Fagaras': 211, 'Pitesti': 101, 'Giurgiu': 90, 'Urziceni': 85},
    'Giurgiu': {'Bucuresti': 90},
    'Urziceni': {'Bucuresti': 85, 'Hirsova': 98, 'Vaslui': 142},
    'Hirsova': {'Urziceni': 98, 'Eforie': 86},
    'Eforie': {'Hirsova': 86},
    'Vaslui': {'Urziceni': 142, 'Iasi': 92},
    'Iasi': {'Vaslui': 92, 'Neamt': 87},
    'Neamt': {'Iasi': 87}
}

# Heurística: Distância em linha reta até Bucareste
heuristic_straight_line_to_bucuresti = {
    'Arad': 366, 'Bucuresti': 0, 'Craiova': 160, 'Dobreta': 242, 'Eforie': 161,
    'Fagaras': 178, 'Giurgiu': 77, 'Hirsova': 151, 'Iasi': 226, 'Lugoj': 244,
    'Mehadia': 241, 'Neamt': 234, 'Oradea': 380, 'Pitesti': 98, 'RimnicuVilcea': 193,
    'Sibiu': 253, 'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374
}

def greedy_best_first_search(graph, start_node, goal_node, heuristic):
    # Fila de prioridade: (h(n), node, path)
    priority_queue = [(heuristic[start_node], start_node, [start_node])]
    visited = set()

    print(f"Iniciando Busca Gulosa de {start_node} para {goal_node}...")

    while priority_queue:
        current_h_cost, current_node, path = heapq.heappop(priority_queue)

        print(f"Expandindo nó: {current_node} (h={current_h_cost}). Caminho atual: {path}")

        if current_node == goal_node:
            print(f"Sucesso! Objetivo '{goal_node}' alcançado.")
            return path, current_h_cost # Retorna o caminho e o custo heurístico (não o custo real)

        if current_node not in visited:
            visited.add(current_node)

            for neighbor, cost in graph.get(current_node, {}).items():
                if neighbor not in visited:
                    new_path = path + [neighbor]
                    heapq.heappush(priority_queue, (heuristic[neighbor], neighbor, new_path))
                    print(f"  Adicionando vizinho '{neighbor}' (h={heuristic[neighbor]}) à fila de prioridade.")
        else:
            print(f"  Nó '{current_node}' já visitado, ignorando.")

    print(f"Falha! Objetivo '{goal_node}' não encontrado.")
    return None, None

# Exemplo de uso:
if __name__ == "__main__":
    start_city = 'Arad'
    goal_city = 'Bucuresti'
    path_found, h_cost = greedy_best_first_search(romania_map, start_city, goal_city, heuristic_straight_line_to_bucuresti)

    if path_found:
        print(f"\nCaminho encontrado de {start_city} para {goal_city}: {' -> '.join(path_found)}")
        print(f"Custo heurístico final (h(goal)): {h_cost}")
    else:
        print(f"\nNão foi possível encontrar um caminho de {start_city} para {goal_city}.")
Iniciando Busca Gulosa de Arad para Bucuresti...
Expandindo nó: Arad (h=366). Caminho atual: ['Arad']
  Adicionando vizinho 'Zerind' (h=374) à fila de prioridade.
  Adicionando vizinho 'Timisoara' (h=329) à fila de prioridade.
  Adicionando vizinho 'Sibiu' (h=253) à fila de prioridade.
Expandindo nó: Sibiu (h=253). Caminho atual: ['Arad', 'Sibiu']
  Adicionando vizinho 'Oradea' (h=380) à fila de prioridade.
  Adicionando vizinho 'Fagaras' (h=178) à fila de prioridade.
  Adicionando vizinho 'RimnicuVilcea' (h=193) à fila de prioridade.
Expandindo nó: RimnicuVilcea (h=193). Caminho atual: ['Arad', 'Sibiu', 'RimnicuVilcea']
  Adicionando vizinho 'Craiova' (h=160) à fila de prioridade.
  Adicionando vizinho 'Pitesti' (h=98) à fila de prioridade.
Expandindo nó: Fagaras (h=178). Caminho atual: ['Arad', 'Sibiu', 'Fagaras']
  Adicionando vizinho 'Bucuresti' (h=0) à fila de prioridade.
Expandindo nó: Craiova (h=160). Caminho atual: ['Arad', 'Sibiu', 'RimnicuVilcea', 'Craiova']
  Adicionando vizinho 'Dobreta' (h=242) à fila de prioridade.
  Adicionando vizinho 'Pitesti' (h=98) à fila de prioridade.
Expandindo nó: Pitesti (h=98). Caminho atual: ['Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti']
  Adicionando vizinho 'Craiova' (h=160) à fila de prioridade.
  Adicionando vizinho 'Bucuresti' (h=0) à fila de prioridade.
Expandindo nó: Bucuresti (h=0). Caminho atual: ['Arad', 'Sibiu', 'Fagaras', 'Bucuresti']
Sucesso! Objetivo 'Bucuresti' alcançado.

Caminho encontrado de Arad para Bucuresti: Arad -> Sibiu -> Fagaras -> Bucuresti
Custo heurístico final (h(goal)): 0

Observe que a Busca Gulosa pode não encontrar o caminho mais curto em custo real. No exemplo, ele expandiu RimnicuVilcea e Craiova, seguindo a heurística, antes de encontrar Fagaras, que levou mais diretamente a Bucareste.

Propriedades da Busca Gulosa

  • Completude: Não é completa. Em espaços de estados com caminhos infinitos ou ciclos, e sem um mecanismo para evitar repetição de nós (o conjunto visited ajuda aqui), pode se perder em um ramo sem fim, mesmo que o objetivo esteja em outro lugar. Se a heurística for ruim, pode ignorar o caminho correto.
  • Otimidade: Não é ótima. Pode encontrar uma solução, mas não há garantia de que será o caminho de menor custo total. A “ganância” pode levar a atalhos que parecem bons heuristicamente, mas são caros na realidade. No exemplo acima, o caminho Arad -> Sibiu -> Fagaras -> Bucuresti (Custo total 140+99+211 = 450) foi encontrado, mas Arad -> Sibiu -> RimnicuVilcea -> Pitesti -> Bucuresti (Custo total 140+80+97+101 = 418) seria mais curto.
  • Complexidade de Tempo: \(O(b^m)\) no pior caso, onde m é a profundidade máxima. Pode ser significativamente melhor na prática se a heurística for boa.
  • Complexidade de Espaço: \(O(b^m)\) no pior caso, pois pode precisar armazenar todos os nós expandidos na fila de prioridade.

Admissibilidade e Consistência de Heurísticas

Para garantir a otimalidade da Busca A*, a heurística utilizada deve satisfazer certas propriedades.

Admissibilidade

Uma função heurística \(h(n)\) é admissível se ela nunca superestima o custo real de chegar ao objetivo a partir do nó n. Formalmente:

  • \(h(n) \le h^*(n)\) para todo nó n, onde \(h^*(n)\) é o custo real do caminho mais barato de n ao objetivo.

  • Importância: A admissibilidade é crucial para garantir a otimalidade da Busca A*. Se A* usa uma heurística admissível, ela sempre encontrará o caminho de menor custo, assumindo custos de aresta não-negativos.

  • Exemplo: A distância em linha reta é uma heurística admissível para problemas de navegação em mapas (como o da Romênia), pois a menor distância entre dois pontos é sempre uma linha reta, e não podemos viajar mais rápido do que isso.

Consistência (ou Monotonicidade)

Uma função heurística \(h(n)\) é consistente se, para todo nó n e qualquer sucessor n' de n gerado por uma ação com custo \(c(n, n')\):

  • \(h(n) \le c(n, n') + h(n')\)

  • Importância: A consistência é uma condição mais forte que a admissibilidade. Se uma heurística é consistente, ela também é admissível. Em algoritmos como A*, uma heurística consistente garante que o valor de \(f(n)\) nunca diminui ao longo de um caminho. Isso evita a necessidade de reabrir e re-expandir nós já expandidos, simplificando a implementação e garantindo que o primeiro caminho encontrado para qualquer nó é o caminho mais curto para aquele nó.

graph TD
    A["Função Heurística h(n)"] --> AD{"Admissível?"};
    AD -- "h(n) ≤ h*(n)" --> AD_Yes{"Sim (A* Ótima)"};
    AD -- "h(n) > h*(n)" --> AD_No{"Não (A* Não Ótima)"};

    A --> CONS{"Consistente?"};
    CONS -- "h(n) ≤ c(n,n') + h(n')" --> CONS_Yes{"Sim (Implica Admissibilidade)"};
    CONS -- "Não" --> CONS_No{"Não (Pode ainda ser Admissível)"};

    style A fill:#f9f,stroke:#333,stroke-width:2px;
    style AD_Yes fill:#afa,stroke:#333,stroke-width:2px;
    style CONS_Yes fill:#afa,stroke:#333,stroke-width:2px;
    style AD_No fill:#f0e68c,stroke:#333,stroke-width:2px;
    style CONS_No fill:#f0e68c,stroke:#333,stroke-width:2px;
Figura 2: Propriedades de Funções Heurísticas

Considerações Práticas para Busca Heurística

  • Design de Heurísticas: A qualidade da heurística é crucial. Uma heurística mal projetada pode fazer com que a busca informada se comporte como uma busca cega ou, pior, leve a soluções não-ótimas (se não for admissível) ou a um desempenho muito ruim.
    • Muitas vezes, heurísticas são derivadas de versões relaxadas do problema, onde algumas restrições são removidas para tornar o problema mais fácil de estimar (e o custo real nunca é menor que o custo relaxado).
  • Trade-offs:
    • Busca Gulosa: Rápida para encontrar alguma solução, mas não garante a melhor e pode se perder. Boa quando a velocidade é mais importante que a otimalidade e a heurística é confiável.
    • Busca A*: Garante a solução ótima (com heurística admissível), mas pode ser mais lenta e consumir mais memória que a Busca Gulosa se a heurística for muito conservadora (baixa estimativa). É o algoritmo preferencial quando otimalidade é um requisito.
  • Memória: A principal limitação da A* é o consumo de memória (\(O(b^d)\)). Para problemas com espaços de estados enormes, variações como a A* Iterativa (IDA*) ou a A* de Memória Limitada (SMA*) são usadas para gerenciar o uso de memória.

Escolhendo a Melhor Estratégia

Problema / Cenário Estratégia Recomendada Justificativa
Encontrar qualquer caminho rápido. DFS ou Busca Gulosa DFS eficiente em memória, Gulosa rápida se heurística boa.
Encontrar o caminho mais curto em termos de passos (custos uniformes). BFS Ótima e completa, mas consome muita memória.
Encontrar o caminho de menor custo total (custos não uniformes), com memória ilimitada. Busca A* Ótima e completa com heurística admissível.
Encontrar o caminho de menor custo total, com memória limitada. A* Iterativa (IDA*) ou SMA* Combinam otimalidade de A* com eficiência de memória de DFS.
Espaço de estados muito grande, heurística forte. Busca Gulosa ou A* Heurísticas informadas são essenciais para reduzir o espaço de busca.

Verificação de Aprendizagem

Responda às seguintes questões e implemente as tarefas propostas para solidificar seu entendimento.

  1. Motivação para Busca Informada:

    1. Quais são as principais desvantagens da Busca em Largura (BFS) e Busca em Profundidade (DFS) em problemas com grandes espaços de estados?
    2. Como uma função heurística (\(h(n)\)) ajuda a superar essas desvantagens?

  2. Busca Gulosa:

    1. Explique o princípio de funcionamento da Busca Gulosa. Qual função de avaliação (\(f(n)\)) ela utiliza?
    2. Por que a Busca Gulosa não é garantidamente ótima? Dê um exemplo (pode ser conceitual ou desenhado) onde ela escolheria um caminho subótimo.

  3. Busca A*:

    1. Qual a função de avaliação (\(f(n)\)) utilizada pela Busca A*? Explique o significado de cada componente.
    2. Em qual aspecto principal a Busca A* se difere da Busca Gulosa, levando-a a ser ótima sob certas condições?

  4. Propriedades de Heurísticas:

    1. Defina uma heurística admissível. Por que a admissibilidade é crucial para a otimalidade da Busca A*?
    2. Defina uma heurística consistente. Qual a relação entre consistência e admissibilidade?

  5. Implementação e Análise Comparativa: Considere um problema de labirinto simples onde o agente precisa ir de um ponto inicial ‘S’ a um ponto final ‘G’. O labirinto é representado por uma grade 2D, e o agente pode se mover para cima, baixo, esquerda ou direita (custo 1 por movimento).

    [['S', ' ', ' ', ' '],
 [' ', 'X', ' ', ' '],
 [' ', ' ', ' ', ' '],
 [' ', ' ', 'X', 'G']]

    onde ‘X’ são obstáculos.

    1. Represente este labirinto como um grafo (nós são coordenadas (linha, coluna)) em Python.
    2. Defina uma função heurística admissível e consistente para este labirinto (dica: distância de Manhattan).
    3. Adapte a função greedy_best_first_search e a_star_search para resolver este labirinto.
    4. Execute ambas as buscas de ‘S’ para ‘G’. Compare:
      1. O caminho encontrado por cada algoritmo.
      2. O custo total do caminho de cada algoritmo.
      3. A ordem em que os nós foram expandidos (você pode inferir isso da saída de print).
      4. Comente se os resultados confirmam as propriedades de otimalidade e eficiência esperadas para cada algoritmo neste cenário.

Referências Bibliográficas

RUSSELL, Stuart J.; NORVIG, Peter. Inteligência Artificial: Um Enfoque Moderno. 2. ed. Rio de Janeiro: Prentice Hall, 2004.