Inteligência artificial - Aula 05

Prévia do material em texto

- -1
INTELIGÊNCIA ARTIFICIAL APLICADA A 
JOGOS DIGITAIS
BUSCA EM ESPAÇO DE ESTADOS
- -2
Olá!
Nesta aula, você irá:
1. Apresentar o conceito de busca, em espaço de estados.
2. Estudar as buscas cegas e as heurísticas.
3. Conhecer os subtipos de busca e seus métodos.
No capítulo anterior, aprendemos como formular corretamente os problemas e demos os primeiros passos em
busca das soluções. Agora, neste capitulo, aprenderemos como solucionar problemas através de técnicas de
busca em espaço de estados.
Lembra do problema das jarras, no capítulo anterior?
Ali, nós resolvemos o problema pela chamada força bruta, construindo uma árvore com todos os estados
possíveis, desde o estado inicial, até encontrarmos um estado objetivo.
Mas, nem sempre um problema ou mini-problema possui um espaço de estados pequeno, que permite examinar
todos os casos possíveis e encontrar a solução ou a solução ótima.
Vejamos um exemplo intermediário. Vamos retomar o jogo das 8 peças, apresentado no capítulo anterior, no
qual um tabuleiro com 9 posições contém 8 peças e uma casa vazia, por meio da qual se faz o movimento das
peças. O objetivo do jogo é atingir uma posição final específica (teste de objetivo), a partir de uma posição inicial
qualquer (aleatória, por exemplo), movimentando-se cada peça por meio do espaço vazio.
Vamos simbolizar o problema como uma matriz 3x3, numerando as peças de 1 a 9 e o espaço vazio como 0.
- -3
Aplicar uma função sucessor e construir todos os estados possíveis pode ser bastante complexo e demorado,
com tabuleiros maiores, então, até para um computador isso pode se tornar complicado de se realizar em tempo
razoável.
Vamos, então, pensar de forma inteligente. Como podemos mover as peças? Cada peça pode se mover,
potencialmente, em 4 direções possíveis, isso nos dá 32 regras para os possíveis movimentos. Se imaginarmos o
espaço vazio como uma peça, reduzimos nossas regras para apenas 4, assumindo que o espaço vazio é que é uma
"peça" que pode se movimentar nas quatro direções possíveis.
Teremos, então, quatro movimentos:
MC - movimento do espaço vazio (0) para cima.
MD - movimento do espaço vazio (0) para direita. 
MB - movimento do espaço vazio (0) para baixo. 
ME - movimento do espaço vazio (0) para esquerda.
A solução para o problema se dará pela execução do seguinte algoritmo:
Selecionar uma regra de movimento dentre as quatro possíveis, respeitando obviamente as fronteiras do
tabuleiro. Qual a melhor regra a ser selecionada? É aqui que entra uma parte extremamente importante do
método; lembre-se bem desse passo, dentro do contexto da solução, voltaremos aqui em breve.
Aplique a regra selecionada, gerando um novo estado e, consequentemente, um novo ramo da árvore, filho do
anterior.
Se o novo estado é igual ao estado objetivo, termine; caso contrário, volte ao passo 1.
Dá para perceber que o coração do sistema é o passo 1, pois, é nele que se seleciona (ou se tenta selecionar) a
melhor regra a ser aplicada, diminuindo assim a possibilidade de realizar uma busca muito grande e errática.
Observe a árvore de busca (incompleta):
Obs.: foram descartadas as funções sucessoras, que voltam ao estado anterior.
- -4
Podemos notar que a árvore de busca completa poderia ser bastante extensa, dependendo do estado inicial!
Como encontrar a solução de forma mais rápida, sem fazer a árvore de busca completa?
Para responder, vamos estudar os tipos de busca a seguir.
Busca cega - busca sem informação
Heurística - busca com informação
1 Busca cega
São buscas sem informação. Não há nenhuma informação adicional sobre os estados, além daquela fornecida na
definição do problema.
Vamos estudar dois métodos:
Busca em largura: é um algoritmo usado para realizar uma busca numa estrutura de árvore ou grafo. Começa 
pelo nó raiz e segue, explorando todos os nós vizinhos inexplorados, examinando sistematicamente todos os nós
de unia árvore, sem considerar o seu alvo de busca, até que ele o encontre.
- -5
E assim por diante...
é um algoritmo usado para realizar uma busca numa estrutura de árvore ou grafo.Busca em profundidade: 
Começa pelo nó raiz e se aprofunda, seguindo pela esquerda, explorando tanto quanto possível cada um dos seus
ramos, até que o alvo da busca seja encontrado, ou até que ele se depare com um nó que não possui filhos (nó
folha). Então a busca retrocede (backtrack) e recomeça no próximo nó vizinho.
No problema do quebra cabeça de 8 peças, teríamos a seguinte sequência de estados:
- -6
E assim por diante...
Obs.: As buscas em profundidade podem ser limitadas, isto é, podem ter um limite no qual ao atingi-lo o
algoritmo considera que chegou a um estado que não tem sucessor, ou seja, um nó que não possui filhos (nó
folha). Então, a busca retrocede (backtrack) e recomeça no próximo nó vizinho.
Concluímos que a busca cega encontrará, em média, a solução de forma mais rápida do que utilizando força
bruta, mas poderemos ter soluções ainda mais eficientes? Claro que sim!
2 Heurísticas
São buscas com informação. São utilizadas informações que permitem descobrir se um estado a ser seguido é
mais promissor que outro, dentro da árvore de busca.
Busca A*
Outro método de busca bastante difundido é a busca A* (busca completa e ótima) que, para gerar um novo
estado, dá preferência ao que possui a melhor função de avaliação, considerando nesta função a soma do custo e
a avaliação heurística. Esse método é ótimo e completo, mas com complexidades de tempo e de espaço
exponenciais. Porém, geralmente, gera menos nós que os outros métodos de busca.
Busca gulosa
A busca gulosa é um tipo de irrevogável, isto é, ela se caracteriza por não permitir que se volte atrás no espaço de
busca. Ela é muito utilizada, quando se tem pouco conhecimento do problema tratado.
O que vem na próxima aula
Na próxima aula, você estudará o assunto seguinte:
• Sistemas baseados em conhecimento e os sistemas especialistas.•
- -7
CONCLUSÃO
Nesta aula, você:
• Conheceu a busca em espaço de estados.
• Aprendeu que existem dois tipos de busca: as buscas cegas e as heurísticas.
• Percebeu que há meios de resolver problemas de forma inteligente, sem uso de força bruta.
• Conheceu as buscas em largura, em profundidade, a busca gulosa e busca A*.
• Compreendeu que nem sempre uma busca com uma heurística ótima pode ser a mais eficiente.
• Analisou os métodos de busca, utilizando o jogo das 8 peças.
•
•
•
•
•
•
	Olá!
	
	1 Busca cega
	2 Heurísticas
	O que vem na próxima aula
	CONCLUSÃO