Please enable JavaScript.

Coggle requires JavaScript to display documents.

Técnicas de projeto de algoritmos, Branch and Bound, Backtracking - Coggle…

- - - - Embora em alguns casos ainda esbarre no crescimento exponencial ou pior
- - - - Se o valor limite não for melhor que o valor da melhor solução o nó é não promissor e pode ser terminado
- - - - Melhor retorno por unidade de peso
    - - Pior retorno por unidade de peso
- - - - O algoritmo retrocede para substituir o último componente da solução parcialmente construída
  - - - Não promissores o soluções completas para o algoritmo
  - - - Se não houver mais uma opção ele volta um nível acima e assim por diante
- - - - Escolhas feitas através de avanços e retrocessos
      - Para encontrar mais respostas pode continuar o processo da folha onde foi achada a solução
  - - - Esquerda
        
        Inclusão
      - Direita
        
        Exclusão
      - Raiz
        
        Começo (sem decisões)
      - Variável s
        
        Representa a soma
        
        Se s é igual a d tem-se a solução
        
        Se s é diferente de d marca-se o nó como não promissor
- - - - Problema n-queens e circuito hamiltoniano
    - - Problema da soma de subconjunto
    - - Tupla pode precisar satisfazer restrições
    - - Os nós representam tuplas parcialmente construídas
  - - - Truques para reduzir o tamanho de uma state space tree
        
        Explorar a simetria
        
        Pré atribuir valores a um ou mais componente de uma solução
        
        Pré ordenamento de dados
        
        Reorganizar dados de uma dada instância
        
        Desejável estimar o tamanho da state space tree
        
        Difícil de fazer
        
        Gerar caminho aleatório da raiz para uma folha e usar informações sobre o número de opções disponíveis durante a geração do caminho
        
        Gerar várias estimativas e calcular uma média produz uma estimativa útil do tamanho da árvore