Unidade Curricular: Inteligência Artificial

Título: Busca na Inteligência Artificial. Busca Cega.

Tipo: Teórico-prática
Número da Actividade: 04

Sumário:
4.1. Introdução .................................................................................................................. 1
4.2. Exemplos Resolvidos ................................................................................................ 2
4.3. Orientação para o trabalho individual ....................................................................... 7
4.4. Bibliografia ................................................................................................................ 8

4.1. Introdução
A resolução de problemas é fundamental para a maioria das aplicações de IA, daí a
necessidade de estudarmos técnicas para essa finalidade. Na aula anterior estudamos a
busca como forma de solucionar problemas não computáveis. Nesta actividade temos
como objectivo a formulação de problemas de busca e a solução destes usando estratégias
de busca cega. Mas antes de começar vamos a responder algumas perguntas:
Defina o que vem a ser um problema para IA?
É a busca de um caminho (sequência de acções) que ligue a descrição inicial do
problema com uma descrição do estado desejado para o problema. É formular, buscar,
executar. A formulação de um problema é o processo de decidir que acções e estados
devem ser considerados, dado um objectivo. A busca é o processo de buscar por tal
sequência de acções que alcançam o objectivo, um algoritmo de busca recebe um
problema como entrada e devolve uma solução sob a forma de uma sequência de acções.
Depois que uma solução é encontrada, as acções recomendadas podem ser executadas.
Isso se chama fase de execução.
Defina os elementos mínimos necessários a serem considerados para a formulação
de um problema em IA.
Um problema pode ser formulado a partir do:
• O estado inicial onde se encontra o agente;
• O conjunto de acções possíveis disponíveis. O termo operador se usa para
denotar a descrição de uma acção em termos de qual estado será alcançado
executando a acção em um estado particular;
• O teste de objectivo, que determina se o estado final foi alcançado.

Elaborado por: Eng.ª Lissette Montero Herrera | 1

Defina outros conceitos associados à resolução de problemas em IA: espaço de
estados, espaço de busca, caminho, solução e custo da solução.
• O espaço de estados do problema é o conjunto de todos os estados
acessíveis a partir do estado inicial mediante uma sequência de acções
qualquer.
• O espaço de busca é a parte do espaço de estados que deixa de ser abstracta,
quer dizer vai-se construindo ao longo do processo de busca. É um
subconjunto do espaço de estados.
• Um caminho no espaço de estado é uma sequência de acções que conduz
de um estado a outro.
• Uma solução é um caminho do estado inicial a um estado que satisfaz o
critério objectivo.
• O custo de um caminho é uma função que atribui um custo a um caminho.
O que é uma estratégia de busca? Como se podem classificar as estratégias de busca?
Uma estratégia de busca define o critério para seleccionar o seguinte nó a ser
expandido. Em geral, as estratégias de busca se podem agrupar em duas grandes categorias:
busca cega e busca informada. Na busca cega não existe nenhuma informação para decidir
que nó expandir, não se conhece a quantidade de passos ou o custo do caminho do estado
actual até o objectivo. Na busca informada se estima qual o melhor nó a ser expandido.
Quais são os sentidos da busca estudados?
A busca pode ser dirigida por dados (forward) ou dirigida por objectivo (backward).
Na busca forward o nó raiz da árvore de busca é o estado inicial, entretanto o estado final ou
objectivo é um nó folha. Já na busca backward é o contrário, o nó raiz da árvore de busca é o
estado final, e o estado inicial é um nó folha.
Como avaliar o desempenho das estratégias de busca?
O desempenho de um algoritmo de busca depende de alguns critérios:
• Completa: se existir uma solução para o problema, ela será encontrada em
tempo finito;
• Discriminatória: caso existam várias soluções, encontra a melhor;
• Económica: encontra a solução o mais rápido possível e ocupando o menor
espaço de memória possível.

4.2. Exemplos Resolvidos

A continuação iremos resolver alguns exercícios, começando pelos problemas já
estudados na aula anterior.

Elaborado por: Eng.ª Lissette Montero Herrera | 2

Exemplo #1: (Problema de 8-puzzle)
Em um tabuleiro 3×3 com 8 peças numeradas e um quadrado vazio, uma peça
adjacente ao quadrado vazio pode-se mover para esse quadrado. O objectivo é alcançar
um estado onde as peças estão ordenadas, conforme um critério.

a) Formular o problema de busca.

b) Construir um espaço de busca seguindo uma estratégia de busca cega em largura
(forward).
c) Determinar qual o tamanho do espaço de estados deste problema.
Solução:
a) Formulação do problema
Inicial para formular um problema de busca devemos definir mínimo os seguintes
elementos:

Estado Inicial:

Estado Final:

Acções: Mover as peças para o quadrado adjacente vazio que se encontra:

1. Acima;
2. Abaixo;
3. A direita;
4. A esquerda.
b) Construir um espaço de busca seguindo uma estratégia de busca cega em largura.
O espaço de busca é a parte do espaço de estados que deixa de ser abstracta, quer dizer,
é um subconjunto do espaço de estados alcançado ao longo do processo de busca. Nos
vamos apenas construir um espaço de busca com 7 estados. Neste caso desejamos fazer
uma busca em largura dirigida por dados, por isso devemos começar pelo estado inicial.
Observar que na medida que se geram os nós, na árvore de busca estes são identificados
com um número que indica a ordem de geração.

Elaborado por: Eng.ª Lissette Montero Herrera | 3

 1
Observações:
1. Primeiro gerar todos os sucessores do
nó raiz. Em seguida, continuar
expandindo o nó mais profundo da
2 3 4 5 árvore.
2. Não repetir nós na árvore de busca e
aplicar as acções na ordem que foi
definida.
3. O algoritmo termina quando se
6 7 encontra uma solução, quer dizer, um
caminho que liga os estados inicial e
final.

A linha c) do exercício fica para trabalho individual.

Exemplo #2: (Problema dos Missionários e Canibais)

O problema consiste em 3 missionários e 3 canibais que desejam atravessar com
segurança um rio, dispondo para isso de um bote que pode transportar no máximo duas
pessoas. Acontece que em momento nenhum, em ambas margens do rio, pode haver um
número de canibais superior ao número de missionários, porque nesse caso os canibais
podem comer aos missionários.

a) Formular o problema de busca.

b) Construir um espaço de busca seguindo uma estratégia de busca cega em largura
(forward).
c) Construir um espaço de busca seguindo uma estratégia de busca cega em
profundidade (forward).
Solução:
a) Formulação do problema
Neste caso é importante definirmos como representar os estados do problema, além dos
restantes elementos da formulação vistos no exercício anterior.
Estados: Uma descrição de estado especifica quantos missionários e canibais temos em
ambas margens do rio. Por tanto, vamos a utilizar uma estrutura da seguinte forma:

Elaborado por: Eng.ª Lissette Montero Herrera | 4

Estado Inicial:

Estado Final:
Acções: Podem atravessar de uma margem a outra:
1. Dois missionários;
2. Dois canibais;
3. Um missionário e uma canibal;
4. Um missionário;
5. Um canibal.
As linhas b) e c) deste exercício devem ser resolvidas em trabalho individual.

Exemplo #3: (Problema do Mapa de Cidades)

O objectivo é buscar um caminho que
conecte uma cidade a outra, mediante um
mapa. Sua trajectória deverá começar na
cidade S e terminar na G.
a) Formular o problema de busca.
b) Construir um espaço de busca seguindo uma estratégia de busca cega em largura
(forward).
c) Construir um espaço de busca seguindo uma estratégia de busca cega em
profundidade (forward).
d) Determinar qual o tamanho do espaço de estados deste problema.
Solução:
a) Formular o problema de busca.
Estado Inicial: S Estado Final: G
Acções: Neste caso como o problema está representado em um grafo, onde os vértices
são os estados do problema e as arestas são as transições entre um estado e outro, então
iremos a utilizar a matriz de adjacência (MA) para representar as acções.

Elaborado por: Eng.ª Lissette Montero Herrera | 5

 S A B C D E F G
0 1 0 0 1 0 0 0 S
1 0 1 0 1 0 0 0 A
0 1 0 1 0 1 1 0 B
0 0 1 0 0 0 0 0 C
MA =
1 1 0 0 0 1 0 0 D
0 0 1 0 1 0 1 0 E
0 0 1 0 0 1 0 1 F
[0 0 0 0 0 0 1 0] G

b) Construir um espaço de busca seguindo uma estratégia de busca cega em largura

(forward).
A continuação iremos mostrar, passo a passo, a construção da árvore de busca utilizando
uma estratégia de busca cega em largura. Inicialmente na árvore apenas está o estado
inicial S porque é uma busca forward. Expandido S temos dois novos estados, A e D. Em
seguida é a vez do estado A ser expandido, de A posso ir aos estados S, B e D, porém
apenas B pode ser inserido na árvore porque não se permitem nós repetidos. De forma
semelhante acontece com o estado D. Nesse nível todos os estados já foram analisados,
dessa forma pode-se passar para o nível seguinte, começando por B. Do estado B pode-
se ir aos estados A, C, E e F, porém apenas C e F são inseridos na árvore. Em seguida,
é a vez do estado E de ser expandido, o que acontece em este caso é que desde E pode-se
ir aos estados B, D e F, todos eles já inserido na árvore, por isso o estado E não pode
ser expandido. O algoritmo continua conforme apresentado.

c) Construir um espaço de busca seguindo uma estratégia de busca cega em profundidade

(forward).

Elaborado por: Eng.ª Lissette Montero Herrera | 6

A continuação iremos mostrar, passo a passo, a construção da árvore de busca usando
uma estratégia de busca cega em profundidade. Inicialmente na árvore apenas está o
estado inicial S porque é uma busca forward. Os filhos de S são os estados A e D. Em
seguida se expande o estado A, de A podemos ir aos estados S, B e D, porém apenas B
pode ser inserido na árvore porque não se permitem nós repetidos. Continuamos
expandindo B porque é o estado mais profundo da árvore, do estado B podemos chegar
aos estados A, C, E e F, mas A já está na árvore de busca. Do estado C apenas se pode
ir ao estado B que já está inserido na árvore, nesse caso como não tem sucessores é
retirado da borda e se analisa o estado E, quem também não tem sucessores para serem
inseridos, por tanto se procede da mesma forma. Por último se expande o estado F, de F
podemos ir aos estados B, E e G, mas só vai-se inserir na árvore o estado G porque não
se permitem nós repetidos. A busca termina uma vez que encontramos o estado final.

4.3. Orientação para o trabalho individual

Realizar as seguintes actividades:
• Do livro básico da disciplina (Russell & Norvig, 2013), realizar o estudo do
Capítulo 3, epígrafes 3.1-3.4, páginas 98-126.
• Resolver os exercícios propostos na Actividade 05.

Elaborado por: Eng.ª Lissette Montero Herrera | 7

4.4. Bibliografia
Russell, S., & Norvig, P. (2013). Inteligência Artificial. Elsevier Editora Ltda.

Elaborado por: Eng.ª Lissette Montero Herrera | 8