TÓPICOS DE I.A.
Métodos de Busca
Busca em Espaços de Estado
Prof. Mário Dantas
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).
2
BUSCA EM ESPAÇOS DE ESTADO

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?
3
BUSCA EM ESPAÇOS DE ESTADO

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?
4
BUSCA EM ESPAÇOS DE ESTADO
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)
5
BUSCA EM ESPAÇOS DE ESTADO
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.
6
BUSCA EM ESPAÇOS DE ESTADO

Jogo da Velha
7
BUSCA EM ESPAÇOS DE ESTADO

Web site
8
http://www.aharef.info/static/htmlgraph/
BUSCA EM ESPAÇOS DE ESTADO

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.
9
BUSCA EM ESPAÇOS DE ESTADO

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.
10
BUSCA EM ESPAÇOS DE ESTADO
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)}

e.
a.
d
.
b.
c.
Grafo direcionado rotulado
11
BUSCA EM ESPAÇOS DE ESTADO
Árvore
 Relações de Parentesco

a.
c.
b.
e.
f.
g.
h
.
d
.
i.
j.
12
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;
13
REPRESENTAÇÃO DE PROBLEMAS POR
ESPAÇOS DE ESTADOS


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.
14
REPRESENTAÇÃO DE PROBLEMAS POR
ESPAÇOS DE ESTADOS

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.
15
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.
16
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM PROFUNDIDADE
a.
e.
f.
k
.
l.
s.
t.
d
.
c.
b.
g.
m.
n
.
i.
h
.
o.
p
.
j.
q.
r.
u
.
A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U, D, I, Q,
J, R
17
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 FALHA
fim.

18
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM PROFUNDIDADE

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
profundidade;
uma
ordem
que
avança
em
19
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM PROFUNDIDADE

Configuração das listas de abertos e fechados:
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
=[]
1.
20
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM PROFUNDIDADE

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.
21
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.
22
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM AMPLITUDE
a.
e.
f.
k
.
l.
s.
t.
d
.
c.
b.
m.
g.
h
.
n
.
o.
i.
p
.
j.
q.
r.
u
.
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P Q, R, S, T,
U
23
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM AMPLITUDE
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 FALHA
fim.
24
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM AMPLITUDE

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.
25
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM AMPLITUDE

Configuração das listas de abertos e fechados:
1.
2.
3.
4.
5.
6.
7.
8.
9.
abertos = [A]; fechados=[ ]
abertos = [B,C,D]; fechados=[A];
abertos = [C,D,E,F]; fechados=[B,A];
abertos = [D,E,F,G,H]; fechados=[C,B,A];
abertos = [E,F,G,H,I,J]; fechados=[D,C,B,A];
abertos = [F,G,H,I,J,K,L]; fechados=[E,D,C,B,A];
abertos = [G,H,I,J,K,L,M](pois L já está em
abertos); fechados=[F,E,D,C,B,A];
abertos = [H,I,J,K,L,M,N];
fechados=[G,F,E,D,C,B,A];
e assim por diante, até que U seja encontrando ou
abertos = [ ]
26
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM AMPLITUDE
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;

27
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS

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.
28
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.
29
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA

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
proibitivo. Ex.: jogo de xadrez.
pode
ser
30
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA

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.
31
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA

Os algoritmos heurísticos são constituídos de
duas partes:

Medida heurística;

Algoritmo (parte que usa as medidas).
32
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA
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.
33
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA
X
X
X
X
O
X
O
O
O
X
X
X
X
O
O
34
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA
X
X
X
3
4
2
35
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA HEURÍSTICA
4
X
O
O
X
O
X
O
X
O
X
X
3
X
O
X
O
X
X
4
4
X
X
5
X
O
O
X
X
X
X
O
X
X
5
4
4
36
4
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;
37
ALGORITMO DE BUSCA HEURÍSTICA
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.
38
ALGORITMO DE BUSCA HEURÍSTICA

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;
39
ALGORITMO DE BUSCA HEURÍSTICA

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.
40
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
a.5
b.4
e.5
g.4
f.5
k
.
l.
s.
t.
d.6
c.4
m.
n
.
i.
h.3
o.2
p.3
u
.
j.
q.
r.
41
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!
42
CÓDIGO JAVA – SUBIDA DA ENCOSTA
43
CÓDIGO JAVA – ESTADOS DO JOGO-DOS-8
44
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
45