Upload
others
View
5
Download
0
Embed Size (px)
Citation preview
1
© Noel de Jesus Mendonça Lopes 1
Pesquisa informada
o Dispomos de informação especifica sobre o problema.
o Esta informação pode ser disponibilizada por uma função de avaliação que indica o quão desejável é expandir um determinado nó.
© Noel de Jesus Mendonça Lopes 2
Best-first search
o Se os nós estiverem ordenados por forma a que aquele que tiver a melhor avaliação é expandido primeiro, estamos perante a estratégia best-first search.
o Algoritmo :Function BestFirstSearch(problema, FuncaoAvaliacao)
returns solução ou falhaFuncaoAdicaoFila ← Função que ordena os nós da fila de acordo com FuncaoAvaliacaoreturn PesquisaGeral(problema, FuncaoAdicaoFila)
© Noel de Jesus Mendonça Lopes 3
Best-first search
o A qualidade desta estratégia de pesquisa depende da qualidade da função de avaliação.
o Os algoritmos pertencentes a esta família tentam encontrar soluções de baixo custo. Tipicamente utilizam estimativas do custo do estado actual até à solução mais próxima e tentam minimizar o seu valor.
© Noel de Jesus Mendonça Lopes 4
Best-first search – Pesquisa gananciosa (greedy)
o Os nós cujo estado se julga estar mais próximo do objectivo são expandidos primeiro.
o Uma função que calcula uma estimativa do custo é chamada por função heurística e é usualmente designada por h.h(n) = Custo estimado do caminho mais
barato desde o estado correspondente ao nó n até a um estado objectivo
2
© Noel de Jesus Mendonça Lopes 5
Pesquisa gananciosa
o h(n) deve ser zero quando o nó n tenha associado um estado correspondente ao objectivo.
o Algoritmo :Function GreedySearch(problema, FuncaoAvaliacao) returns
solução ou falhareturn BestFirstSearch(problema, h)
o Tenta atingir o objectivo o mais depressa possível.
o Encontra soluções rapidamente.
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Sibiu
RimnicuVilcea
Fagaras
Criova
PitestiBucharest
Giurgiu
Urziceni
Hirsova
Eforie
Vaslui
Iasi
Neamt71
75
118
11170
75
120
146
80
140
151
99
211
97
138
101
90
8598
86
142
92
87Arad
BucharestCraiovaDobretaEforie
FagarasGiurgiuHirsova
LasiLugoj
MehaidaNeamtOradeaitesti
Rimnicu VilceaSibiu
TimisoaraUrziceniVasluiZerind
3660
160242161178771512262442412343809819325332980199374
Distância em linharecta até Bucharest
h(n) = distância em linha recta entre n e a localização do objectivo
© Noel de Jesus Mendonça Lopes 7
Pesquisa gananciosao Susceptível a falsas partidasn Ex : Ir de Lasi para Fagarasn Necessário evitar estados repetidosn São expandidos nós desnecessários
o Não é óptimo nem completo, à semelhança do deep-first search.
o Complexidade : O(bm). No entanto a complexidade pode ser reduzida substancialmente dependendo da qualidade de h.
© Noel de Jesus Mendonça Lopes 8
A*
f(n) = g(n) + h(n)
f(n) = custo estimado da solução mais “barata” que passa por n
Function A*(problema) returns solução ou falhareturn BestFirstSearch(problema, g + h)
3
© Noel de Jesus Mendonça Lopes 9
A*
o Óptimo e completo se :n h(n) nunca sobrestimar o custo de
alcançar o objectivo. Uma função h que obedeça a este critério é designada por heurística admissível.
© Noel de Jesus Mendonça Lopes 10
Heurísticas admissíveis
o São por natureza optimistas.o Em quase todas as heurísticas
admissíveis o custo de f nunca decresce ao longo de qualquer caminho a partir da raiz da árvore de pesquisa. Estas heurísticas têm um comportamento monótono.
© Noel de Jesus Mendonça Lopes 11
Heurísticas admissíveis
o Quando a heurística não é monótona podemos fazer uma pequena correcção em f que a torne monótona. Supondo que o nó n é o pai de n’, podemos transformar f numa função monótona da seguinte forma :
f(n’) = max( f(n), g(n’) + h(n’) )o Esta equação designa-se por
equação do caminho máximo.
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Sibiu
RimnicuVilcea
Fagaras
Criova
Pitesti
Bucharest
Giurgiu
Urziceni
Hirsova
Eforie
Vaslui
Iasi
Neamt
380
400
420
4
© Noel de Jesus Mendonça Lopes 13
Contornos
o Se h for 0 (uniform-cost search), os limites dos contornos serão circulares, à volta do estado inicial.
o Quanto melhor for a heurística mais os limites dos contornos se esticarão em direcção do objectivo.
© Noel de Jesus Mendonça Lopes 14
A*
o É eficientemente óptimo para qualquer função heurística.n Não existe nenhum outro algoritmo
óptimo que expanda menos nós que o A*
o É completo desde que o custo de todas as operações seja positivo (maior que zero).
© Noel de Jesus Mendonça Lopes 15
Funções heurísticas
5 4
6 1
7 3
8
2 5
4
6
1
7
3
8
2 5 4
6 1
7 3
8
2
© Noel de Jesus Mendonça Lopes 16
Funções heurísticas
o Factor de ramificação ≈ 3o Solução ≈ 20 passoso Pesquisa exaustiva : 320 = 35 x 108
estadoso Evitando os estados repetidos : 9! =
362880
5
© Noel de Jesus Mendonça Lopes 17
Funções heurísticas
o Determinar uma função heurística que nunca sobrestime o número de passos necessários para atingir o objectivo?
© Noel de Jesus Mendonça Lopes 18
Funções heurísticas
o h1 = nº de peças fora da posição correcta.
o h2 = soma das distâncias de cada uma das peças até à sua posição correcta (segundo a distância de manhattan).
© Noel de Jesus Mendonça Lopes 19
Factor de ramificação efectivo (b*)
N = 1 + b* + (b*)2 + ... + (b*)d
Uma boa heurística terá um b*perto de 1
© Noel de Jesus Mendonça Lopes 20
Factor de ramificação efectivo
1.301.342.7318206806
1.241.332.80253963848
1.48
1.79
A*(h1)
Factor de ramificação efectivo
Custo da pesquisa
2.87
2.45
IDS
1.4512131124
1.7966102
A*(h2)A*(h2)A*(h1)IDSd
IDS – Iterative deepening search.
Dados obtidos em 100 instâncias de um puzzle com 8 peças.
6
© Noel de Jesus Mendonça Lopes 21
Factor de ramificação efectivo
1.261.46363305618
1.271.47676727620
1.281.4812191809422
1.241.422.787322736440412
1.231.442.83113539347394114
1.251.45211130116
1.221.382.7939934712710
1.48
A*(h1)
Factor de ramificação efectivo
Custo da pesquisa
IDS
1.2616413913524
A*(h2)A*(h2)A*(h1)IDSd
© Noel de Jesus Mendonça Lopes 22
Heurísticas
o h2 domina h1, se quando utilizamos h2expandimos em média menos nós que quando utilizamos h1.
o Entre duas heurísticas é sempre preferível aquela com maiores valores, desde que não sobrestime o custo de atingir o objectivo.
© Noel de Jesus Mendonça Lopes 23
Problemas relaxados
o Um problema com menos restrições nos operadores diz-se relaxado.
o Muitas vezes o custo de uma solução exacta para um problema relaxado é uma boa heurística para o problema original.
© Noel de Jesus Mendonça Lopes 24
Problemas relaxados
o Uma peça pode mover-se de A para B se A é adjacente a B e B está vazio.
o Uma peça pode mover-se de A para B se A é adjacente a B.
o Uma peça pode mover-se de A para B se B está vazio.
o Uma peça pode mover-se de A para B.
5 4
6 1
7 3
8
2
7
© Noel de Jesus Mendonça Lopes 25
Problemas relaxadoso Em (1993) um programa chamado
ABSOLVER cujo objectivo é gerar heurísticas de forma automática a partir da definição de um problema, encontrou a primeira heurística útil para o cubo de Rubik e gerou uma nova heurística para o puzzle com 8 peças, que resultou ser melhor que qualquer das heurísticas existentes.
o O ABSOLVER utiliza o método do “problema relaxado” em conjunto com outras técnicas.
© Noel de Jesus Mendonça Lopes 26
Escolha das heurísticaso Se dispusermos de várias heurísticas
admissíveis h1, h2, ..., hm e nenhuma dominar as restantes qual escolher ?
h(n) = max(h1(n), h2(n), ..., hm(n))
o Desta forma é utilizada a heurística mais precisa para o nó em questão.
o Como todas as heurísticas que compõem h são admissíveis h é também admissível.
o Obviamente h domina todas as heurísticas que a compõem.
© Noel de Jesus Mendonça Lopes 27
Escolha das heurísticas
o Uma boa função heurística para além de ser precisa deve ser ainda eficiente.
o Estatístican Perdemos a garantia de admissibilidade
mas em média expandimos menos nósn Ex : Quando h(n) = 14 em 90% dos
casos são necessários 18 passos.
© Noel de Jesus Mendonça Lopes 28
Escolha das heurísticas
o Recolha das características do estado que contribuem para a avaliação heurística.
o Usualmente a função de avaliação é uma combinação linear dos valores das características.
o Mas qual a contribuição de cada característica ?
8
© Noel de Jesus Mendonça Lopes 29
Contribuição das características para a função de avaliação
o Mesmo quando não se sabe o quão importante é uma característica, ou se é benéfica ou má é possível a um algoritmo de aprendizagem adquirir coeficientes razoáveis para cada característica.
© Noel de Jesus Mendonça Lopes 30
Heurísticas para problemas de satisfação de restrições (CSP)
o Heurística da variável mais restringidan Usada em conjunto com o forward
checking;n Escolhemos a variável que dispõe de
menos valores;n O factor de ramificação tende a ser
menor.
© Noel de Jesus Mendonça Lopes 31
Heurísticas para problemas de satisfação de restrições (CSP)
o Heurística da variável mais restritivan Escolhe a variável que aparece no maior número
de restrições que contêm variáveis sem valor;n O factor de ramificação tende a ser menor.
o Heurística do valor menos restritivon Escolhe o valor que retira o menor número de
valores das variáveis que partilham restrições com a variável actual.
© Noel de Jesus Mendonça Lopes 32
Iterative deepening A* (IDA*)
o Cada iteração é feita com um algoritmo similar ao deep-limited search, mas em vez de se parar a pesquisa quando uma determinada profundidade é alcançada esta para quando o custo de f(n) for superior a um determinado valor.
o Em cada iteração são expandidos os nós dentro do contorno para o custo de f actual e determina-se qual será o próximo contorno.
9
© Noel de Jesus Mendonça Lopes 33
Iterative deepening A* (IDA*)function IDA(p) returns solução ou falha
inputs : p, problemalocal variables : limitef, o limite do custo de f (contorno)
raiz, um nó
raiz ← CriaNo(EstadoInicial(p))limitef ← Custo(raiz)
dosolução, limitef ← Contorno(p, raiz, limitef)if solução is null then
if limitef = ∞ then return falhaelse
return soluçãoend
loop
© Noel de Jesus Mendonça Lopes 34
Iterative deepening A* (IDA*)function Contorno(p, no, limitef) returns solução e um novo limite do custo de f
inputs : p, problemano, um nólimitef, o limite actual do custo de f (contorno)
local variables : proximof, o próximo limite do custo de f (contorno), inicialmente ∞
if Custo(no) > limitef then return null, Custo(no)if Objectivo(p, Estado(no)) then return no, limiteffor each nó s in Sucessores(no) do
solução, novof ← Contorno(p, s, limitef)if solução is null then
if novof < proximof then proximof ← novofelse
return solução, limitefend
nextreturn null, proximof
© Noel de Jesus Mendonça Lopes 35
Iterative deepening A* (IDA*)o Completo e óptimo, tendo em atenção as
mesmas salvaguardas que o A*.o Necessita de muito menos memória que o
A*.o A complexidade (tempo) depende do
número de valores diferentes que a heurística pode devolvern Ex: No puzzle com 8 peças f cresce apenas uma
ou duas vezes, já no problema do caixeiro viajante o valor de f é em principio diferente para cada nó, o que significa que cada contorno pode incluir apenas mais um nó.
© Noel de Jesus Mendonça Lopes 36
Algoritmo ε-admissível
o Em cada iteração aumentamos o valor do contorno por ε.n Reduzimos assim o custo da pesquisa, já
que em cada iteração são englobados mais nós (dependendo de ε).
n A solução retornada pode ser pior do que a óptima, no máximo por ε.
10
© Noel de Jesus Mendonça Lopes 37
Simplified Memory-Bounded A* (SMA*)
o Utiliza toda a memória que lhe for disponibilizada.
o Evita estados repetidos sempre que a memória o permita.
o É completo desde que a memória disponível seja suficiente para guardar o caminho para a solução com o menor profundidade.
© Noel de Jesus Mendonça Lopes 38
Simplified Memory-Bounded A*
o É óptimo desde que a memória disponível seja suficiente para guardar o caminho para a solução com o menor custo. Caso contrário retorna a melhor solução que se pode atingir com a memória disponível.
o Quando existe memória suficiente para guardar a árvore de pesquisa completa o algoritmo é eficientemente óptimo.
© Noel de Jesus Mendonça Lopes 39
Simplified Memory-Bounded A*
o Antes de gerar um sucessor o algoritmo verifica se existe memória suficiente para o guardar. Caso não exista memória suficiente o algoritmo retira um dos nós da fila para poder gerar o sucessor.
o Os nós retirados da fila são aqueles menos promissores, isto é aqueles com maior custo de f e são chamados nós esquecidos.
© Noel de Jesus Mendonça Lopes 40
Simplified Memory-BoundedA*o De forma a evitar re -explorar sub-árvores
retiradas da memória em cada nó antecessor é guardada informação do melhor caminho na sub-árvore esquecida. Desta forma o algoritmo só regenera uma sub-árvore, quando todos os outros caminhos parecerem piores que o caminho esquecido.
o Desta forma se todos os descendentes do nó n forem esquecidos, não saberemos por onde devemos ir a partir do nó n mas sabemos se vale a pena ir pelo nó n.
11
© Noel de Jesus Mendonça Lopes 41
Simplified Memory-Bounded A*function SMA(p) returns solução ou falha
/*dada a complexidade do algoritmo muitos pormenores foram omitidos */inputs : p, problemalocal variables : fila, uma fila de nós ordenada primeiro pelo custo f dos nós e depois por ordem decrescente pela profundidade dos nós
fila ← CriaFila(CriaNo(EstadoInicial(p))
doif Vazia(fila) then return falhan ← primeiro nó da filaif Objectivo(p, Estado(n)) then return nif not TemMaisSucessores(n) then
Actualiza o custo f do nó n e dos seus antecessoreselse
s ← ProximoSucessor(n)f(s) ← CustoF(p, s)if Cheia(fila) then RetiraUltimoNo (fila)Insere(fila, s)
endloop
© Noel de Jesus Mendonça Lopes 42
Simplified Memory-Bounded A*function CustoF(p, n) returns custo de f para o nó n
inputs : p, probleman, nó
static : maiorProfundidade, O maior número de nós que conseguimos ter em memória.
if not Objectivo(p, Estado(n)) and Profundidade(n) = maiorProfundidade then return ∞
if Pai(n) is null then return g(n) + h(n)
return Max(f(Pai(n)), g(n) + h(n))
A
B
C D
E F
G
H I
J K
10 8
1010
1010
8 16
8 8
0+12=12
8+5=13
24+0=24
24+5=29
16+2=18
24+0=24
20+0=20
10+5=15
20+5=25
30+0=3030+5=35
© Noel de Jesus Mendonça Lopes 44
Hill-climbing
12
© Noel de Jesus Mendonça Lopes 45
Hill-Climbingfunction HillClimbing(p) returns solução
inputs : p, problemalocal variables : actual, um nó
proximo, um nó
actual ← CriaNo(EstadoInicial(p))
doproximo ← O sucessor de actual com maior valorif valor(proximo) < valor(actual) then return actualactual ← proximo
loop