Métodos de Busca em Inteligência Artificial

Julgue os itens a seguir, relativos a métodos de busca com informação (busca heurística) e sem informação (busca cega), aplicados a problemas em que todas as ações têm o mesmo custo, o grafo de busca tem fator de ramificação finito e as ações não retornam a estados já visitados.

I. A primeira solução encontrada pela estratégia de busca em largura é a solução ótima.

II. A primeira solução encontrada pela estratégia de busca em profundidade é a solução ótima.

III. As estratégias de busca com informação usam funções heurísticas que, quando bem definidas, permitem melhorar a eficiência da busca.

IV. A estratégia de busca de aprofundamento iterativo não evita ciclos infinitos.

CERTO é I e III

Pesquisa em Árvore Binária de Pesquisa

Suponha que se queira pesquisar a chave 287 em uma árvore binária de pesquisa com chaves entre 1 e 1.000. Durante uma pesquisa como essa, uma sequência de chaves é examinada. Cada sequência abaixo é uma suposta sequência de chaves examinadas em uma busca da chave 287.

• I. 7, 342, 199, 201, 310, 258, 287
• II. 110, 132, 133, 156, 289, 288, 287
• III. 252, 266, 271, 294, 295, 289, 287
• IV. 715, 112, 530, 249, 406, 234, 287

É válido apenas o que se apresenta em

I e II

Conceitos Fundamentais de Busca

Espaço de Estados

• O conjunto de todos os estados acessíveis a partir de um estado inicial é chamado de espaço de estados.
  • Os estados acessíveis são aqueles dados pela função sucessora.
• O espaço de estados pode ser interpretado como um grafo em que os nós são estados e os arcos são ações.

Tipos de Busca

• Busca sem informação ou busca cega:
  • Usa apenas conhecimento da especificação do problema e procura encontrar uma solução.
• Busca informada:
  • Explora conhecimento extra sobre o domínio para guiar a busca em direção a regiões de menor custo.
• Busca local:
  • Não armazena informações sobre caminhos.

Estratégias de Busca Sem Informação

• Busca em Extensão (Breadth-first):

  Estratégia simples, em que o nó raiz é expandido primeiro, em seguida todos os nós do nó raiz são expandidos, depois os sucessores desses nós e assim por diante (busca em árvore).

• Busca de Custo Uniforme:

  Expande o nó com caminho de custo mais baixo. Observe que, se todos os custos de passos forem iguais, teremos uma busca em extensão.

• Busca em Profundidade (Depth-first):

  Expande o nó não-expandido mais profundo, onde os nós sem sucessores retornam ao nó seguinte mais raso que ainda tem sucessores inexplorados.

• Busca em Profundidade Limitada:

  Busca em profundidade com limite de profundidade $l$, isto é, nós com profundidade $l$ não têm sucessores.

• Busca de Aprofundamento Iterativo:

  Efetua sequência de buscas de profundidade limitada com limite crescente (Repete todos os algoritmos).

Resumo

• A formulação de problemas usualmente requer a abstração de detalhes do mundo real para que seja definido um espaço de estados que possa ser explorado através de algoritmos de busca.
• Há uma variedade de estratégias de busca sem informação (ou busca cega).
• A busca de aprofundamento iterativo usa somente espaço linear e não consome muito mais tempo que outros algoritmos sem informação.

Busca com Informação (ou Heurística)

• Utiliza conhecimento específico sobre o problema para encontrar soluções de forma mais eficiente do que a busca cega.
  • Conhecimento específico além da definição do problema.
• Abordagem geral: busca pela melhor escolha.
  • Utiliza uma função de avaliação para cada nó.
  • Expande o nó que tem a função de avaliação mais baixa, porque a avaliação mede a distância até o objetivo.
  • Dependendo da função de avaliação, a estratégia de busca muda.

Busca Gulosa pela Melhor Escolha

• Função de avaliação $f(n) = h(n)$ (heurística) = estimativa do custo de $n$ até o objetivo.
• Exemplo: $h(n)$ = distância em linha reta de $n$ até Bucareste.
• Busca gulosa pela melhor escolha expande o nó que parece mais próximo ao objetivo de acordo com a função heurística.
• Não é ótima, pois segue o melhor passo considerando somente o estado atual.

Busca A*

• Ideia: evitar expandir caminhos que já são caros.
• Uma heurística $h(n)$ é admissível se para cada nó $n$, $h(n) \le h^{*}(n)$, onde $h^{*}(n)$ é o custo verdadeiro de alcançar o estado objetivo a partir de $n$.
• Uma heurística admissível nunca superestima o custo de alcançar o objetivo, isto é, ela é otimista.

Sistemas Baseados em Conhecimento

• A maioria dos sistemas de IA baseados em conhecimento (SBC) se compõe de uma base de conhecimento (BC) e uma lógica de controle, responsável pelo mecanismo de raciocínio.
• A separação do conhecimento do domínio e da sua forma de manipulação permite que sejam implementadas diferentes tarefas com o mesmo conhecimento.

Agentes Baseados em Conhecimento

• Agentes humanos possuem conhecimento estruturado sobre fatos do mundo e raciocinam para inferir novos conhecimentos.
• Base de conhecimento: conjuntos de fatos sobre o mundo.
• Mecanismo de inferência: produção de conhecimento sobre novos fatos.

Lógica de Primeira Ordem

• Principal diferença entre lógica proposicional e a lógica de primeira ordem é o compromisso ontológico, ou seja, o que cada linguagem pressupõe sobre a natureza da realidade:
  • Lógica Proposicional: pressupõe que existem fatos que são válidos ou não-válidos no mundo.
  • Lógica de Primeira Ordem: pressupõe que o mundo consiste em objetos com certas relações entre eles que são válidas ou não-válidas.