Please enable JavaScript.

Coggle requires JavaScript to display documents.

Back-tracking e Branch-and-bound - Coggle Diagram

- - - - As principais aplicações desse tipo de algoritmo são para a construção de todos os 2^n subconjuntos de um conjunto S, com n elementos e todas as permutações desse conjunto
      - Backtracking é aplicável na solução de vários problemas conhecidos, dentre os quais podem-se destacar:
        
        N-Rainhas
        
        Encontrar Espaço de Soluções
        
        Passeio do Cavalo
        
        Problemas de labirinto
        
        Caixeiro Viajante
      - O procedimento é usado em linguagens de programação como Prolog. Uma busca inicial em um programa nessa linguagem segue o padrão busca em profundidade, ou seja, a árvore é percorrida sistematicamente de cima para baixo e da esquerda para direita
      - É um algoritmo que representa um refinamento da busca por força bruta, em que múltiplas soluções podem ser eliminadas sem serem explicitamente examinadas
      - Entrada: X [1..i] especifica primeiro i componentes promissores de uma solução
      - Saída: todas as tuplas que representam as soluções do problema
- - - - É utilizado para vários problemas NP-completos como:
        
        Problema da mochila
        
        Problema do caixeiro viajante
      - Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada
      - O termo branch refere-se ao fato de que o método efetua partições no espaço das soluções e o termo bound ressalta que a prova da otimalidade da solução utiliza-se delimites calculados ao longo da enumeração
      - É um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória