Métodos de Resolução de Problemas e de Procura
A resolução de problemas em Inteligência Artificial (IA) baseia-se na procura de soluções em espaços de estados, onde cada estado representa uma configuração do problema, e ações permitem a transição entre estados. Este processo é categorizado em procura não-informada (cega) e procura informada (heurística), com abordagens adequadas para diferentes problemas.
1. Estratégias de Procura
1.1 Procura Não-Informada (Cega)
- Definição:
Métodos que exploram o espaço de estados sem conhecimento adicional sobre o problema além do próprio grafo. Não utilizam heurísticas para guiar a procura. - Tipos:
- Custo Uniforme:
- Expande o nó com o menor custo acumulado até ao momento.
- É ótimo (encontra a solução de menor custo) e completo (encontra uma solução se ela existir).
- Adequado para problemas onde o custo das ações é variável.
- Exemplo: Planeamento de rotas com custos diferentes (pedágios, distância).
- Iterativa (Depth-Limited Search):
- Realiza uma procura em profundidade até um limite fixo, aumentando o limite iterativamente.
- Combina eficiência de memória da profundidade com a completude da procura em largura.
- Exemplo: Exploração de grafos em ambientes com espaço de busca infinito.
- Bidirecional:
- A procura é feita simultaneamente a partir do estado inicial e do estado final, encontrando-se no meio.
- Reduz exponencialmente o número de estados explorados em problemas com estados bem definidos.
- Exemplo: Redes de transportes onde o destino é conhecido.
- Custo Uniforme:
1.2 Procura Informada (Heurística)
- Definição:
Métodos que utilizam uma função heurística para estimar a proximidade de um estado à solução, guiando a procura de forma mais eficiente. - Tipos:
- Heurísticas:
- Funções que fornecem estimativas de custo para atingir o objetivo a partir de um dado estado.
- Exemplo: Distância em linha reta numa rede de estradas para calcular a proximidade ao destino.
- Procura Gulosa:
- Seleciona o nó mais promissor com base exclusivamente na heurística (h(n)), que estima o custo até o objetivo.
- Rápida, mas não ótima, podendo escolher caminhos subótimos.
- Exemplo: Navegação em mapas com preferência por caminhos mais curtos (mesmo que não sejam os de menor custo total).
- Algoritmo A*:
- Combina o custo acumulado até ao nó atual ((g(n))) com a heurística ((h(n))) para escolher o nó a ser expandido: (f(n) = g(n) + h(n)).
- Ótimo e completo, desde que a heurística seja admissível (não superestime o custo real).
- Exemplo: Planeamento de trajetos onde tanto o custo acumulado quanto a proximidade ao destino são considerados.
- Heurísticas:
Comparação Entre Métodos
Desafios e Considerações
- Eficiência Computacional:
Métodos cegos exploram muitos nós desnecessários, enquanto métodos heurísticos podem ser computacionalmente caros dependendo da qualidade da heurística. - Qualidade da Heurística:
No caso da procura informada, o desempenho depende diretamente da capacidade da heurística em aproximar os custos reais. Heurísticas mal definidas podem degradar o desempenho. - Ambientes Dinâmicos:
Estratégias tradicionais são menos eficazes em ambientes onde o espaço de estados muda frequentemente (e.g., jogos em tempo real, sistemas robóticos).