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:
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?

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 o interpretador pode reduzir, da forma mais
eficiente, a complexidade da busca?
 Como se pode projetar um interpretador para que ele
utilize uma linguagem de representação o mais
eficientemente possível?

BUSCA EM ESPAÇOS DE ESTADO
Teoria dos Grafos
 Um grafo consiste:
Conjunto de NÓS;
 Conjunto de ARCOS (Elos)

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.
BUSCA EM ESPAÇOS DE ESTADO

Jogo da Velha
BUSCA EM ESPAÇOS DE ESTADO

Web site
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.
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.
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
BUSCA EM ESPAÇOS DE ESTADO
Árvore
 Relações de Parentesco

a.
c.
b.
e.
f.
g.
h
.
d
.
i.
j.
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.

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.
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.
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.

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS – BUSCA EM PROFUNDIDADE
a.
e.
f.
k
.
l.
s.
t.
d
.
c.
b.
m.
g.
h
.
n
.
o.
i.
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
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS

A 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.
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
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
Implementação do algoritmo de 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.

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
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.

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS

Configuração da lista de abertos
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 = [ ]
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
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;

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
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.

ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS

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;
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS

Configuração da lista de abertos
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.
ESTRATÉGIAS PARA BUSCA EM ESPAÇO DE
ESTADOS
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.

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.
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.

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 pode ser
proibitivo. Ex.: jogo de xadrez.
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á-la a encontrar a solução de
um problema, isto é inerente das heurísticas;
 As “regras práticas” que um especialista humano
usadas para resolver problemas eficientemente
são essencialmente heurísticas quanto a sua
natureza.

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).