T ÓPICOS DE I.A. Métodos de Busca Busca em Espaços de Estado Prof. Mário Dantas

TÓPICOS DE I.A.Métodos de Busca

Busca em Espaços de Estado

Prof. Mário Dantas

http://www.istockphoto.com/stock-photo-8183124-intelligence.php

2

BUSCA EM ESPAÇOS DE ESTADO

Conceito:

É uma técnica de I.A. que “... proporciona um

meio de solucionar problemas complexos,

para os quais não há disponível uma

abordagem mais direta nem uma estrutura

na qual qualquer técnica direta disponível

possa ser inserida” (FERNANDES, 2005).

3


Questões Importantes:

Existe garantia que o sistema para resolução de

problemas encontrará uma solução?

Este sistema chegará sempre ao final, ou ele

poderá ficar preso num laço infinito?

Quando uma solução é encontrada, é garantido

que ela seja ótima?

4


Questões Importantes:

Qual é a complexidade do processo de busca em

termos de tanto de consumo de tempo como de

consumo de memória?

Como se pode reduzir, da forma mais eficiente, a

complexidade da busca?

Como se pode projetar uma aplicação para que

ela utilize uma linguagem de representação o

mais eficientemente possível?

5


Teoria dos Grafos

Um grafo consiste:

Conjunto de NÓS;

Conjunto de ARCOS (Elos);

Criada no século XVII;

Pontes de Konigsberg.

Leonhard Euler (1707 a 1783)

6


Teoria dos Grafos

Os NÓS representam os Estados, por

exemplo, o resultados de inferência lógicas

ou as diferentes configurações de um

tabuleiro;

Os ARCOS representam as transições entre

estados, por exemplo, as inferências lógicas

ou movimentos válidos de um jogo.

7


Jogo da Velha

8


Web site

http://www.aharef.info/static/htmlgraph/

9


Em sistemas especialistas os estados

descrevem o nosso conhecimento sobre um

caso do problema em algum estágio de um

processo de raciocínio. O conhecimento do

especialista, na forma de regras SE... ENTÃO,

nos permite gerar informação nova. O ato de

aplicar uma regra é representado como um

arco entre estados.

10


Uma árvore é um grafo no qual dois nós têm, no

máximo, um caminho entre eles. As árvores

freqüentemente tem raízes e, neste caso, elas são

normalmente desenhadas com a raiz no topo,

como um grafo radicado. Como cada nó de uma

árvore tem apenas uma caminho de acesso, a

partir de qualquer outro nó, é impossível para um

caminho circular continuamente através de uma

seqüência de nós, originando um laço.

11


Nós = (a, b, c, d, e) Arcos = {(a,b), (a,d), (b,c), (c,b), (c,d), (d,a),

(d,e) (e,c), (e,d)}

a.

b.

d.

c.

e.

Grafo direcionado rotulado

12


Árvore Relações de Parentesco

a.

b.

d.

c.

e.

f. g.

h.

i. j.

13

REPRESENTAÇÃO DE PROBLEMAS POR ESPAÇOS DE ESTADOS

Um espaço de estado é representado pelo

conjunto {N, A, S, DO}, onde:

N representa os nós ou estados do grafo.

Eles correspondem aos estados de um

processo de solução de problema;

A representa os arcos entre os nós. Eles

correspondem aos passos de um processo de

solução de problema;

14


S representa um subconjunto não vazio de N, contém o(s) estado(s) inicial(is) do problema;

DO representa um subconjunto não vazio de N, contém o(s) estado(s) objetivo(s) do problema.

15


Os estados e, DO são descritos usando:

Uma propriedade mensurável dos estados

encontrados na busca;

Uma propriedade do caminho desenvolvido na

busca, por exemplo, os custos de transição para

o arco do caminho.

Um caminho solução é um caminho através

deste grafo de um nó S para um nó em DO.

16

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS

Entre as principais destacam-se a busca em a

busca em Amplitude e a busca em Profundidade;

Na busca em profundidade, quando um estado é

examinado, todos os seu filhos e os descendentes

de seus filhos são examinados antes de qualquer

um de seus irmãos;

Apenas quando não forem encontrados

descendentes de um estado é que seus irmãos são

considerados.

17

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS – BUSCA EM PROFUNDIDADE

A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U, D, I, Q, J, R

a.

b.

d.

c.

e.

f. g.

h.

i. j.

k.

l. m. n.

o.

q.

r.p.

s. t. u.

1 2

18

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS – BUSCA EM PROFUNDIDADE Implementação do algoritmo de busca em profundidade:função busca_em_profundidade;inicio abertos := [iniciar]; fechados := []; enquanto abertos <> [] faça inicio remova o estado mais à esquerda em abertos, chame-o de X; se X for um objetivo, então retorne SUCESSO senão inicio gere filhos de X; coloque X em fechados; descarte filhos de X se já estiverem em abertos ou fechados; coloque os filhos que restam no final à esquerda de abertos; fim fim retorne FALHAfim.

19


Nesse algoritmo os estados descendentes

são adicionados e removidos a partir do final

esquerdo da lista de abertos. Assim nessa

implementação a estrutura de dados usada é

a pilha (LIFO). Com isso a busca é

direcionada para os estados gerados mais

recentemente, produzindo uma ordem que

avança em profundidade;

20

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS – BUSCA EM PROFUNDIDADE Configuração das listas de abertos e fechados:

1. abertos = [A]; fechados=[ ]2. abertos = [B,C,D]; fechados=[A];3. abertos = [E,F,C,D]; fechados=[B,A];4. abertos = [K,L,F,C,D]; fechados=[E,B,A];5. abertos = [S,L,F,C,D]; fechados=[K,E,B,A];6. abertos = [L,F,C,D]; fechados=[S,K,E,B,A];7. abertos = [T,F,C,D]; fechados=[L,S,K,E,B,A];8. abertos = [F,C,D]; fechados=[T,L,S,K,E,B,A];9. abertos = [M,C,D](como L já está em abertos);

fechados=[F,T,L,S,K,E,B,A];10. abertos = [C,D]; fechados=[M,F,T,L,S,K,E,B,A];11. abertos = [G,H,D]; fechados=[C,M,F,T,L,S,K,E,B,A];12. e assim por diante, até que U seja encontrando ou

abertos = [ ]

21


Na busca em profundidade não se tem

garantia que o caminho mais curto até um

estado foi localizado na primeira vez que

este estado é encontrado;

Isso pode ser feito utilizando um atributo

TAMANHO_CAMINHO e varrendo toda a

árvore.

22

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS – BUSCA EM AMPLITUDE

A busca em amplitude, por outro lado,

explora o espaço nível por nível, apenas

quando não houver mais estados a serem

explorados num determinado nível é que o

algoritmo se moverá para o próximo.

23


A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P Q, R, S, T, U

a.

b.

d.

c.

e.

f. g.

h.

i. j.

k.

l. m. n.

o.

q.

r.p.

s. t. u.

1

2

24


função busca_em_amplitude;inicio abertos := [iniciar]; fechados := []; enquanto abertos <> [] faça inicio remova o estado mais à esquerda em abertos, chame-o de X; se X for um objetivo, então retorne SUCESSO senão inicio gere filhos de X; coloque X em fechados; descarte filhos de X se já estiverem em abertos ou fechados; coloque os filhos que restam no final à direita de abertos; fim fim retorne FALHAfim.

25


A lista de abertos é implementado como uma fila

(FIFO);

Os estados são adicionados à direita da lista e

removidos pela esquerda;

Os estados filhos que já foram descobertos são

descartados;

Se o algoritmo encerrar porque a condição

“enquanto” não for mais satisfeita (abertos=[ ]),

então ele varreu o grafo inteiro sem encontrar o

estado objetivo.

26


Configuração das listas de abertos e fechados:1. abertos = [A]; fechados=[ ]2. abertos = [B,C,D]; fechados=[A];3. abertos = [C,D,E,F]; fechados=[B,A];4. abertos = [D,E,F,G,H]; fechados=[C,B,A];5. abertos = [E,F,G,H,I,J]; fechados=[D,C,B,A];6. abertos = [F,G,H,I,J,K,L];

fechados=[E,D,C,B,A];7. abertos = [G,H,I,J,K,L,M](pois L já está em

abertos); fechados=[F,E,D,C,B,A];8. abertos = [H,I,J,K,L,M,N];

fechados=[G,F,E,D,C,B,A];9. e assim por diante, até que U seja encontrando

ou abertos = [ ]

27


A busca em amplitude garante que o caminho mais curto entre o estado inicial e o objetivo será encontrada, caso exista;

Pode-se manter outras informações nas listas de estados, como os ancestrais junto a cada estado, com isso pode-se refazer o caminho percorrido até o estado meta;

28


Entre as características mais significativas a

escolha entre as duas abordagens se incluem:

A importância de se encontrar o caminho mais curto

até o objetivo;

Fator de ramificação de espaço;

Disponibilidade de tempo computacional e de

recursos de memória;

A média de comprimento dos caminhos até o objetivo;

Se queremos todas soluções ou apenas a primeira

encontrada.

29

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS – BUSCA HEURÍSTICA

De acordo com Polya (1945), heurística é “o

estudo dos métodos e das regras de

descoberta e invenção”.

Na busca em espaços de estado, heurísticas

são formalizadas como regras para escolher

aqueles ramos que tem maior probabilidade

de levarem a uma solução aceitável para o

problema.

30


As heurísticas são usadas basicamente

quando:

Um problema pode não ter uma solução exata por

causa das ambigüidades inerentes na formulação

do problema ou pela disponibilidade de dados. Ex.:

medicina e visão;

Um problema pode ter uma solução exata, mas o

custo computacional de encontrá-la pode ser

proibitivo. Ex.: jogo de xadrez.

31


Uma heurística é apenas um conjectura informada

sobre o próximo passo a ser tomado na solução e

um problema;

Pode levar um algoritmo encontrar uma solução sub-

ótima ou não levá-lo a encontrar a solução de um

problema, isto é inerente das heurísticas;

As “regras práticas” usadas por especialista humano

para resolver problemas de forma eficiente são

essencialmente heurísticas quanto a sua natureza.

32


Os algoritmos heurísticos são constituídos de duas partes:

Medida heurística;

Algoritmo (parte que usa as medidas).

33


O jogo-da-velha

Cada um dos nove primeiros movimentos temos oito

respostas, que por sua vez tem sete movimentos;

Assim em uma busca exaustiva teríamos um espaço

de 9! = 362.880;

Analisando o jogo observamos que é possível reduzir o

espaço por simetria.

Assim não existem nove movimentos iniciais, mas

apenas três.

34


X

X

X

X O X O O

X

O

X

X

O

X

O

35

X


X

X

3 4 2

36


X

O

X

O

X

O

X X

O

X

X

O

X

X

O

X

X

O

X X

X O

X

O

X

X

O

X

X

4

3 4 4 5 5 4 4 4

37

ALGORITMO DE BUSCA HEURÍSTICA

funcao busca_melhor_escolha;

inicio

abertos := [inicio];

fechados := [];

enquanto aberto <> [] faça

inicio

remova o estado mais à esquerda em abertos, chame-o de X;

se X = objetivo, então retornar o caminho de início até X;

senão início

gere filhos de X;

para cada filho X faça

caso

o filho não está em abertos nem em fechados:

início

atribua um valor heurítico ao filho;

acrescente o filho em abertos;

fim;

38


o filho está em abertos:

se o filho foi alcançado por um caminho mais curto então atribua ai estado em abertos o caminho mais curto;

o filho já está em fechados:

se i filho foi alcançado por um caminho mais curto então

início

remova o estado de fechados;

acrescente o filho em abertos;

fim;

fim;

coloque x em fechados;

reordene estados em abertos pelo mérito heurístico (melhor mais à esquerda)

fim;

retorne FALHA;

fim.

39


Considerações:

cada estado retém informação sobre seu

ancestral;

determina se estado já foi alcançado por um

caminho mais curto;

retorna o caminho de solução final;

estados duplicados não são aceitos;

40


Considerações:

lista de abertos é ordenada de acordo com os

valores heurísticos desses estados (fila de

prioridades);

o próximo estado pode ser de qualquer nível do

espaço de estados;

o algoritmo se recupera de erros e acaba

encontrando o objetivo correto.

41

p.3


a.5

b.4d.6c.

4

e.5 f.5 g.4 h.3 i. j.

k.

l. m. n.

o.2 q.

r.

s. t. u.

42

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE ESTADOS Configuração das listas de abertos e fechados:

1. abertos = [A5]; fechados=[ ]

2. avaliar A5; abertos = [B4,C4,D6]; fechados=[A5];

3. avaliar B4; abertos = [C4,E5,F5,D6]; fechados=[B4,A5];

4. avaliar C4; abertos = [H3,G4,E5,F5,D6];

fechados=[C4,B4,A5];

5. avaliar H3; abertos = [O2,P3,G4,E5,F5,D6];

fechados=[H3,C4,B4,A5];

6. avaliar O2; abertos = [P3,G4,E5,F5,D6];

fechados=[O2,H3,C4,B4,A5];

7. avaliar P3; a solução foi encontrada!

43

CÓDIGO JAVA – SUBIDA DA ENCOSTA

44

CÓDIGO JAVA – ESTADOS DO JOGO-DOS-8

45

REFERÊNCIAS

LUGER, George F.. Inteligência Artificial: estruturas e estratégias para a solução de problemas complexos. Porto Alegre: Bookmann, 2004. Capítulos 3 e 4.

FERNANDES, Anita Maria da Rocha. Inteligência Artificial: noções gerais. Florianópolis: Visual Books, 2005.

Site: <http://www.inf.furb.br/~jomi/> acessado em 10 de fev. de 2010

Documents

T ÓPICOS DE I.A. Métodos de Busca Busca em Espaços de Estado Prof. Mário Dantas