Busca Heurística e Ontologias: Conceitos e Aplicações

Busca Heurística

A busca heurística utiliza conhecimento específico do problema na escolha do próximo nó a ser expandido, aplicando uma função de avaliação a cada nó na fronteira do espaço de estados.

Função heurística (h): Estima o custo do caminho mais barato do estado atual até o estado final mais próximo. Exemplo: encontrar a rota mais barata de João Pessoa a Cajazeiras (h(n) = distância direta entre o nó n e o nó final).

Classes de Algoritmos para Busca Heurística

• Busca pela melhor escolha: Busca genérica onde o nó de menor custo “aparente” na fronteira do espaço de estados é expandido primeiro.
• Busca com limite de memória.
• Busca com melhora iterativa.

Busca Gulosa

Semelhante à busca em profundidade com backtracking, tenta expandir o nó mais próximo do nó final com base na estimativa da função heurística h.

• Custo de busca: Mínimo (não expande nós fora do caminho).
• Limitações: Não é ótima (escolhe apenas o caminho mais econômico) e não é completa (pode entrar em looping se não detectar estados repetidos ou desenvolver caminhos infinitos).
• Custo de tempo e memória: Guarda todos os nós expandidos na memória.

Algoritmo A*: Análise de Comportamento

Algoritmo para busca de caminho em grafos, do vértice inicial ao final. É uma estratégia completa e ótima.

• Custo de tempo: Exponencial com o comprimento da solução (boas funções heurísticas diminuem esse custo).
• Custo de memória: Guarda todos os nós expandidos para possibilitar o backtracking.

Busca com Limite de Memória

• IDA* (Iterative Deepening A*): Similar ao aprofundamento iterativo, porém o limite é dado pela função de avaliação (f) e não pela profundidade (d). Requer menos memória que o A*.
• SMA*: O número de nós guardados em memória é fixado previamente.

Ontologias

Hierarquia de conceitos (classes) com suas relações, restrições, axiomas e terminologia associada.

• Definições: Explícitas, declarativas e formais (compreensíveis para inferência por agentes).
• Conceitualização: Modelo abstrato de uma área de conhecimento.
• Compartilhada: Conhecimento consensual.

Camada de Ontologias

União, Interseção, Complemento, Enumeração de instâncias, Classes podem ter disjunções, Propriedades podem ter: transitividade, simetria, atributos inversos, propriedades funcionais, Igualdade e desigualdade de instâncias.

Aplicação Gestão de Conhecimento - A Web semântica pode ser o elemento agregador, pois o conhecimento de uma empresa pode ser organizado em torno de ontologias. Agentes inteligentes - Poderão trocar e processar informação convenientemente em processos de comércio eletrônico. Se programados convenientemente poderão responder a perguntas sobre informações da Web.