FORMALIZACAO

FUNDAÇÃO EDUCACIONAL ROSEMAR PIMENTEL
CENTRO UNIVERSITÁRIO GERALDO DI BIASE

Aula 5
Inteligência Artificial

Campus Volta Redonda – Av. Dep. Geraldo Di Biase 81
Aterrado – Volta Redonda – RJ – Tel: [phone] – www.ugb.edu.br

ÁRVORES SEMÂNTICAS
Uma árvore semântica é um tipo de rede semântica que tem as seguintes propriedades:
 Cada nó (exceto o nó raiz, descrito a seguir) tem exatamente um predecessor (pai) e um ou mais sucessores (filhos). Na árvore semântica da figura 1, o nó A é o predecessor do nó B: o nó A conecta-se por uma aresta ao nó B e vem antes dele na árvore. Os sucessores do nó B, nós D e E, conectam-se diretamente (por uma aresta cada) ao nó B e vêm depois dele na árvore. Podemos escrever estas relações como: suc(B) = D e pred (B) = A.
A natureza não simétrica deste relacionamento significa que uma árvore semântica é um grafo orientado. Em oposição, grafos não orientados são aqueles onde não há uma diferença entre um arco de A para B e um arco de B para A.

Figura 1: Uma rede semântica e uma árvore semântica.

 Um nó não tem predecessores. Este nó é chamado de raiz. Em geral, ao fazer uma busca em uma árvore semântica, começa-se do nó raiz. Isto é devido ao nó raiz tipicamente representar um ponto inicial do problema.
 Alguns nós não têm sucessores. Esses nós são chamados de folhas. Uma ou mais folhas são chamados de alvos. Estes são os nós que representam um estado no qual a busca foi bemsucedida.
 Exceto as folhas, todos os nós têm um ou mais sucessores. Exceto a raiz, todos os nós têm exatamente um predecessor.
 Um ancestral de um nó é um nó acima dele em algum caminho na árvore. Um descendente vem depois de um nó em um caminho na árvore.
Um caminho é uma rota na árvore semântica, que pode consistir em apenas um nó (um caminho de comprimento 0). Um caminho de comprimento 1 consiste em um nó, um ramo que parte deste nó e o nó sucessor ao qual este ramo chega. Um caminho que parta da raiz e vá até um alvo