Buscas em Inteligência Artificial — métodos e critérios

Buscas

Busca exaustiva (cega)

Método de busca para determinar a ordem correta de aplicação dos operadores que levará do estado inicial ao estado final.

• Não sabe qual o melhor nó da fronteira a ser expandido; apenas distingue o estado objetivo dos não objetivos.

Estratégias para determinar a ordem de ramificação dos nós

1. Busca em largura
2. Busca de custo uniforme
3. Busca em profundidade
4. Busca com aprofundamento iterativo

Direção da ramificação

1. Do estado inicial para um estado final
2. De um estado final para o estado inicial
3. Busca bidirecional

Critério de avaliação das estratégias de busca

Completa? A estratégia sempre encontra uma solução quando existe alguma?

Ótima? A estratégia encontra a melhor solução quando existem soluções diferentes (menor custo de caminho)?

Custo de tempo? Quanto tempo é gasto para encontrar uma solução?

Custo de memória? Quanta memória é necessária para realizar a busca?

Busca em profundidade

• Segue cada caminho até sua maior profundidade antes de seguir para o próximo caminho.
• Se a folha não representar um estado objetivo, a busca retrocederá ao primeiro nó anterior que tenha um caminho não explorado.

Busca em largura (extensão)

• Percorre a árvore em largura ao invés de profundidade.
• Começa examinando todos os nós de um nível abaixo da raiz.
• Se não encontrar o objetivo, busca no próximo nível.
• Melhor em árvores que tenham caminhos muito profundos.
• Utilizada em árvores de jogos.

Busca de custo uniforme

A primeira solução encontrada é a solução ótima se o custo do caminho sempre aumentar ao longo do percurso, ou seja, se não existirem operadores com custo negativo.

Busca heurística

• Busca genérica onde o nó de menor custo “aparente” na fronteira do espaço de estados é expandido primeiro.
• Utiliza conhecimento específico do problema na escolha do próximo nó a ser expandido.
• A função de avaliação estima o custo do caminho do nó atual até o objetivo (conhecida como heurística); essa estimativa indica o quão promissor é o nó em relação a atingir a meta.

Função heurística h

• Estima o custo do menor caminho do estado atual até o estado final mais próximo.
• Uma boa heurística nunca deve ultrapassar o custo real da solução (heurística admissível).

Combinação g(n) + h(n)

A função f(n) será construída como: f(n) = g(n) + h(n), onde g(n) é o custo do caminho desde o início até n e h(n) é a estimativa heurística do custo de n até o objetivo.