Please enable JavaScript.
Coggle requires JavaScript to display documents.
(M17) CHAPTER 8 AND 12 (8.1, 8.2, 12.3) - Coggle Diagram
(M17) CHAPTER 8 AND 12 (8.1, 8.2, 12.3)
Basic Examples
Problema da Sequência de Fibonacci
Exponencial devido à duplicação de subproblemas.
Implementação direta usando chamada recursiva.
Problema da Torre de Hanói
Solução baseada em mover (n-1) discos recursivamente.
Exponencial, com tempo de execução O(2^n).
Problema do Caminho Mínimo em um Triângulo
Solução baseada em recursão para somar caminhos.
Exponencial se recursivo e (n²) com memorização
Knapsack problem and Memory functions
Knapsack
Fórmula recursiva para escolher ou não cada item.
Exponencial em abordagem recursiva simples.
Uso de tabela para armazenar resultados intermediários.
Memory functions
Reduz duplicação de cálculos.
Técnica para otimizar algoritmos recursivos.
Aplicação no problema da mochila e outros.
Redução de tempo de execução de exponencial para polinomial.
Algoritmos de Aproximação para Problemas NP-Difíceis
Problemas sem solução exata eficiente.
Importante para problemas grandes e complexos.
Algoritmos de Aproximação para o Problema do Caixeiro Viajante
Escolha localmente ótima em cada etapa.
Árvore Geradora Mínima
Algoritmos Gulosos
Algoritmos de Aproximação para o Problema da Mochila
Seleção baseada em razão valor/peso.
Fator de Aproximação
Normalmente O(n log n), com aproximação O(n C)
Heurística