Busca Combinatorial e Métodos de Heurística Baseado em: The Algorithm Design Manual Steven S. Skiena

  • View
    106

  • Download
    3

Embed Size (px)

Text of Busca Combinatorial e Métodos de Heurística Baseado em: The Algorithm Design Manual Steven S....

  • Slide 1
  • Busca Combinatorial e Mtodos de Heurstica Baseado em: The Algorithm Design Manual Steven S. Skiena
  • Slide 2
  • Introduo (1) O uso de tcnicas de busca exaustiva pode ser usada para resolver problemas pequenos. Em algumas aplicaes necessrio gastar-se para ter certeza da soluo encontrada. Isto implica em testar todas as instncias.
  • Slide 3
  • Introduo (2) Backtracking uma tcnica para listar todas as configuraes representando possveis solues para um problema algortmico combinatorial. Pruning Search melhora a eficincia eliminando configuraes irrelevantes. Para problemas grandes, o mtodo heurstico de simulated anneling ser utilizado.
  • Slide 4
  • Observaes (1) Busca combinatorial, combinado com tcnicas de tree pruning, pode ser utilizada para encontrar a soluo tima de problemas pequenos de otimizao. Tcnicas engenhosas de pruning podem acelerar a busca combinatorial para um alcance surpreendente.
  • Slide 5
  • Observaes (2) Simulated Annealing uma tcnica simples mas eficaz para eficientemente obter solues boas embora no timas para problemas de busca combinatorial.
  • Slide 6
  • Backtracking (1) uma forma sistemtica de percorrer todas as possveis configuraes de um espao. Estas configuraes podem ser todos os arranjos de objetos ou todas as formas possveis de construir uma coleo deles.
  • Slide 7
  • Backtracking (2) Outras aplicaes podem necessitar de: enumerao de todas as rvores geradoras; todos os caminhos entre dois vrtices; todos as possveis formas de particionar os vrtices em classes de cores.
  • Slide 8
  • Backtracking (3) necessrio gerar cada uma das possveis configuraes exatamente uma vez. Para evitar configuraes repetidas e/ou perdidas, devemos definir uma ordem sistemtica de gerao entre todas as configuraes possveis.
  • Slide 9
  • Backtracking (4) As configuraes so representadas por um vetor A=(a 1, a 2,..., a n ), onde cada elemento a i selecionado de um conjunto de possveis candidatos S i para a posio i. O procedimento de busca aumenta a soluo um elemento de cada vez.
  • Slide 10
  • Backtracking (5) A partir de uma soluo parcial (a 1, a 2,..., a k ), com k n, construmos o conjunto S k+1 de possveis solues para as k+1 primeiras posies. Tentamos estender o conjunto de solues parciais adicionando o prximo elemento de S k+1. Se possvel estender esta soluo parcial, o fazemos e tentamos estend-la mais ainda.
  • Slide 11
  • Backtracking (6) Se o conjunto est vazio, no h como estender a soluo parcial corrente. Neste caso, devemos retroceder e trocar a k, o ltimo elemento colocado, por um novo elemento de S k.
  • Slide 12
  • Backtracking (7) Backtracking constri uma rvore de solues parciais, onde cada vrtice uma soluo parcial. Uma aresta de x para y significa que y foi criado a partir de um avano de x. O processo de construir as solues corresponde a uma busca em profundidade nesta rvore.
  • Slide 13
  • Backtracking (8) Pode-se usar busca em largura para enumerar todas as solues. Prefere-se busca em profundidade por causa da quantidade de espao. Na busca de profundidade, o estado corrente est completamente representado pelo caminho a partir da raiz, que necessita de espao proporcional altura da rvore.
  • Slide 14
  • Backtracking (9) Na busca em largura, a fila armazena todos os ns de um nvel corrente, que proporcional largura da rvore de busca. Para muitos problemas interessantes, a largura da rvore cresce exponencialmente em sua altura.
  • Slide 15
  • Construo 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, 2 n subconjuntos.
  • Slide 16
  • Construo de todos os subconjuntos (2) Cada subconjunto descrito pelos elementos que a ele pertencem. Cada subconjunto pode ser representado por um vetor de n clulas, onde cada posio i contm um valor V ou F. Na notao, S k =(V,F).
  • Slide 17
  • Construo 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)* (-,-,-)* (-,-) (-) ()
  • Slide 18
  • Construo de todas as permutaes (1) Temos que contar as permutaes. Existem n escolhas distintas para o valor do primeiro elemento de uma permutao de {1,...n}. Para o prximo elemento, existem n-1 escolhas para o segundo elemento. Total de permutaes distintas n!.
  • Slide 19
  • Construo de todas as permutaes (2) Utiliza-se um vetor de n elementos. O conjunto de candidatos para a i-sima posio ser formada pelos elementos que no apareceram nas (i-1) primeiras posies da soluo parcial.
  • Slide 20
  • Construo de todas as permutaes (3) As permutaes dos elementos {1,2,3} so 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) ()
  • Slide 21
  • Construindo todos os caminhos em um grafo (1) Enumerar todos os possveis caminhos entre dois vrtices s e t de um grafo um problema um pouco mais complicado. No h uma frmula explcita que conta o nmero de solues em funo do nmero de vrtices ou arestas.
  • Slide 22
  • Construindo todos os caminhos em um grafo (2) O incio de qualquer caminho sempre s, assim S 1 ={s}. O conjunto de possveis candidatos para a segunda posio so os vrtices vizinhos a s. S k+1 consiste do conjunto de vrtices adjacentes a a k que ainda no foram utilizados na soluo parcial. A soluo deve ter espao suficiente para todos os n vrtices, embora nem todos sejam utilizados.
  • Slide 23
  • Construindo todos os caminhos em um grafo (3) 1 2 3 4 5 6 1 2 3 4 5 6 5 4 3 3 4 4 6 5 4 2 6 5 2 36 2 5 6 2 3 5 2 4 3 3 6 4
  • Slide 24
  • Search Pruning (1) Backtracking garante a corretude enumerando todas as possibilidades. Em algumas aplicaes algumas das possibilidades no precisam ser geradas. Para isto, o conjunto de prximos elementos contm somente movimentos que so legais para a configurao parcial corrente.
  • Slide 25
  • Search Pruning (2) A poda (pruning) uma tcnica em que a busca interrompida em uma posio a partir da qual a soluo parcial no pode ser estendida.
  • Slide 26
  • Minimizao de Largura de Banda O problema da largura de banda (bandwidth problem) tem como entrada um grafo G com n vrtices e m arestas. O objetivo determinar uma permutao dos vrtices alinhados que minimize o comprimento mximo de qualquer aresta.
  • Slide 27
  • 111591111111111 1