Questão 66930

Em uma disciplina de Inteligência Artificial para um curso de Licenciatura em Computação, o professor quer que seus alunos compreendam a diferença entre os algoritmos de busca 'não informada' (ou cega) e 'informada' (ou heurística). Ele explica: "Algoritmos de busca não informada, como a Busca em Largura (BFS) ou a Busca em Profundidade (DFS), exploram o espaço de busca sem qualquer conhecimento sobre a 'direção' do objetivo. Eles apenas seguem a topologia do grafo. Algoritmos de busca informada, por outro lado, utilizam uma 'função heurística', $h(n)$, que estima o custo do caminho do estado $n$ até o objetivo. Essa informação adicional permite que a busca seja muito mais eficiente, pois ela pode priorizar a exploração dos caminhos que 'parecem' mais promissores." Para ilustrar, ele apresenta o problema de encontrar o caminho mais curto entre duas cidades em um mapa rodoviário. E apresenta dois algoritmos de busca informada: a **Busca Gulosa (Greedy Best-First Search)**, que expande o nó que parece estar mais perto do objetivo de acordo com a heurística $h(n)$; e a **Busca A*** (A-Estrela), que expande o nó com o menor valor de $f(n) = g(n) + h(n)$, onde $g(n)$ é o custo real do caminho da origem até o nó $n$, e $h(n)$ é o custo estimado de $n$ até o destino.

A heurística utilizada é a distância em linha reta entre as cidades. Qual é a diferença fundamental no comportamento e nas garantias da Busca Gulosa e da Busca A*?

I. A Busca Gulosa pode ser sub-ótima. Ela pode seguir um caminho que parece promissor no início (baixa distância em linha reta), mas que acaba sendo um caminho muito mais longo na realidade (com muitas curvas), ignorando um caminho que começa com uma distância em linha reta maior, mas que é mais direto e curto no total.

II. A Busca A*, ao combinar o custo já percorrido ($g(n)$) com a estimativa futura ($h(n)$), equilibra a exploração. Ela não se deixa levar apenas pela promessa futura, mas também considera o esforço já gasto. Se a heurística $h(n)$ for 'admissível' (nunca superestimar o custo real), a Busca A* tem a garantia de encontrar o caminho mais curto.

III. A Busca Gulosa é sempre mais rápida e eficiente que a Busca A*, pois não precisa calcular o termo $g(n)$, e sempre encontrará o caminho ótimo.

É correto o que se afirma em: