Please enable JavaScript.
Coggle requires JavaScript to display documents.
BACKTRACKING e B&B - Coggle Diagram
BACKTRACKING e B&B
BACKTRACKING
Conceito: Busca inteligente em espaço exponencial
Funcionamento
Constrói soluções componente por componente
Avalia candidatos parciais
Retrocede quando sem opções válidas
Usa árvore de espaço de estados
Estrutura da árvore
Raiz: Estado inicial
Níveis: Componentes da solução
Nós promissores: Podem levar a solução
Nós não-promissores: Becos sem saída
Folhas: Soluções ou dead ends
Exemplos clássicos
N-Queens: Posicionar rainhas sem ataque
Circuito Hamiltoniano: Visitar todos vértices
Subset-Sum: Subconjunto com soma específica
Otimizações
Explorar simetrias do problema
Pré-atribuir valores a componentes
Reordenar dados da instância
Estimativa de tamanho da árvore (Knuth)
Características
Aplicado a problemas combinatoriais difíceis
Melhor que busca exaustiva pura
Sucesso varia por problema e instância
Pior caso ainda exponencial
BRANCH-AND-BOUND
Conceito: Backtracking + função de limitação
Componentes principais
Função de limitação (bounding function)
Estratégia de seleção de nós
Critério de poda de ramos
Melhor solução conhecida
Estratégias de busca
Best-first: Nó mais promissor primeiro
Breadth-first: Por níveis
Depth-first: Profundidade primeiro
LIFO/FIFO: Ordem de processamento
Exemplos de aplicação
Problema da Atribuição
Limite inferior: Soma mínimos por linha/coluna
Poda quando limite > melhor solução
Problema da Mochila
Limite superior: Relaxação fracionária
Cada nó representa subconjunto de itens
Caixeiro Viajante
Limite inferior: Soma duas menores distâncias
Aproveita simetrias do grafo
Vantagens sobre backtracking
Poda mais eficiente com limitação
Encontra soluções ótimas para otimização
Flexibilidade na ordem de exploração
Pode usar informação adicional
Desafios
Escolha da função de limitação
Balanço entre simplicidade e eficácia
Estratégia de seleção de nós
Previsibilidade de desempenho
CONSIDERAÇÕES GERAIS
Aplicabilidade
Problemas NP-difíceis
Busca em espaços exponenciais
Quando algoritmos exatos são necessários
Alternativa a heurísticas aproximadas
Limitações
Complexidade exponencial no pior caso
Uso intensivo de memória
Difícil prever tempo de execução
Sensível a qualidade da limitação
Melhorias possíveis
Uso de simetrias do problema
Pré-processamento de dados
Soluções iniciais de boa qualidade
Paralelização da busca
Comparação com outras técnicas
Melhor que busca exaustiva
Exato vs aproximado (heurísticas)
Tempo vs qualidade da solução
Adequado para instâncias pequenas/médias