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)

1

2

3

4

5

61

2

3

4

5

6

5

4

3

3

4

4

65

4

2

6

5

2

3 62

5

6

2

3

52

433

6

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