Resolução de Problemas por meio de
Busca
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
3
Buscando Soluções
Busca Heurística = Conhecimento
4
Busca Heurística ou Informada

Estratégias de Busca Cega
• encontram soluções para problemas pela geração
sistemática de novos estados, que são comparados ao
objetivo;
• são ineficientes na maioria dos casos:
- são capazes de calcular apenas o custo de caminho do nó atual ao nó
inicial (função g), para decidir qual o próximo nó da fronteira a ser
expandido.
- essa medida não necessariamente conduz a busca na direção do objetivo.
• Como encontrar um barco perdido?
- não podemos procurar no oceano inteiro...
5
Busca Heurística

Estratégias de Busca Heurística
• utilizam conhecimento específico do problema na escolha do
próximo nó a ser expandido
• barco perdido
- correntes marítimas, vento, etc...

Aplica de uma função de avaliação a cada nó na fronteira do
espaço de estados
• essa função estima o custo de caminho do nó atual até o objetivo
mais próximo utilizando uma função heurística

Heurística
• do grego heuriskein, encontrar, descobrir
• introduzida em IA por George Polya em 1957 (livro How to Solve It)
• é conhecimento e, por isso, marcou quebra da IA com a pesquisa
operacional
6
Funções Heurísticas

Função heurística (h)
• estima o custo do caminho mais barato do estado atual até o
estado final mais próximo.
• são específicas para cada problema

Exemplo:
• encontrar a rota mais curta entre duas cidades
• hdd(n) = distância direta entre o nó n e o nó final.

Como escolher uma boa função heurística?
• ela deve ser admissível, i.e., nunca superestimar o custo real da
solução
• ex. distância direta (hdd) é admissível porque o caminho mais
curto entre dois pontos é sempre uma linha reta
7
Busca pela Melhor Escolha (BME)
Best-First Search


Busca genérica onde o nó de menor custo “aparente” na fronteira
do espaço de estados é expandido primeiro
Duas abordagens básicas:
1. Busca Gulosa (Greedy search)
2. Algoritmo A* e suas variantes

Algoritmo:
Função-Insere - ordena nós com base na Função-Avaliação
função Busca-Melhor-Escolha (problema,Função-Avaliação)
retorna uma solução
Busca-Genérica (problema, Função-Insere)
8
Busca Gulosa


Semelhante à busca em profundidade com backtracking
Tenta expandir o nó mais próximo do nó final com base na
estimativa feita pela função heurística h(n).

Função-Avaliação = Função Heurística h(n)

Algoritmo:
função Busca-Gulosa (problema)
retorna uma solução ou falha
Busca-Melhor-Escolha (problema, h)
Exemplo: Ir de Arad a Bucharest
Busca Gulosa...
11
Busca Gulosa

Custo de busca mínimo!
• No exemplo, não expande nós fora do caminho

Porém não é ótima:
• No exemplo escolhe o caminho que é mais econômico à
primeira vista, via Fagaras
• porém, existe um caminho mais curto via Rimnicu Vilcea

Não é completa:
• pode entrar em loop se não detectar a expansão de
estados repetidos
• pode tentar desenvolver um caminho infinito

Custo de tempo e memória: O(bd)
12
Algoritmo A*

É ainda a técnica de busca mais usada

Tenta minimizar o custo total da solução combinando:
• Busca Gulosa: econômica, porém não é completa nem ótima
• Busca de Custo Uniforme (Djikstra): ineficiente, porém
completa e ótima

Função de avaliação:
• f (n) = g (n) + h (n)
• g (n) = distância de n ao nó inicial
• h (n) = distância estimada de n ao nó final
• A* expande o nó de menor valor de f na fronteira do espaço
de estados.
13
Algoritmo A*


Se h é admissível, f (n) nunca irá superestimar o custo real
da melhor solução através de n.
Algoritmo:
função Busca-A* (problema)
retorna uma solução ou falha
Busca-Melhor-Escolha (problema, g+h)
Algoritmo A* : exemplo
Ir de Arad a Bucharest
14
Algoritmo A*: outro exemplo
Viajar de Arad a Bucharest
Usando A*
17
Algoritmo A*: análise do comportamento

A estratégia é completa e ótima

Custo de tempo:
• exponencial com o comprimento da solução, porém boas funções
heurísticas diminuem significativamente esse custo
- o fator de expansão fica próximo de 1

Custo memória: O (bd)
• guarda todos os nós expandidos na memória
- para possibilitar o backtracking

Eficiência ótima
• só expande nós com f(n)  f*, onde f* é o custo do caminho ótimo
- f é não decrescente
• nenhum outro algoritmo ótimo garante expandir menos nós
A* define Contornos
. fator de expansão
próximo de 1
18
19
Busca com Limite de Memória
Memory Bounded Search

IDA* (Iterative Deepening A*)
• igual ao aprofundamento iterativo, porém seu limite é dado
pela função de avaliação (f) (contornos), e não pela
profundidade (d).
• necessita de menos memória do que A* mas continua ótima

SMA* (Simplified Memory-Bounded A*)
• O número de nós guardados em memória é fixado previamente
- conforme vai avançando, descarta os piores nós (embora guarde
informações a respeito deles) e atualiza os melhores valores dos caminhos
• É completa e ótima se a memória alocada for suficiente
IDA* - Iterative Deepening A*
20
SMA* (Simplified Memory-Bounded A*)
21
Busca - Funções Heurísticas e
Algoritmos de Melhorias Interativas
22
23
Inventando Funções Heurísticas

Como escolher uma boa função heurística h?

h depende de cada problema particular.

h deve ser admissível
• não superestimar o custo real da solução

Existem estratégias genéricas para definir h:
1) Relaxar restrições do problema;
2) Usar informação estatística;
3) Identificar os atributos mais relevantes do
problema
4) “Aprender” a heurística pela experiência
- Aprendizagem de máquina
24
(1) Relaxando o problema

Problema Relaxado:
• versão simplificada do problema original, onde os
operadores são menos restritivos


Exemplo: jogo dos 8 números:
• operador original: um número pode mover-se de A para B se A é
adjacente a B e B está vazio
4 5 8
• busca exaustiva  320 estados possíveis
1 6
- Fator de ramificação  3 e d  20 passos
7 2 3
Operadores relaxados:
1. um número pode mover-se de A para B (h1)
2. um número pode mover-se de A para B se A é adjacente a B (h2)
Estratégias para definir h
(1) Relaxando o problema


O custo de uma solução ótima para um problema relaxado
é sempre uma heurística admissível para o problema
original.
Existem softwares capazes de gerar automaticamente
problemas relaxados
•Se o problema for definido em uma
linguagem formal


Existem também softwares capazes de gerar
automaticamente funções heurísticas para problemas
relaxados
Ex.: CPLEX 7.5
25
26
(2) Usando informação estatística

Funções heurísticas podem ser “melhoradas” com
informação estatística:
• executar a busca com um conjunto de treinamento (e.g., 100
configurações diferentes do jogo), e computar os resultados.
• se, em 90% dos casos, quando h (n) = 14, a distância real da
solução é 18,
• então, quando o algoritmo encontrar 14 para o resultado da
função, vai substituir esse valor por 18.

Informação estatística expande menos nós, porém
elimina admissibilidade:
• em 10% dos casos do problema acima, a função de avaliação
poderá superestimar o custo da solução, não sendo de grande
auxílio para o algoritmo encontrar a solução mais barata.
27
(3) Usando atributos/características


Características do problema podem ser usadas para
mensurar o quão se está próximo da solução
ex. xadrez
•número de peças de cada lado
•somatório dos pesos das peças de cada lado
(Peão-1, ..., Rainha-9)
•número de peças sob ataque

Quando não se conhece a importância das características,
pode-se aprendê-las (w1f1+w2f2+...+wnfn)
28
Qualidade da função heurística

Qualidade da função heurística: medida através do fator de
expansão efetivo (b*).
• b* é o fator de expansão de uma árvore uniforme com N
nós e nível de profundidade d
• N = 1 + b* + (b*)2 + ... + (b*)d , onde
N = total de nós expandidos para uma instância de problema
d = profundidade da solução;

Mede-se empiricamente a qualidade de h a partir do conjunto
de valores experimentais de N e d.
• uma boa função heurística terá o b* muito próximo de 1.

Se o custo de execução da função heurística for maior do que
expandir nós, então ela não deve ser usada.
• uma boa função heurística deve ser eficiente
29
Heurísticas para jogo 8 números

Heurísticas possíveis
• h1 = no. de elementos fora do lugar (h1=7)
• h2 = soma das distâncias de cada número à posição
final (h2=2+3+3+2+4+2+0+2=18)
- Manhattan Distance d de dois pontos (x,y) e (u,v), d = |x-u| + |y-v|
30
Escolhendo Funções Heurísticas

É sempre melhor usar uma função heurística com valores
mais altos, contanto que ela seja admissível.
• ex. h2 melhor que h1

hi domina hk  hi(n)  hk(n) "n no espaço de estados
• h2 domina h1 no exemplo anterior

Caso existam muitas funções heurísticas para o mesmo
problema, e nenhuma delas domine as outras, usa-se uma
heurística composta:
• h (n) = max (h1 (n), h2 (n),…,hm(n))
• Assim definida, h é admissível e domina cada
função hi individualmente
Estratégias para definir h
(2) Aprendendo a heurística

Definindo h com aprendizagem automática
(1) Criar um corpus de exemplos de treinamento
•Resolver um conjunto grande de problemas
- e.g., 100 configurações diferentes do jogo dos 8 números
•Cada solução ótima para um problema
provê exemplos
- Cada exemplo consiste em um par
- (estado no caminho “solução”, custo real da solução a partir
daquele ponto)
31
Estratégias para definir h
(2) Aprendendo a heurística
(2) Treinar um algoritmo de aprendizagem indutiva
•Que então será capaz de prever o custo de
outros estados gerados durante a execução
do algoritmo de busca
32
Experimento com 100 problemas
Uma boa função heurística terá o b* muito próximo de 1.
33
Na sequencia....

Algoritmos de Melhorias Iterativas
34
Algoritmos de Melhorias Iterativas

Dois exemplos clássicos
•Subida da encosta (Hill-Climbing)
•Têmpera simulada (Simulated Annealing)
35
Algoritmos de Melhorias Iterativas
(Iterative Improvement Algorithms)

Idéia geral
•começar com um estado inicial
- configuração completa, solução aceitável
•e tentar melhorá-lo iterativamente
•E.g., ajustar a imagem da TV com antena
interna

Os estados são representados sobre uma superfície
(gráfico)
•a altura de qualquer ponto na superfície
corresponde à função de avaliação do
estado naquele ponto
36
Exemplo de Espaço de Estados
37
Algoritmos de Melhorias Iterativas

O algoritmo se “move” pela superfície em busca de pontos
mais altos
• Objetivos (onde a função de avaliação é melhor)
- Objetivos são estados mais adequados

O ponto mais alto corresponde à solução ótima
• máximo global
- nó onde a função de avaliação atinge seu valor máximo

Aplicações: problemas de otimização
• por exemplo, linha de montagem, rotas, etc.
38
Algoritmos de Melhorias Iterativas

Esses algoritmos guardam apenas o estado atual, e não
vêem além dos vizinhos imediatos do estado
• Contudo, muitas vezes são os melhores métodos
para tratar problemas reais muito complexos.

Duas classes de algoritmos:
• Subida da Encosta ou Gradiente Ascendente
- Hill-Climbing
- só faz modificações que melhoram o estado atual.
• Têmpera Simulada
- Simulated Annealing
- pode fazer modificações que pioram o estado temporariamente
para fugir de máximos locais
39
Subida da Encosta - Hill-Climbing

O algoritmo não mantém uma árvore de busca:
• guarda apenas o estado atual e sua avaliação

É simplesmente um “loop” que se move
• na direção crescente da função de avaliação
- para maximizar
• ou na direção decrescente da função de avaliação
- para minimizar
- Pode ser o caso se a função de avaliação representar o custo, por
exemplo...
40
Subida da Encosta: algoritmo

função Hill-Climbing (problema) retorna uma solução
variáveis locais: atual (o nó atual), próximo (o próximo nó)
atual  Estado-Inicial do Problema
loop do
próximo  sucessor do nó atual de maior/menor valor
(i.e., expande nó atual e seleciona seu melhor filho)
se Valor[próximo] < Valor[atual ] (ou >, para minimizar)
então retorna nó atual (o algoritmo pára)
atual  próximo
end
41
Exemplo de Subida da Encosta
Cálculo da menor rota com 5 nós


estado inicial = (N1, N2, N3, N4, N5)
f = soma das distâncias diretas entre cada nó, na ordem escolhida
(admissível!)

operadores = permutar dois nós quaisquer do caminho

restrição = somente caminhos conectados são estados válidos

estado final = nó onde valor de f é mínimo

e1 = {N1, N2, N3, N4, N5}
•

e2 = {N2, N1, N3, N4, N5}
•

f(N1, N2, N3, N4, N5) = 10
f(N2, N1, N3, N4, N5) = 14
e3 = {N2, N1, N4, N3, N5}
•
f(N2, N1, N3, N4, N5) = 9!!!
42
Subida da Encosta
Problemas


O algoritmo move-se sempre na direção que
apresenta maior taxa de variação para f
Isso pode levar a 3 problemas:
1. Máximos locais
2. Planícies (platôs)
3. Encostas e picos
43
Subida da Encosta
Máximos locais

Os máximos locais são picos mais baixos do que o pico mais
alto no espaço de estados
•máximo global - solução ótima

Nestes casos, a função de avaliação leva a um valor máximo
para o caminho sendo percorrido
•a função de avaliação é menor para todos os
filhos do estado atual, apesar de o objetivo
estar em um ponto mais alto
- essa função utiliza informação “local”
•e.g., xadrez:
- eliminar a Rainha do adversário pode levar o jogador a perder o jogo.
44
Subida da Encosta
Máximos locais

O algoritmo pára no máximo local
•só pode mover-se com taxa crescente de
variação de f
- restrição do algoritmo
•Exemplo de taxa de variação negativa
- Jogo dos 8 números:
- mover uma peça para fora da sua posição correta para dar passagem a outra
peça que está fora do lugar tem taxa de variação negativa!!!
45
Subida da Encosta
Platôs (Planícies)

Uma região do espaço de estados onde a função de
avaliação dá o mesmo resultado
• todos os movimentos são iguais (taxa de variação zero)
- f(n) = f(filhos(n))

O algoritmo pára depois de algumas tentativas
• Restrição do algoritmo

Exemplo: jogo 8-números
• em algumas situações, nenhum movimento possível vai
influenciar no valor de f, pois nenhum número vai chegar
ao seu objetivo.
46
Subida da Encosta
Encostas e Picos

Apesar de o algoritmo estar em uma direção que leva
ao pico (máximo global), não existem operadores
válidos que conduzam o algoritmo nessa direção
• Os movimentos possíveis têm taxa de variação zero ou
negativa
- restrição do problema e do algoritmo

Exemplo: cálculo de rotas
• quando é necessário permutar dois pontos e o caminho
resultante não está conectado.
47
Subida da Encosta
Problemas - solução


Nos casos apresentados, o algoritmo chega a um
ponto de onde não faz mais progresso
Solução: reinício aleatório (random restart)
• O algoritmo realiza uma série de buscas a partir de
estados iniciais gerados aleatoriamente
• Cada busca é executada
- até que um número máximo estipulado de iterações seja
atingido, ou
- até que os resultados encontrados não apresentem
melhora significativa
• O algoritmo escolhe o melhor resultado obtido com as
diferentes buscas.
- Objetivo!!!
48
Subida da Encosta: análise

O algoritmo é completo?
• SIM, para problemas de otimização
- uma vez que cada nó tratado pelo algoritmo é sempre um
estado completo (uma solução)
• NÃO, para problemas onde os nós não são estados completos
- e.g., jogo dos 8-números
- semelhante à busca em profundidade

O algoritmo é ótimo?
• TALVEZ, para problemas de otimização
- quando iterações suficientes forem permitidas...
• NÃO, para problemas onde os nós não são estados completos
49
Subida da Encosta: análise

O sucesso deste método depende muito do formato da
superfície do espaço de estados:
•se há poucos máximos locais, o reinício
aleatório encontra uma boa solução
rapidamente
•caso contrário, o custo de tempo é
exponencial.
50
Têmpera Simulada -Simulated
Annealing

Este algoritmo é semelhante à Subida da Encosta,
porém oferece meios para escapar de máximos locais
• quando a busca fica “presa” em um máximo local, o algoritmo
não reinicia a busca aleatoriamente
• ele retrocede para escapar desse máximo local
• esses retrocessos são chamados de passos indiretos

Apesar de aumentar o tempo de busca, essa estratégia
consegue escapar dos máximos locais
51
Têmpera Simulada

Analogia com cozimento de vidros ou metais:
• processo de resfriar um líquido gradualmente até ele se
solidificar

O algoritmo utiliza um mapeamento de resfriamento de
instantes de tempo (t) em temperaturas (T).
52
Têmpera Simulada

Nas iterações iniciais, não escolhe necessariamente o
“melhor” passo, e sim um movimento aleatório:
• se a situação melhorar, esse movimento será sempre escolhido
posteriormente;
• caso contrário, associa a esse movimento uma probabilidade
de escolha menor do que 1.

Essa probabilidade depende de dois parâmetros, e
decresce exponencialmente com a piora causada pelo
movimento,
• eDE/T, onde:
DE = Valor[próximo-nó] - Valor[nó-atual]
T = Temperatura
53
Têmpera Simulada: algoritmo
função Anelamento-Simulado (problema, mapeamento)
retorna uma solução
variáveis locais: atual, próximo, T (temperatura que controla a
probabilidade de passos para trás)
atual  Faz-Nó(Estado-Inicial[problema])
for t  1 to  do
T  mapeamento[t]
Se T = 0
então retorna atual
próximo  um sucessor de atual escolhido aleatoriamente
DE  Valor[próximo] - Valor[atual]
Se DE > 0
então atual  próximo
senão atual  próximo com probabilidade = e-DE/T
54
Têmpera Simulada

Para valores de T próximos de zero
•a expressão DE/T cresce
•a expressão e-DE/T tende a zero
•a probabilidade de aceitar um valor de próximo
menor que corrente tende a zero
•o algoritmo tende a aceitar apenas valores de
próximo maiores que corrente

Conclusão
•com o passar do tempo (diminuição da
temperatura), este algoritmo passa a funcionar
como Subida da Encosta
55
Têmpera Simulada

Implementação (dica)
• Gerar número aleatório entre (0,1) e comparar com o valor
da probabilidade
• Se número sorteado < probabilidade, aceitar movimento para
trás

Análise
• O algoritmo é completo
• O algoritmo é ótimo se o mapeamento de resfriamento tiver
muitas entradas com variações suaves
- isto é, se o mapeamento diminui T suficientemente
devagar no tempo, o algoritmo vai encontrar um máximo
global ótimo.
56
57
Heurística... por toda IA


A noção de heurística sempre foi além da busca e de uma
formalização via função de um estado
Heurística
• escolha, prioridade, estratégia na busca de uma solução
razoável onde não há solução ótima ou recurso para
determiná-la
• No dia a dia: heurística para dirigir, namorar, estudar,...

Em IA: em todas as áreas como conhecimento de controle
• ex. escolha de regras a serem disparadas (SBC)
• ex. escolha de viés de generalização (aprendizagem)
• ...
Referências


T. Mitchell. Machine Learning. McGraw Hill, New York,
1997.
Stuart Russell and Peter Norvig, Artificial Intelligence
- A Modern Approach. Prentice Hall, 1995.
58