Busca Combinatorial e
Métodos de Heurística
Baseado em:
The Algorithm Design Manual
Steven S. Skiena
Introdução (1)



O uso de técnicas de busca exaustiva
pode ser usada para resolver problemas
pequenos.
Em algumas aplicações é necessário
gastar-se para ter certeza da solução
encontrada.
Isto implica em testar todas as
instâncias.
Introdução (2)



Backtracking é uma técnica para listar
todas as configurações representando
possíveis soluções para um problema
algorítmico combinatorial.
Pruning Search melhora a eficiência
eliminando configurações irrelevantes.
Para problemas grandes, o método
heurístico de simulated anneling será
utilizado.
Observações (1)


Busca combinatorial, combinado com
técnicas de tree pruning, pode ser
utilizada para encontrar a solução ótima
de problemas pequenos de otimização.
Técnicas engenhosas de pruning podem
acelerar a busca combinatorial para um
alcance surpreendente.
Observações (2)

Simulated Annealing é uma técnica
simples mas eficaz para eficientemente
obter soluções boas embora não ótimas
para problemas de busca combinatorial.
Backtracking (1)


É uma forma sistemática de percorrer
todas as possíveis configurações de um
espaço.
Estas configurações podem ser todos os
arranjos de objetos ou todas as formas
possíveis de construir uma coleção
deles.
Backtracking (2)

Outras aplicações podem necessitar de:



enumeração de todas as árvores
geradoras;
todos os caminhos entre dois vértices;
todos as possíveis formas de particionar os
vértices em classes de cores.
Backtracking (3)


É necessário gerar cada uma das
possíveis configurações exatamente
uma vez.
Para evitar configurações repetidas e/ou
perdidas, devemos definir uma ordem
sistemática de geração entre todas as
configurações possíveis.
Backtracking (4)


As configurações são representadas por
um vetor A=(a1, a2, ..., an), onde cada
elemento ai é selecionado de um
conjunto de possíveis candidatos Si
para a posição i.
O procedimento de busca aumenta a
solução um elemento de cada vez.
Backtracking (5)



A partir de uma solução parcial
(a1, a2, ..., ak),
com k n, construímos o conjunto Sk+1 de
possíveis soluções para as k+1 primeiras
posições.
Tentamos estender o conjunto de soluções
parciais adicionando o próximo elemento de
Sk+1.
Se é possível estender esta solução parcial, o
fazemos e tentamos estendê-la mais ainda.
Backtracking (6)


Se o conjunto está vazio, não há como
estender a solução parcial corrente.
Neste caso, devemos retroceder e
trocar ak, o último elemento colocado,
por um novo elemento de Sk.
Backtracking (7)



Backtracking constrói uma árvore de
soluções parciais, onde cada vértice é
uma solução parcial.
Uma aresta de x para y significa que y
foi criado a partir de um avanço de x.
O processo de construir as soluções
corresponde a uma busca em
profundidade nesta árvore.
Backtracking (8)



Pode-se usar busca em largura para
enumerar todas as soluções.
Prefere-se busca em profundidade por causa
da quantidade de espaço.
Na busca de profundidade, o estado corrente
está completamente representado pelo
caminho a partir da raiz, que necessita de
espaço proporcional à altura da árvore.
Backtracking (9)


Na busca em largura, a fila armazena
todos os nós de um nível corrente, que é
proporcional à largura da árvore de busca.
Para muitos problemas interessantes, a
largura da árvore cresce exponencialmente
em sua altura.
Construção de todos os
subconjuntos (1)





Quantos subconjuntos existem para um
conjunto de n elementos inteiros {1,2, ..., n}?
Para n=1,
dois subconjuntos {} e {1}.
Para n=2,
quatro subconjuntos.
Para n=3,
oito subconjuntos...
Para n elementos,
2n subconjuntos.
Construção de todos os
subconjuntos (2)



Cada subconjunto é descrito pelos
elementos que a ele pertencem.
Cada subconjunto pode ser
representado por um vetor de n células,
onde cada posição i contém um valor V
ou F.
Na notação, Sk=(V,F).
Construção de todos os
subconjuntos (3)
Construir todos os subconjuntos de
{1,2,3}.
(1) (1,2) (1,2,3)* (1,2,-)* 
(1,-) (1,-,3)* (1,-,-)* (1,-) 
(1)  (-) (-,2) (-,2,3)* 
(-,2,-)* (-,-) (-,-,3)* (-,-,-)* 
(-,-) (-) ()

Construção de todas as
permutações (1)




Temos que contar as permutações.
Existem n escolhas distintas para o
valor do primeiro elemento de uma
permutação de {1,...n}.
Para o próximo elemento, existem n-1
escolhas para o segundo elemento.
Total de permutações distintas é n!.
Construção de todas as
permutações (2)


Utiliza-se um vetor de n elementos.
O conjunto de candidatos para a i-ésima
posição será formada pelos elementos
que não apareceram nas (i-1) primeiras
posições da solução parcial.
Construção de todas as
permutações (3)

As permutações dos elementos {1,2,3} são
obtidos da seguinte forma:
(1) (1,2) (1,2,3)* (1,2) (1) 
(1,3) (1,3,2)* (1,3) (1) () 
(2) (2,1) (2,1,3)* (2,1) (2) 
(2,3) (2,3,1)* (2,3) (2) () 
(3)  (3,1)  (3,1,2)* (3,1) (3) 
(3,2) (3,2,1)*  (3,2) (3) ()
Construindo todos os
caminhos em um grafo (1)


Enumerar todos os possíveis caminhos
entre dois vértices s e t de um grafo é
um problema um pouco mais
complicado.
Não há uma fórmula explícita que conta
o número de soluções em função do
número de vértices ou arestas.
Construindo todos os
caminhos em um grafo (2)




O início de qualquer caminho é sempre s, assim
S1={s}.
O conjunto de possíveis candidatos para a
segunda posição são os vértices vizinhos a s.
Sk+1 consiste do conjunto de vértices adjacentes a
ak que ainda não foram utilizados na solução
parcial.
A solução deve ter espaço suficiente para todos os
n vértices, embora nem todos sejam utilizados.
Construindo todos os
caminhos em um grafo (3)
4
5
3
5
4
6
6
3
4
2
5
3
2
4
1
6
5
3
6
1
5
6
3
4
2
3
4
2
6
5
2
5
2
2
6
4
3
3
4
Search Pruning (1)



Backtracking garante a corretude
enumerando todas as possibilidades.
Em algumas aplicações algumas das
possibilidades não precisam ser geradas.
Para isto, o conjunto de próximos
elementos contém somente movimentos
que são legais para a configuração parcial
corrente.
Search Pruning (2)

A poda (pruning) é uma técnica em que
a busca é interrompida em uma posição
a partir da qual a solução parcial não
pode ser estendida.
Minimização de Largura de
Banda


O problema da largura de banda
(bandwidth problem) tem como entrada
um grafo G com n vértices e m arestas.
O objetivo é determinar uma
permutação dos vértices alinhados que
minimize o comprimento máximo de
qualquer aresta.
1
11
5
9
1
1
1
1
1
1
1
1
1
1
1