Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming - Coggle Diagram
Dynamic Programming
Approximation algorithms
-
Alternativa: “resolver” o problema usando algoritmos de aproximação. A solução não precisa ser ótima, mas apenas aceitável.
-
-
-
Embora os algoritmos de aproximação variem em nível de sofisticação, a maioria deles é baseada em alguma heurística específica do problema.
Uma heurística é uma regra de senso comum extraída da experiência e não de uma teoria matematicamente comprovada.
Etapa 1 Classificar as arestas em ordem crescente de seus pesos.(Os laços podem ser quebrados
arbitrariamente.). Inicializar o conjunto de arestas de passeio a serem construídas para o conjunto vazio.
Etapa 2 Repita este passo n vezes, onde n é o número de cidades na instância sendo resolvido: adicione a próxima aresta na lista de arestas ordenadas ao conjunto de tour arestas, desde que esta adição não crie um vértice de grau 3 ou um
ciclo de duração inferior a n; caso contrário, pule a borda.
-