...

Estratégias de Busca

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Estratégias de Busca
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Estratégias de Busca
February 21, 2013
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Introdução
ˆ estratégia de busca
ˆ árvore de busca
ˆ nó de busca (estado inicial: raiz da árvore)
ˆ expansão de nós da árvore
ˆ estruturas de dados para as árvores de busca
ˆ cada nó é uma estrutura com pelo menos 5
componentes/campos:
◮
◮
◮
◮
◮
estado
nó pai
jogada/regra aplicada para gerar o nó
número de nós no caminho para este nó (profundidade do
nó na árvore)
custo do caminho desde o nó raiz
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Estruturas
ˆ datatype node components:
STATE, PARENT NODE,
OPERATOR, DEPTH, PATH COST
ˆ Necessária representação para lista de nós que ainda não
foram expandidos
ˆ Escolha: fila de nós com as seguintes operações:
◮ MAKE QUEUE(Elementos)
◮ EMPTY?(Queue)
◮ REMOVE FRONT(Queue) (função)
◮ QUEUEING FN(Elementos,Queue)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Algoritmo Geral
function GENERAL_SEARCH(problem, QUEUEING_FN) retorna
solucao ou falha
nodes := MAKE_QUEUE(MAKE_NODE(INITIAL_STATE(problem)))
loop
if EMPTY?(nodes) then return falha
node := REMOVE_FRONT(nodes)
if STATE(node) = GOAL_TEST[problem] then return
node
new_nodes := EXPAND(node,OPERATORS(problem))
nodes := QUEUEING_FN(nodes,new_nodes)
end
Obs: QUEUEING FN é uma função variável!
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca de Soluções: Estratégias
ˆ Avaliação:
◮ completude
◮ complexidade temporal
◮ complexidade espacial
◮ otimalidade
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Métodos não informados de busca (busca cega)
ˆ largura (BL)
ˆ custo uniforme (BCU)
ˆ profundidade (BP)
ˆ limitada em profundidade (BLP)
ˆ profundidade iterativa (BPI)
ˆ bidirecional (BB)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Largura (BL)
ˆ todos os nós e nı́vel d na árvore de busca são expandidos
antes dos nós de nı́vel d+1
ˆ função QUEUEING FN: fifo
function BREADTH_FIRST_SEARCH(problem) retorna
solucao ou falha
return GENERAL_SEARCH(problem,ENQUEUE_AT_END)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Largura (BL)
A
A
B
D
C
E
F
A
B
G
D
C
E
F
A
B
G
D
C
E
F
B
G
D
C
E
F
G
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Largura: análise
ˆ completude: se houver solução, BL garante que vai ser
encontrada → completa
ˆ se houver + de 1 solução garante quee encontra a mais rasa
primeiro → é ótima se o custo do caminho for uma função
não decrescente da profundidade do nó
ˆ espaço/memória = número máximo de nós para computar
1 solução de profundidade d (fator de ramificação b)
1 + b + b × b + (b × b) × b + ... + bd
ˆ complexidades de espaço e tempo iguais: O(bd ), todas as
folhas da árvore têm que ser armazenadas ao mesmo tempo
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Largura: análise
Profundidade
Nós
Tempo
Memória
0
1
1 ms 100 Bytes
2
111
1s
11 KB
4 11.111
11s
1MB
6
106
18 min
111 MB
8
108
31 h
11 GB
10
10
10
128 dias
1TB
12
1012
35 anos
111TB
14
1014 3500 anos 11.111TB
Obs: 1000 nós podem ser testados e expandidos por segundo, 1
nó precisa de 100 Bytes, b = 10
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Largura: análise
ˆ qtde de memória: maior problema de BL
ˆ se o problema tiver uma solução em nı́vel 12, então levaria
35 anos para computar a resposta!!!
ˆ em geral, problemas de busca com complexidade de tempo
exponencial não podem ser resolvidos para instâncias
muito grandes de entrada
ˆ problema de todos os métodos de busca não informados
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca de Custo Uniforme (BCU)
ˆ modificação da estratégia de BL para expandir apenas nós
de baixo custo (utiliza função de custo g(n))
ˆ BL é de custo uniforme com g(n) = DEPTH(n)
ˆ função QUEUEING FN: ordem crescente de custos
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca de Custo Uniforme: Análise
ˆ BCU encontra a solução de menor custo se o custo do
caminho nunca decrescer para os descendentes:
g(SU CCESSOR(n)) ≥ g(n)
ˆ Complexidades temporal e espacial iguais às de BL.
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Profundidade
ˆ expande nós mais profundos da árvore primeiro
ˆ função QUEUEING FN: lifo (pilha)
function DEPTH_FIRST_SEARCH(problem) retorna
solucao ou falha
return GENERAL_SEARCH(problem,ENQUEUE_AT_BEGINNING)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Profundidade
A
A
B
C
D
H
E
I
J
B
F
K
L
G
N
M
C
D
O
H
E
I
J
K
E
I
J
L
G
N
M
D
O
O
H
E
I
J
F
K
J
O
C
F
L
K
N
M
L
A
E
I
G
E
G
N
M
O
J
F
K
L
G
N
M
O
A
C
E
B
F
L
K
C
D
C
A
J
N
M
L
B
F
K
G
A
C
D
B
F
A
B
H
A
G
N
M
C
E
O
A
C
F
L
K
G
N
M
F
O
A
C
G
M
N
O
C
F
O
N
M
A
C
F
L
L
G
L
G
M
N
F
O
G
M
N
O
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Profundidade: Análise
ˆ espaço: somente os nós do caminho da solução + nós ainda
não expandidos
ˆ total: b × m, onde b = fator de ramificação e m =
profundidade máxima
ˆ BF precisaria de apenas 12KB invés de 111TB para
encontrar a solução em nı́vel 12.
ˆ tempo: O(bm )
ˆ para problemas qur têm muitas soluções, BF pode ser +
rápida que BL por ter boa chance de encontrar uma
solução depois de explorar um espaço pequeno do espaço
de busca total
ˆ estratégia não é completa nem ótima!!
ˆ BP não deve ser usada para árvores de muita ou
profundidade infinita!!
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca Limitada em Profundidade
ˆ Impõe um corte na profundidade máxima de um caminho
ˆ necessário verificar profundidade de cada nó expandido
ˆ função EXPAND responsável por verificar se profundidade
limite foi atingida
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca Limitada em Profundidade: Análise
ˆ estratégia é completa, mas....
ˆ ...não é ótima!
ˆ se limite de profundidade muito pequeno, não garantimos
completude
ˆ tempo: O(bl ), com l, limite de prof.
ˆ espaço: O(b × l)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Profundidade Iterativa
ˆ tenta todos os possı́veis limites de profundidade
ˆ combina vantagens de BL com BF
function ITERATIVE_DEEPENING_SEARCH(problem) retorna
solucao ou falha
for depth := 0 to infinito do
if DEPTH_LIMITED_SEARCH(problem,depth) then
return solucao
end
return falha
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca em Profundidade Iterativa: Análise
ˆ é ótima e completa
ˆ espaço: como busca em profundidade
ˆ ordem de expansão dos nós análogo à BL, com exceção de
que alguns estados são expandidos várias vezes
ˆ tempo:
(d+1)×1+(d)×b+(d−1)×b2 +...+3×bd−2 +2×bd−1 +1×bd
ˆ nós da folha da última iteração são expandidos uma única
vez
ˆ próximo nı́vel: duas vezes etc
ˆ raiz expandida d+1 vezes
ˆ complexidade temporal: O(bd )
ˆ método utilizado qdo a árvore de busca é muito grande e
prof da solução não conhecida
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca Bidirecional (BB)
ˆ Busca por dois lados: do estado inicial para o final e do
final para o inicial
ˆ BB termina quando as duas buscas se encontram
ˆ para problemas com fator de ramificação b, BB pode fazer
gde diferença em termos de tempo de execução/espaço
consumido
ˆ b=10, d=6:
◮
◮
BL: 1.111.111 nós
d
d
BB: 2.222 nós (2 × b 2 → O(b 2 ))
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca Bidirecional (BB): Algoritmo
function BIDIRECIONAL_SEARCH(problem, QUEUEING_FN1, QUEUEING_FN2
retorna solucao ou falha
nodes1 := MAKE_QUEUE(MAKE_NODE(INITIAL_STATE(problem)))
nodes2 := MAKE_QUEUE(MAKE_NODE(FINAL_STATE(problem)))
loop
if EMPTY?(nodes1) || EMPTY?(nodes2) then return falha
node1 := REMOVE_FRONT(nodes1)
node2 := REMOVE_FRONT(nodes2)
if node1 in nodes2 || node1 = node2 then return solucao
if node2 in nodes1 || node1 = node2 then return solucao
new_nodes1 := EXPAND(node1,OPERATORS(problem))
nodes1 := QUEUEING_FN1(nodes1,new_nodes1)
new_nodes2 := EXPAND(node2,OPERATORS(problem))
nodes2 := QUEUEING_FN2(nodes2,new_nodes1)
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Busca Bidirecional (BB): Algoritmo
Busca Bidirecional (BB)
ˆ Na prática:
◮ precisamos de formas eficientes para descobrir se um novo
nó já apareceu na árvore de busca da outra busca
◮ decidir o tipo de busca a ser utilizada em cada metade do
espaço de busca
◮ seleção de sucessores e predecessores
Busca de Soluções Busca de Soluções Busca de Soluções Busca Busca Busca Busca Busca Busca B
Comparação entre buscas
Critério
tempo
espaço
otimalidade
completude
BL
bd
bd
sim
sim
BCU
bd
bd
sim
sim
BP
bm
b×m
não
não
BLP
bl
b×l
não
sim, se l ≥ d
BPI
bd
b×d
sim
sim
BB
d
b2
d
b2
sim
sim
Fly UP