Agenda
Análise e Técnicas de Algoritmos
Jorge Figueiredo
••
••
••
••
Conceitos
Conceitos Básicos
Básicos
O
O Problema
Problema das
das Rainhas
Rainhas
Template
TemplateGenérico
Genérico
Mochila
Mochila Binária
Binária
Backtracking
Backtracking and
and Branch-and-Bound
Branch-and-Bound
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Jogo da Troca de Bolas
Jogo da Troca de Bolas
•• nn bolas
bolas vermelhas
vermelhas ee nn bolas
bolas pretas
pretas
•• Tabuleiro
Tabuleiro (uma
(uma linha)
linha) com
com 2n
2n ++ 11 posições
posições
•• Bolas
Bolas com
com aamesma
mesma cor
cor em
em extremidades
extremidades diferentes,
diferentes,ee um
um
espaço
espaço vazio
vazio separando
separando oo conjunto
conjunto de
de bolas
bolas diferentes.
diferentes.
•• Movimentos
Movimentos possíveis:
possíveis:
–– Bola
Bola vermelha
vermelha para
para aa esquerda
esquerda ee preta
preta para
para aa direita
direita
–– Mover
Mover um
um espaço
espaço se
se oo espaço
espaço está
estávazio
vazio
–– Pular
Pular sobre
sobre exatamente
exatamente uma
uma bola
bola de
de cor
cor diferente,
diferente, se
seoo
espaço
espaço logo
logo após
após aa bola
bola estiver
estiver vazio
vazio
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Problema do Labirinto
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Problema do Labirinto
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
1
Jogo do “Resta Um”
O Que Estes Problemas Têm em Comum?
•• Tomar
Tomar uma
uma série
série de
de decisões
decisões entre
entre várias
várias opções.
opções.
•• Cada
Cada decisão
decisão leva
leva aa um
um novo
novo conjunto
conjunto de
de decisões.
decisões.
•• Alguma(s)
Alguma(s) seqüência(s)
seqüência(s) de
de decisões
decisões pode(m)
pode(m) conduzir
conduzir aa
solução
solução do
do problema.
problema.
•• Encontrar
Encontrar solução:
solução:
1.
1. Fazer
Fazer uma
uma lista
listacom
com todos
todos os
os candidatos
candidatos possíveis.
possíveis.
2.
2. Examinar
Examinar todas
todas as
as respostas
respostas ou
ou alguma
alguma delas.
delas.
3.
3. Retornar
Retornar aa solução.
solução.
•• Problemas
Problemas de
de otimização
otimização
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Como Resolver?
Backtracking
•• Estratégia
Estratégia para
para sistematicamente
sistematicamente aa lista
lista de
de possíveis
possíveis
soluções,
soluções, eliminando
eliminando (explicitamente)
(explicitamente) aa verificação
verificação de
de uma
uma
boa
boa parte
parte dos
dos possíveis
possíveis candidatos.
candidatos.
•• Pode
Pode ser
ser considerado
considerado como
como uma
uma variação
variação de
de DFS.
DFS.
•• Usa
Usa uma
uma árvore
árvore implícita.
implícita.
Candidatos
Força
Força bruta:
bruta: na
na prática
prática esta
estaabordagem
abordagem não
não éé muito
muito eficiente
eficiente
porque
porque aa lista
lista de
de candidatos
candidatos éé grande.
grande.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Lixo
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Idéia Geral: Usando o Espaço de Solução
•• Soluções
Soluções representadas
representadas por
por n-tuplas
n-tuplas ou
ou vetores
vetores de
de solução:
solução:
–– <v
<v11,, vv22,, ...,
..., vvnn>>
–– Cada
Cada vvi i éé escolhido
escolhido aa partir
partir de
de um
um conjunto
conjunto finito
finito de
de opções
opções
SSi.i.
•• Inicia
Inicia com
com um
um vetor
vetor vazio.
vazio.
•• Em
Emcada
cada etapa
etapa oo vetor
vetor éé extendido
extendido com
com um
um novo
novo valor.
valor.
•• O
O novo
novo vetor
vetor éé então
então avaliado.
avaliado. Se
Se não
não for
for solução
solução parcial,
parcial, oo
último
último valor
valor do
do vetor
vetor éé eliminado
eliminado ee outro
outro candidato
candidato éé
considerado.
considerado.
Restrições
Restrições
•• Restrições
Restrições Explícitas:
Explícitas: correspondem
correspondem às
às regras
regras que
que
restringem
restringem cada
cada vvi i em
em tomar
tomar valores
valores de
de um
um determinado
determinado
conjunto.
conjunto. Está
Estárelacionado
relacionado com
com aa representação
representação do
do problema
problema
ee as
as escolhas
escolhas possíveis.
possíveis.
•• Restrições
se relacionam
Restrições Implícitas:
Implícitas: determinam
determinam como
como os
os vvi’s
i’s se relacionam
entre
entre si.
si.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
2
O Problema das 8 Rainhas
Soma de Subconjuntos
•• Colocar
Colocar 88 rainhas
rainhas em
em um
um tabuleiro
tabuleiro de
de xadrez
xadrez de
de modo
modo que
que
nenhuma
nenhuma rainha
rainha ataque
ataque uma
uma outra.
outra.
•• Solução:
Solução: uma
uma 8-tupla
8-tupla <v
<v11,, vv22,, …,
…, vv88>>em
em que
que vvi i indica
indica aa coluna
coluna
da
darainha
rainhai.i.
•• Restrições
Restrições Explícitas:
Explícitas: SSi i=={1,
{1, 2,
2,3,
3,…,
…, 8},
8},11≤≤ ii≤≤ n.
n.
•• Restrições
Restrições implícitas:
implícitas:
–– Nenhum
pode ser
ser igual
igual ao
ao outro.
outro.
Nenhum vvi i pode
–– Duas
Duas rainhas
rainhas não
não podem
podem estar
estar na
na mesma
mesma diagonal.
diagonal.
•• Tamanho
Tamanho do
do espaço
espaço solução:
solução:
–– Força
Força Bruta:
Bruta: 4.426.165.368
4.426.165.368
8
–– Com
Com R.E.:
R.E.:888..
–– Com
Com R.I.:
R.I.: 8!.
8!.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Geração da Árvore
•• Sejam
Sejam nn números
númerospositivos
positivos (W
(Wi,i, 11≤≤ ii≤≤ n)
n) ee um
um valor
valor positivo
positivo
M,
M, achar
achar todos
todos os
ossubconjuntos
subconjuntos de
de W
Wi icuja
cujasoma
soma éé M.
M.
•• Solução:
Solução: uma
uma k-tupla
k-tupla com
com os
osíndices
índices dos
dos números
números escolhidos.
escolhidos.
•• Restrições
Restrições Explícitas:
Explícitas: vvi i == {j{j || jj éé inteiro,
inteiro, 11 ≤≤ jj ≤≤n}.
n}.
•• Restrições
Restrições Implícitas:
Implícitas:
–– vvi i ≠≠ vvj,j, ii≠≠ j.j.
–– ΣΣ ==M.
M.
–– vvi i << vvi+1
, 1 ≤ i < n.
i+1, 1 ≤ i < n.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Exemplo: Problema das 4 rainhas
Para
Para criar
criar aa árvore
árvore que
que representa
representa oo espaço
espaço solução
solução fazemos:
fazemos:
1.
1. Começar
Começar da
da raiz
raiz ee gerar
gerar outros
outros nós.
nós.
2.
2. Um
Um nó
nó que
que foi
foi gerado
gerado ee que
que não
não foi
foi totalmente
totalmente explorado
explorado
éé dito
dito nó
nó vivo.
vivo.
3.
3. Um
Um nó
nó cujos
cujos filhos
filhosestão
estão sendo
sendo gerados
gerados éé dito
dito em
em
expansão.
expansão.
4.
4. Usar
Usar função
função de
de poda
poda para
para detonar
detonar aa geração
geração de
de alguns
alguns
filhos,
filhos,se
se for
for oocaso.
caso.
5.
5. Um
Um nó
nó morto
morto éé aquele
aquele que
que foi
foi podado
podado ou
ou todos
todos os
os filhos
filhos já
já
foram
foram gerados.
gerados.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Algoritmo Genérico
Mochila Binária
Backtrack(v[1..k])
► v é um vetor promissor de tamanho k
if v é solução then
escreva v
for cada vetor promissor w de tamanho k+1
em que w[1..k] = v[1..k] do
Backtrack(w[1..k+1])
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
•• Considerar
Considerar nn tipos
tipos de
de objetos
objetos (um
(um número
número adequado
adequado de
de cada
cada
objeto)
objeto)
•• Cada
Cada objeto
objeto ii tem:
tem:valor
valor(v
(vi)i) ee peso
peso (w
(wi)i)
•• Mochila
Mochila com
com capacidade
capacidade W
W
•• Para
Para concretizar:
concretizar:
–– W
W ==88
–– oo11:: (w=2,
(w=2, v=3)
v=3)
–– oo22:: (3,
(3, 5)
5)
–– oo33:: (4,
(4, 6)
6)
–– oo44:: (5,
(5, 10)
10)
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
3
Mochila Binária: Algoritmo
Mochila Binária (Variação)
Backpack(i, r)
► maior lucro usando objetos de tipos i até n e que não
exceda r
b←0
for k ← i to n do
if w[k] ≤ r then
b ← max(b, v[k]+ Backpack(k, r – w[k]))
return b
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
•• Um
Um objeto
objeto de
de cada
cada tipo.
tipo.
•• Usar
Usar uma
uma função
função extra
extra que
que limita
limita poda:
poda:
–– Usar
Usar aa estratégia
estratégia gulosa
gulosa para
para mochila
mochila fracionária
fracionária para
para
computar
computar um
um limite
limite superior
superior de
de lucro.
lucro.
–– Ordenar
Ordenar os
os objetos
objetos por
por valor/peso.
valor/peso.
•• Duas
Duas possibilidades
possibilidades de
de backtracking:
backtracking:
–– Limite
Limite de
de peso.
peso.
–– Se
Se não
não existe
existe possibilidade
possibilidade da
da melhor
melhor estimativa
estimativa de
de lucro
lucro
ser
ser maior
maior do
do que
que oo melhor
melhor lucro
lucro já
já encontrado.
encontrado.
Mochila Binária (Variação)
••
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Mochila Binária (Variação)
Considere
Considere W=
W=16
16 ee os
osseguintes
seguintes 44 objetos:
objetos:
ii
11
22
33
44
vvi i
R$45
R$45
R$30
R$30
R$45
R$45
R$10
R$10
w
wi i
33
55
99
55
Valor = R$0
Peso = 0
E.L = R$ 115
vvi/w
i/wi i
R$15
R$15
R$
R$ 66
R$
R$ 55
R$
R$ 22
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Valor = R$45
Peso = 3
E.L = R$ 115
Branch-and-Bound
R$0
0
R$ 115
R$0
0
R$ 79
R$75
8
R$ 115
R$120
17
max
R$75
8
R$ 85
R$90
12
R$ 96
••
••
••
Variação
Variação de
de backtracking.
backtracking.
Necessidade
Necessidade de
de função
função de
de poda.
poda.
Em
Em alguns
alguns problemas,
problemas, poda
poda pode
pode ser
ser realizada
realizada mais
mais cedo
cedo se
se
usarmos
usarmos BFS
BFS em
emvez
vez de
de DFS.
DFS.
•• BnB
BnB == Backtracking
Backtracking ++ Função
Função de
de poda
poda –– DFS
DFS ++ BFS
BFS++PQ
PQ
R$45
R$0
3 0
R$R$
55115
X
Análise e Técnicas de Algoritmos – 2005.1
X
R$45
3
R$ 96
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Mochila Binária (Variação)
R$45
3
R$ 115
Valor = R$0
Peso = 0
E.L = R$ 79
X
R$85
13
R$ 85
R$75
8
R$ 75
X
X
R$100
17
X
R$90
12
R$ 90
X
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
4
Mochila Binária (Variação)
••
Mochila Binária (BnB)
Considere
Considere W=
W=16
16 ee os
osseguintes
seguintes 44 objetos:
objetos:
ii
11
22
33
44
vvi i
R$45
R$45
R$30
R$30
R$45
R$45
R$10
R$10
w
wi i
33
55
99
55
R$0
0
R$ 115
R$45
3
R$ 115
vvi/w
i/wi i
R$15
R$15
R$
R$ 66
R$
R$ 55
R$
R$ 22
R$0
0
R$ 79
R$75
8
R$ 115
R$120
17
max
R$75
8
R$ 85
R$90
12
R$ 96
X
R$100
17
X
© Jorge Figueiredo, DSC/UFCG
•• Usar
Usar BnB.
BnB.
•• Identificar
Identificarfunção
função de
de poda.
poda.
•• Guiar
Guiar BFS
BFS (Best-first
(Best-firstSearch)
Search)
2
12
15
17
14
3
4
18
40
2
3
4
B
14
15
13
22
18
40
C
11
17
19
23
D
17
14
20
28
B
14
15
13
22
11
17
19
23
D
17
14
20
28
3
18
13
19
20
2
12
12
© Jorge Figueiredo, DSC/UFCG
4
40
22
23
28
58
[58..73]
[58..73]
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Problema de Atribuição de Tarefas
A
B
C
D
1
11
14
11
17
2
12
15
17
14
3
18
13
19
20
4
40
22
23
28
A → 1 60
A → 1 60
A → 2 58
A → 2 58
A → 3 65
A → 3 65
A → 4 78
Análise e Técnicas de Algoritmos – 2005.1
87
73
Problema de Atribuição de Tarefas
1
11
14
11
17
1
11
1
Análise e Técnicas de Algoritmos – 2005.1
A
B
C
D
© Jorge Figueiredo, DSC/UFCG
11
C
X
Problema de Atribuição de Tarefas
A
A
R$90
12
R$ 90
Análise e Técnicas de Algoritmos – 2005.1
Problema de Atribuição de Tarefas
•n
•n agentes
agentes para
para nn tarefas.
tarefas.
•Cada
•Cada agente
agente deve
deve executar
executar exatamente
exatamente uma
uma única
única tarefa.
tarefa.
•Se
•Se ao
ao agente
agente ii éé atribuída
atribuída aa tarefa
tarefa j,j, um
um custo
custo CCi,ji,jéé
identificado.
identificado.
•Problema
•Problema éé atribuir
atribuir tarefas
tarefas aos
aos agentes
agentes para
para minimizar
minimizar oo custo
custo
total
total de
de executar
executar as
as nntarefas.
tarefas.
R$45
R$0
3 0
R$R$
55115
X
X
Análise e Técnicas de Algoritmos – 2005.1
X
R$45
3
R$ 96
[58..73]
A → 4 78
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
5
Problema de Atribuição de Tarefas
A
B
C
D
1
11
14
11
17
2
12
15
17
14
3
18
13
19
20
4
40
22
23
28
[58..73]
A → 1 60
A→2
Problema de Atribuição de Tarefas
58
A → 3 65
A
B
C
D
1
11
14
11
17
2
12
15
17
14
3
18
13
19
20
A → 2; B → 1 68
A→2
A → 2; B → 4 64
A → 3 65
3
18
13
19
20
© Jorge Figueiredo, DSC/UFCG
4
40
22
23
28
A→2
58
A → 3 65
A → 2; B → 3 59
A → 2; B → 4 64
A → 2; B → 1 68
Problema de Atribuição de Tarefas
A
B
C
D
A → 2; B → 4 64
1
11
14
11
17
2
12
15
17
14
3
18
13
19
20
4
40
22
23
28
[58..64]
A → 1 60
A → 2; B → 3; c → 1; d → 4
64
A → 2; B → 3 59
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
[58..73]
A → 1 60
A → 2; B → 1 68
A → 4 78
Problema de Atribuição de Tarefas
2
12
15
17
14
58
A → 2; B → 3 59
Análise e Técnicas de Algoritmos – 2005.1
1
11
14
11
17
[58..73]
A → 1 60
A → 4 78
A
B
C
D
4
40
22
23
28
A→2
58
A → 3 65
A → 2; B → 3; c → 4; d → 1
A → 2; B → 1 68
A → 2; B → 3; c → 1; d → 4
64
A → 2; B → 3 59
A → 2; B → 4 64
A → 2; B → 3; c → 4; d → 1
65
65
A → 4 78
Análise e Técnicas de Algoritmos – 2005.1
A → 4 78
© Jorge Figueiredo, DSC/UFCG
Eficiência de Backtracking e BnB
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Exercício: O Problema do Caixeiro Viajante
•• Fatores
Fatores que
que afetam
afetam aa eficiência:
eficiência:
–– tempo
tempo para
para gerar
gerar oo próximo
próximo vvkk;;
–– Cardinalidade
Cardinalidade de
de SSkksatisfazendo
satisfazendo as
as restrições;
restrições;
–– tempo
tempo de
de execução
execução da
da função
função de
de poda;
poda;
–– Cardinalidade
Cardinalidade de
de SSkksatisfazendo
satisfazendo aa função
função de
de poda.
poda.
•• Uma
Uma boa
boa função
função de
de poda
poda reduz
reduz substancialmente
substancialmente oo número
número
de
de nodos
nodos considerados.
considerados.
•• Existe
Existe um
um tradeoff:
tradeoff: uma
uma boa
boa função
função de
de poda
poda versus
versus oo tempo
tempo
de
de avaliá-la.
avaliá-la.
•• Para
Para estimar
estimar oo número
número de
de nodos
nodos gerados,
gerados, podemos
podemos usar
usar
Análise
Análise Monte-Carlo
Monte-Carlo (simulação
(simulação estatística).
estatística).
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
6
Exercício: O Problema do Caixeiro Viajante
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
7