Please enable JavaScript.

Coggle requires JavaScript to display documents.

((Backtracking & Branch-and-Bound)) - Coggle Diagram

- - - - Conceito
        
        Busca mais eficiente que exaustiva
        
        Usa árvore de espaço de estados (DFS)
        
        Abandona caminhos não promissores (retrocede)
      - Estrutura
        
        Cada nó = decisão parcial
        
        Folhas = solução ou beco sem saída
        
        Nó promissor vs não promissor
      - Exemplos
        
        N-Queens
        
        Colocar n rainhas sem ataque
        
        Simetria reduz buscas
        
        Hamiltonian Circuit
        
        Visita todos vértices sem repetir
        
        Subset Sum
        
        Soma de subconjuntos igual a valor alvo
        
        Poda por soma inválida
      - Observações
        
        Pode explorar todo espaço (exponencial)
        
        Estimativa de tamanho com método de Knuth
        
        Útil para problemas combinatórios difíceis
        
        Estratégias para reduzir árvore:
        
        Explorar simetrias
        
        Pré-fixação de valores
        
        Ordenação dos dados
    - - Conceito
        
        Foco em problemas de otimização
        
        Usa bounds para eliminar ramos
        
        Mantém melhor solução vista até o momento
      - Requisitos
        
        Função de limite para cada nó
        
        Valor da melhor solução até agora
      - Estratégia
        
        Poda ocorre se:
        
        Bound >= melhor solução (minimização)
        
        Restrição violada
        
        Solução única viável (compara com melhor)
        
        Tipo:
        
        Best-First: expande nó mais promissor (menor bound)
      - Exemplos
        
        Assignment Problem
        
        Seleção de menor elemento por linha como bound
        
        Knapsack Problem
        
        Bound com valor/volume restante
        
        Árvore binária de inclusão/exclusão
        
        TSP (Caixeiro Viajante)
        
        Bound baseado nas duas menores distâncias por cidade
      - Observações
        
        Escolha de função de bound é crítica
        
        Pode usar heurísticas para solução inicial
        
        Melhor balancear simplicidade e precisão do bound