13-Buscas

Prévia do material em texto

1
Resolução de Problemas 
e
Técnicas de Busca
2
Resolução de Problemas
- Resolver problemas é um indicador de inteligência
- Para resolver problemas em computadores é preciso encontrar 
estruturas capazes de representá-los
-As estruturas mais usadas na prática são os grafos e árvores, 
para os quais existe um bom conjunto de técnicas destinadas ao seu 
processamento
3
Representação de Problemas e Espaço de Estados
Usando os grafos:
-Os nós representam os estados que podem ocorrer em diferentes 
etapas da resolução do problema
- Os arcos representam ações que transformam um estado em 
outro
Estado 1
Estado 2
Estado 3
Estado 1
Estado 2
Estado 3
4
Representação de Problemas e Espaço de Estados
Um exemplo de resolução de problema
Missionários x Canibais
Objetivo
encontrar os passos para que três missionários e três canibais 
consigam atravessar um rio, de um lado para o outro, usando apenas 
um barco, que consegue transportar, no máximo, dois passageiros 
de cada vez e, de modo que, nunca o número de canibais ultrapasse 
o número de missionários em qualquer uma das margens do rio
Algumas variações:
- Fazendeiro, lobo, cabra e pacote de alface
- etc.
http://rachacuca.com.br/jogos/missionarios-e-canibais/
5
Representação de Problemas e Espaço de Estados
Missionários x Canibais
6
Representação de Problemas e Espaço de Estados
Missionários x Canibais
Usando um grafo com os estados
Resolver o problema
Usar técnicas de busca para encontrar um caminho 
que leve do estado inicial até o estado final
7
Representação de Problemas e Espaço de Estados
Jogo dos quadradinhos (Nim)
Usando um grafo com os estados
?
?
8
Representação de Problemas e Espaço de Estados
Decomposição de Problemas
- A complexidade dos problemas sempre deve ser considerada
- número de prováveis caminhos é muito grande
- impossível de ser processado (problemas combinatórios)
- não podem ser resolvidos em tempos viáveis
Solução (dividir para conquistar)
- verificar se o problema pode ser dividido em problemas menores
- Problemas menores possuem soluções menos complexas
- Assim, a resolução do problema principal deverá ser obtida 
resolvendo os problemas menores 
9
Técnicas de Busca
- Muitas técnicas de busca operam sobre uma estrutura de árvore
- Para aplicar estas técnicas em um grafo é preciso usar um 
mecanismo de controle para:
- que todos os nós possam ser visitados
- não se visite um mesmo nó várias vezes
- Este controle é geralmente realizado com o apoio de uma lista de 
nós a visitar
10
Técnicas de Busca
Procedimento genérico
Inicialmente, colocar o primeiro nó (nó inicial) na lista e, a cada nó
visitado, retirar o nó da lista e aplicar a função teste para 
verificar se é um nó meta (solução do problema)
Em caso afirmativo, interrompe-se a busca
Caso contrário, o nó é expandido (seus filhos são colocados na lista)
Um nó X é filho de um nó Y se acessado por um único arco a partir 
do nó Y, e não é filho de outro nó
11
Técnicas de Busca
Tipos de buscas
Buscas cegas
visitam todos os nós adotando alguma sequência
Buscas heurísticas
- Usam alguma informação para estimar o custo de cada ação, como, 
por exemplo, uma distância estimada entre o nó atual e a meta
- Tentam encontrar uma solução de forma mais rápida, do que 
percorrer todos os nós da árvore
12
Técnicas de Busca
Medidas de desempenho dos algoritmos de busca
Completeza
- quando o algoritmo sempre encontra uma solução, se ela existe
Otimização
- quando o algoritmo encontra a solução ótima
Complexidade de tempo
- se refere ao tempo máximo exigido pelo algoritmo para realizar a 
busca
Complexidade de memória
- se refere à quantidade máxima de memória usada pelo algoritmo, 
geralmente, utilizada para guardar informações sobre os nós 
visitados e a serem visitados (Lista)
13
Técnicas de Busca
Deseja-se encontrar um caminho entre os nós A e I
Os valores sobre os arcos indicam a distância entre os nós ou o custo para 
transformar um estado no outro
O valor dentro do nó é uma distância estimada entre o nó e a meta (estado final) 
(não é uma medida exata), mas pode ser usada para acelerar a busca
Por simplicidade, considera-se que os nós filhos devem sempre suceder os pais 
alfabeticamente (evita-se os loops que ocorrem na prática)
14
Técnicas de Busca
Técnicas de Buscas Cegas
Usam uma lista para manter o controle sobre os nós já visitados
As buscas cegas mais conhecidas são: 
- busca em amplitude ou largura, ou extensão ou ainda busca 
em níveis (breadth-first); 
- busca em profundidade (depth-first ); 
- busca bidirecional
15
Técnicas de Busca
Busca em Amplitude ou Largura
- Sempre insere o nó a ser visitado no final da lista de controle
- Consequentemente, percorre os nós mais próximos ao nó inicial e, em 
seguida, os nós que estão a dois arcos do nó inicial
- Por isto, também é conhecida por busca em níveis
- Como os nós são inseridos no final e retirados do início da lista, tem-
se uma estrutura FIFO (First In First Out )
16
Técnicas de Busca
Busca em Amplitude ou Largura
- nó A (início) 
- nó I (meta) 
Inicialmente, a lista está vazia e o 
nó A (estado inicial) é inserido na lista Lista = A
O nó A é visitado e, como não é o nó meta, deve ser expandido (seus 
filhos B, C e D ) são colocados no final da lista. O nó A é removido
O próximo nó B é visitado (também não é a meta), então é expandido, 
(seus filhos E e F ) são inseridos no final da lista e B é removido
17
Técnicas de Busca
Busca em Amplitude ou Largura
O nó C é o próximo a ser visitado 
e, como também não é a meta, será
expandido e eliminado
18
Técnicas de Busca
Busca em Profundidade
- Os nós a serem visitados são inseridos no início da lista
- Assim, serão percorridos todos os nós nível abaixo, até atingir o nó
mais distante da raiz, quando, então, a busca precisa retornar um 
nível acima para continuar
- Como os nós são inseridos no início da lista e sempre retirados do 
início da mesma para serem visitados, tem-se uma estrutura LIFO
(Last In First Out )
19
Técnicas de Busca
Busca em Profundidade
- nó A (início) 
- nó I (meta) 
Inicialmente, a lista está vazia e 
o nó A (estado inicial) é inserido na lista Lista = A
O nó A é visitado e, como não a meta, é expandido (seus filhos B,C e D) 
são inseridos no início da lista (nó A é removido)
A lista fica:
O próximo nó visitado é B (não é a meta), então é expandido (filhos E e 
F são inseridos no inicio da lista) e B é removido
A lista agora é:
20
Técnicas de Busca
Busca em Profundidade
Agora o nó E será o próximo 
a ser visitado. Como também 
não é a meta, será expandido 
(filhos K e L) e eliminado, e a lista assim ficará:
Agora o nó K é visitado e, como não possui filhos será eliminado
O próximo nó a visitar é L, ...
21
Técnicas de Busca
Busca Bidirecional
Procura evitar o aumento excessivo de nós a visitar com a busca em 
largura (a cada nível abaixo o número de nós aumenta muito)
A busca bidirecional usa duas buscas em largura
- uma partindo do nó inicial e 
- outra partindo do nó meta
- o processo termina quando as duas buscas se interceptam
Custos
- busca em largura é bd
- busca bidirecional é bd/2 + bd/2
Onde: d é o número de níveis 
b é o número de nó nos níveis
22
Técnicas de Busca
Busca Bidirecional
as buscas partindo de A e I
se interceptarão no nó D, 
que está no primeiro nível da 
busca partindo por A e também por I
A busca é encerrada quando após percorrer um nível de cada lado, 
23
Técnicas deBusca
Técnicas de Buscas Heurísticas
- usam algoritmos baseados em um conhecimento que pode ajudar a acelerar a 
solução do problema
- uma estimativa da distância entre os nós e a meta
- Em geral, os parâmetros são incertos e não garantem uma solução 
ótima (ou mesmo uma solução)
- Na maioria das vezes, conseguem acelerar o processo
- As buscas heurísticas exploram direções aparentemente boas
Em suas tarefas diárias, as pessoas sempre usam heurísticas
Exemplos: Alguém diz que perdeu suas chaves 
� As buscas são nos locais mais prováveis (chão, sobre uma mesa, etc)
Alguém procura água em uma mata
� As buscas são feitas nos vales
24
Técnicas de Busca
Técnicas de Buscas Heurísticas
- Alguns autores consideram como heurísticas apenas as estratégias 
não numéricas
- ex. para sair de uma floresta : evite virar sempre para a esquerda,
pois poderá ficar andando em círculos
- Para estes autores, quando são usados valores numéricos para a 
tomada de decisões, considera-se então estar usando uma função de 
avaliação ou função de custo, e não uma heurística
função de avaliação 
- estima a distância entre o estado atual e a meta
funções de custo
- medem (exatamente) a dificuldade para ir de um estado para o seu vizinho
25
Técnicas de Busca
Técnicas de Buscas Heurísticas (Busca pela melhor escolha)
- Seleciona os nós de acordo com uma "função de avaliação“
- Coloca os nós a visitar em uma "lista", ordenada pelo valor da função de avaliação
- A função de avaliação mede 
- o esforço para ir do Nó atual até a meta
- não se sabe o caminho exato até a meta (apenas uma estimativa)
Quando a busca sempre escolhe o nó mais próximo da meta, entre todos os nós 
filhos, é chamada busca GULOSA (Greedy) pela melhor escolha
Na verdade, o termo busca pela melhor escolha é genérico, englobando diversas 
buscas heurísticas
26
Técnicas de Busca
Técnicas de Buscas Heurísticas 
(Busca pela melhor escolha)
Exemplo:
Partindo de A, avalia os nós filhos B, C e D e a lista ficará
A D C B A
43 45 68 / | \
/ | \
B C D
Então vai por D (busca gulosa)
27
Técnicas de Busca
Técnicas de Buscas Heurísticas 
(Busca pela melhor escolha)
Exemplo:
Porém D não é a meta, assim, será removido da lista e expandido:
lista
A I J D C B
0 28 45 68
Agora, visita o nó I, que é a meta
O trajeto encontrado foi A->D->I
com comprimento 61 + 43 = 104
Obs. - Existem caminhos mais curtos entre A e I
- Caso chegue a um beco, consegue voltar por causa da "lista" 
28
Técnicas de Busca
Técnicas de Buscas Heurísticas (Busca subindo o morro - Hill Climbing)
- Também é uma busca pela melhor escolha
- Não usa a lista de nós a visitar
- Move-se na direção de um melhor valor (objetiva atingir o topo – meta)
- Quando vai para o primeiro nó filho melhor que o nó atual é chamada busca 
subindo o morro simples
- Quando sempre vai para o melhor dos filhos, é chamada busca subindo o morro 
trilha mais íngreme (gulosa)
Esta busca apresenta dois problemas:
- Falsos picos: Quando uma direção parece melhor, mas depois se conclui que não era
-Platôs: Um estado em que todos os nós filhos tem o mesmo valor na função de avaliação
29
Técnicas de Busca
Técnicas de Buscas Heurísticas 
Busca subindo o morro Simples
Início: nó A
Como não é a meta, vai para primeiro 
nó filho, mais próximo da meta que o nó atual A 67
/ | \
B C D
Logo, vai por C (também não é a meta) 68 45 43
Então, vai testar os filhos de C, no caso F, G e H A 67
|
Então, vai por G. C 45
/ | \
Em seguida, chegará a meta I F G H
50 28 21
(O trajeto agora foi A->C->G->I=74)
30
Técnicas de Busca
Técnicas de Buscas Heurísticas (Busca menor custo - A*)
Explora o nó com menor custo total, o que inclui o custo exato para 
sair do início e chegar ao nó atual e também o custo estimado para ir 
do nó atual até a meta
Esta busca usa uma lista, ordenada pelos custos totais, assim, caso a 
exploração de um caminho não encontre uma solução, a busca poderá
voltar a tentar um outro caminho
31
Técnicas de Busca
Técnicas de Buscas Heurísticas 
(Busca menor custo - A*)
Exemplo:
Iniciando em A, que não é a meta vai calcular os custos dos filhos de A
custo: B = 15 + 68 = 83 A
C = 23 + 45 = 68 15 / | \ 61
D = 61 + 43 = 104 / |23 \
B C D
e a lista ficará A C B D 68 45 43
68 83 104
32
Técnicas de Busca
Técnicas de Buscas Heurísticas 
(Busca menor custo - A*)
Então vai por C, que também não 
é a meta, então, remove e expande C
Os custos dos filhos de C são: A 
F = 23 + 13 + 50 = 86 15 / | \ 61
G = 23 + 23 + 28 = 74 / |23 \
H = 23 + 25 + 21 = 69 B C D
/ | \
13/ 23| \ 25
F G H
50 28 21
e a lista ficará: A C H G B F D
69 74 83 86 104 
33
Técnicas de Busca
Técnicas de Buscas Heurísticas 
(Busca menor custo - A*)
Agora, vai por H (falso pico)
se fosse por G chegaria mais rapidamente
Remove e expande H
custo do filho de H: J = 23 + 25 + 16 + 28 = 92
e a lista ficará: A C H G B F J D
74 83 86 92 104
Então, visita G, Remove e expande G e o seu filho I tem custo
custo de I = 23 + 23 + 28 + 0 = 74
Agora a lista ficará: A C H G I B F J D
74 83 86 92 104
Então, agora o nó I é visitado, pelo caminho de menor custo
34
Técnicas de Busca
Técnicas de Buscas Heurísticas 
Busca com Adversários
Precisam considerar seus próprios movimentos e também os movimentos de seu 
adversário
Isto é feito tentando:
- maximizar o ganho de seus movimentos
- minimizando o ganho do seu adversário 
(estrago que ele lhe faz)
A estratégia mais 
usada é o
algoritmo min-max
35
Técnicas de Busca
Técnicas de Buscas Heurísticas 
Busca com Adversários (algoritmo min-max)
Supondo os valores dos Nós a seguir:
O maior problema do min-max é a grande quantidade de nós para avaliar
36
Técnicas de Busca
Técnicas de Buscas Heurísticas 
Busca com Adversários (algoritmo min-max)
Poda alfa-beta
Está estratégia diminui o numero de nós a serem avaliados
A busca avalia os nós E, F e G, para encontrar o minimo = 3� atribui B=3
Em seguida, avalia H=2. 
Como o valor de H é menor que o valor de B, não precisa avaliar I e J
Em seguida, avalia K e L. Como L=1, menor que B, não precisa avaliar M e N 
Deste modo, diminui-se o numero de nós a avaliar
37
Técnicas de Busca
Trabalho prático
Implemente um programa (linguagem livre) para resolver o jogo dos quadradinhos
1) O tabuleiro inicia com as peças no lugar correto 
e o usuário diz quantos movimentos aleatórios devem 
ser feitos para misturar as peças
2) Usar: a) Busca aleatória (movimentos aleatórios)
b) Heurística 1 – análise em um nível
c) Heurística 2 – análise em dois níveis
d) Heurística pessoal
3) Anotar o número de movimentos necessários 
para obter a resposta final, usando as três 
abordagens (em um relatório)
4) Evitar loops, anotando os últimos movimentos
em um array e, verificando se ocorrem repetições
(quando houver, impeça)
Trabalho em duplas
Entrega: 25/04/2014
Código + exe (email) 
Código + relatório (impresso)