Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com Limitações de Algoritmos - Coggle Diagram
Lidando com Limitações de Algoritmos
Backtracking
Ideia
Busca por soluções válidas recursivamente
Usa podas: interrompe caminhos que não podem levar à solução
Aplicações clássicas
Sudoku, N-queens, labirinto, subconjuntos
Objetivo
Resolver problemas por tentativa e erro controlado
Explora árvore de decisões -> volta atrás quando caminho inválido é detectado
Branch-and-Bound
Ideia
Cada subproblema tem um limite inferior estimado
Poda ramos que não podem melhorar a melhor solução atual
Exemplo clássico:
Problema do Caixeiro Viajante (TSP)
Objetivo
Resolver problemas de otimização combinatória
Explora soluções parciais, mas também mantém melhor solução encontrada até agora
Limitações do Poder dos Algoritmos
Problemas intratáveis
Algoritmo existe, mas tempo de execução é impraticável
Ex: problemas NP-completos (como o caixeiro viajante)
Soluções práticas
Técnicas para reduzir o espaço de busca -> Backtracking e Branch-and-Bound
Problemas não resolvíveis
Não existe algoritmo que resolva o problema para todos os casos
Ex: Problema da parada (Halting Problem)