28/02/2013

1

Representação do Conhecimento

Prof. Hudson Costa

Introdução

Para um computador poder solucionar um problema relacionado ao mundo real, ele primeiro precisa de um meio para representar o mundo real internamente.

28/02/2013

2

A Necessidade de uma Boa Representação

Redes semânticas

A rede semântica é uma representação comumente utilizada em IA. É um grafo consistindo em vértices que são conectados por arestas. Os vértices representam objetos e as ligações entre os vértices representam relacionamentos entre esses objetos, As ligações geralmente são rotuladas para indicar a natureza do relacionamento.

28/02/2013

3

Redes semânticas

Redes semânticas - exercício

28/02/2013

4

Redes semânticas - exercício

Crie uma rede semântica para descrever o seguinte conhecimento : Um carro é um veículo. Um carro desloca-se nas estradas. Um jipe é um veículo. Um jipe também se pode deslocar fora das estradas. Um carro tem 4 rodas. Uma moto é um veículo. Uma moto tem duas rodas. Os veículos deslocam-se por intermédio de motores. Uma bicicleta é um veículo cujo meio de locomoção são os pedais.

Redes semânticas - exercício

Crie uma rede semântica para descrever o seguinte conhecimento : Fido é um cachorro que tem como dono Bob. Fido, adora caçar Fang, que é um gato. Fang, como todo bom gato que se preze, adora caçar ratos. Já os ratos caçados por Fang, como de costume, comem queijo. Bob também come queijo. Bob, além de ser dono de Fido, é um construtor.

28/02/2013

5

Espaços de busca

É uma representação do conjunto de possíveis escolhas de um dado problema, uma ou mais das quais é a solução do problema. O objetivo da maioria dos procedimentos de busca é identificar um ou mais alvos e, geralmente, identificar um ou mais caminhos até esses alvos.

Espaços de busca

Estado 1 Robô na sala A. Bloco na sala A.

Estado 2 Robô na sala B. Bloco na sala A.

Estado 3 Robô na sala C. Bloco na sala A.

Estado 4 Robô na sala A. Bloco na sala B.

Estado 5 Robô na sala B. Bloco na sala B.

Estado 6 Robô na sala C. Bloco na sala B.

Estado 7 Robô na sala A. Bloco na sala C.

Estado 8 Robô na sala B. Bloco na sala C.

Estado 9 Robô na sala C. Bloco na sala C.

28/02/2013

6

Espaços de busca

Um estado é representado por um par (X,Y), onde X e Y são números que indicam a quantidade de água que contém as jarras de 4 e 3 litros, respectivamente. O estado inicial é (0,0) e o sistema de produção consiste nos seguintes operadores: (X,Y) --> (4,Y) se X < 4 (X,Y) --> (X,3) se Y < 3 (X,Y) --> (0,Y) se X > 0 (X,Y) --> (X,0) se Y > 0 (X,Y) --> (X - min(X, 3-Y), min(3, X+Y)) se Y < 3 (X,Y) --> (min(4, X+Y), Y - min(4-X, Y)) se X < 4 Os dois primeiros operadores representam a ação de encher uma das jarras. Os operadores 3 e 4 representam a ação de esvaziar uma jarra. Finalmente, os dois últimos operadores representam a ação des transvasar (talvez parcialmente) o conteúdo de uma jarra na outra. O objetivo, nesse problema, é de obter 2 litros de água na jarra de 4 litros. Na nossa representação, isso corresponde ao estado (2,0).

Espaços de busca

28/02/2013

7

Espaços de busca

Missionários e Canibais Três missionários e três canibais estão em uma das margens de um rio, com uma canoa. Todos querem ir para a outra margem do rio. A canoa somente pode transportar uma ou duas pessoas de cada vez. Não poderá haver, em qualquer momento, mais canibais que missionários em ambas as margens do rio, pois isto poderia resultar em os missionários serem devorados.

Estado 5 1 M 3 C E

2 M 0 C

D

Estado 6 0 M 3 C E

3 M 0 C

D

Estado 7 2 M 2 C E

1 M 1 C

D

Estado 8 2 M 1 C E

1 M 2 C

D

Estado 9 2 M 0 C E

1 M 3 C

D

Estado 10 1 M 2 C E

2 M 1 C

D

Estado 11 1 M 1 C E

2 M 2 C

D

Estado 12 1 M 0 C E

2 M 3 C

D

Estado 13 0 M 2 C E

3 M 1 C

D

Estado 14 0 M 1 C E

3 M 2 C

D

Estado 15 3 M 0 C E

0 M 3 C

D

Estado 16 0 M 0 C E

3 M 3 C

D

Estado 1 3 M 3 C E

0 M 0 C

D

Estado 2 3 M 2 C E

0 M 1 C

D

Estado 3 3 M 1 C E

0 M 2 C

D

Estado 4 2 M 3 C E

1 M 0 C

D

28/02/2013

8

Árvores Semânticas

• É um tipo de rede semântica com as seguintes características: – Nós predecessores e Nós sucessores. – É um grafo orientado. – O nó raiz não possui predecessores. – Nós que não possuem sucessores são nós folha. – Caminho é uma rota na árvore semântica que pode consistir em

apenas um nó (comp = 0). – Caminho completo: parte da raíz até o alvo. – Caminho parcial. – Ramo é uma aresta que conecta dois nós. – Fator de ramificação N de um nó: são seus N sucessores. – Fator de ramificação da árvore: média dos fatores de ramificação de

todos os nós. – Níveis: nível N=0 é o nível da raiz. Sucessores do nó raiz: N=1. Os

demais nós estarão no nível n + 1.

Árvores Semânticas

D

A

B

C

E

A

B C

D E F G

28/02/2013

9

Árvores de Busca

• Nada mais é do que uma árvore na qual podemos representar os caminhos possíveis em uma rede semântica.

A

D B

C E C D

B

A

C E

B

A

C

E

E D

D

A

E A

Árvore de busca para o problema dos missionários e canibais

Operadores:

1. Levar um canibal para a outra margem.

2. Levar dois canibais para a outra margem.

3. Levar um missionário para a outra margem.

4. Levar dois missionários para a outra margem.

5. Levar um canibal e um missionário para a outra margem.

0,0,0

1,0,1

0,0,0 0,0,0 1,0,0 1,0,0

2,0,1 1,1,1

1

1 1

2

2

5

3

28/02/2013

10

0,0,0

1,0,1 2,0,1 1,1,1

1 2 5

3

1,0,0

1

2

1

4

5

4

1

2

1,0,0

3,0,1

2,0,0

2,2,1

1,1,0

1,3,1

0,3,0

2,3,1 1

2 5

1,3,0 2,2,0

3

3,3,1 3,3,1

O problema do caixeiro-viajante

Um caixeiro-viajante deve visitar cada uma das cidades de um conjunto de cidades e retornar á cidade de partida. O objetivo do problema é encontrar o caminho mais curto que permita que ele visite cada uma das cidades.

28/02/2013

11

E

C

B

A

D

800

1500

900

700 600

1000

1100 1700 600 700

A

B C D E

C

D E

E D

A A

B D C E C D B

28/02/2013

12

Torres de Hanói

Temos três pinos e diversos discos de tamanhos diferentes. O objetivo é partir do estado inicial, no qual todos os discos estão no primeiro pino, por ordem de tamanho (o menor em cima) e chegar ao estado objetivo, no qual todos os discos estão no terceiro pino, também por ordem de tamanho. Podemos mover um disco de cada vez, desde que não haja discos sobre ele e desde que não seja movido para cima de um disco que seja menor que ele.

Torres de Hanói

Operadores:

1. Mover disco do pino 1 para o 2.

2. Mover disco do pino 1 para o pino 3.

3. Mover disco do pino 2 para o pino 1.

4. Mover disco do pino 2 para o pino 3.

5. Mover disco do pino 3 para o pino 1.

6. Mover disco do pino 3 para o pino 2.

28/02/2013

13

(1,2,3) ( ) ( )

(2,3) (1) ( )

(3) (1) (2)

(3) ( ) (1,2)

(1,3) ( ) (2) (3) ( ) (1,2)

(1,3) ( ) (2) (1,3) (2) ( )

(3) (1,2) ( ) (1,3) (2) ( )

(3) (1,2) ( )

(3) ( 2) (1)

(2,3) ( ) (1)

Descrever e Decidir

É um método que permite utilizar busca combinada com conhecimento para responder questões sobre o mundo.

28/02/2013

14

Descrever e Decidir

Alice, olhando pela janela, pode ver uma ave no jardim. Ela não tem muitos conhecimentos sobre aves, mas um amigo dela, Bob, entende do assunto. Ela chama Bob e descreve o pássaro para ele. Pela sua descrição, ele está certo em lhe dizer que a ave é um pinguim.

Pode voar?

Está extinto?

É preto-e-branco?

QUIVI PINGUIM

NÃO

NÃO

NÃO

SIM

SIM

SIM

DODO

28/02/2013

15

Explosão combinatória

Quando um problema tem como característica o fato de, à medida que aumenta o número de itens sendo considerados, o número de caminhos possíveis na árvore de busca cresce exponencialmente.

Árvores de objetivos

Também chamada de árvore e-ou, é uma forma de árvore semântica utilizada para representar problemas que podem ser subdivididos deste modo.

28/02/2013

16

Árvore de objetivos

MOVER A, B, C, D DE 1 PARA 3

MOVER A, B, C DE 2 PARA 3

MOVER A, B DE 1 PARA 3

MOVER A DE 2 PARA 3

MOVER D DE 1 PARA 3

MOVER C DE 2 PARA 3

MOVER B DE 1 PARA 3

• Abordagens para subdivisão de problemas: – Top down: envolve subdividir inicialmente o problema

principal em objetivos menores e então subdividir esses objetivos recursivamente em outros menores ainda.

– Bottom up: envolve determinar inicialmente todos os subobjetivos que sejam necessários para solucionar o problema por inteiro e então começar por solucionar os nós de sucesso e daí para cima até que uma solução completa seja obtida.

Árvore de objetivos

28/02/2013

17

Usos de árvores de objetivos

• Problema de coloração de mapas: