Please enable JavaScript.
Coggle requires JavaScript to display documents.
mapa mental 16 - Coggle Diagram
mapa mental 16
Três exemplos de problemas relacionados a programação dinâmica são... O problema da moeda que consiste em pegar a quantidade máxima de dinheiro de forma que nenhuma moeda adjacente a outra na linha original de moedas seja pega
O problema do troco; consiste em dar o troco(em dinheiro) com a quantidade mínima de cédulas ou moedas; no problema de cima poderíamos construir uma tabela para armazenar as soluções do subproblemas mas no caso do problema do troco isso se tornaria custoso;
O terceiro exemplo é o problema da coleta de moedas que consiste em dispor uma certa quantidade de moedas em um tabuleiro com nXm quadrados e um robô colocado no quadrado superior esquerdo, precisa coletar o máximo de moedas e colocar no quadrado inferior direito. o robô pode apenas se movimentar uma vez para direita ou uma vez para baixo a cada lance, o algoritmo deve achar a quantidade máxima de moedas e o caminho que o robô faz
Na etapa final dos três algoritmos que resolvem esses três problemas, usamos uma estratégia de ir voltando nas computações que foram feitas, para achar de fato a melhor solução para o elemento i;
Uma grande diferença entre a programação dinâmica e uma aproximação top-down para a solução do problema. é que a top-down resolve subproblemas mais de uma vez, tornando-a pouco eficiente, já a programação dinâmica resolve esses subproblemas apenas uma vez
Porém numa solução por programação dinâmica resolve alguns problemas que não precisam ser resolvidos ao contrário de uma aproximação top-down, então uma ideia seria combinar uma vantagem de cada tipo de solução, isso é possível através de funções de memória;
NP-hard problems são aqueles, pelo menos tão difíceis quanto os NP-complete
Um algoritmo de aproximação polinomial é chamado de C-approximation algorithm, onde c é a razão de precisão
Com o melhor valor para C podemos calcular o índice de performance( o ideal seria um índice de 1) que é a principal métrica para analisar a qualidade de um algoritmo
As aproximações mais simples para o algoritmo do comerciante viajante são baseadas nos algoritmos gulosos, um desses algoritmos é o algoritmo do vizinho mais próximo, porém os resultados obtidos com ele não são muito bons
O algoritmo dos fragmentos heurísticos múltiplos é outra opção de algoritmo guloso, os caminhos achados por ele são melhores do que o algoritmo do vizinho mais próximo porém seu índice de performance também não tem limites
Também existem algoritmos baseados em árvores mínimas que podem ser usados para o problema do comerciante viajante, um deles é o Twice-around the tree algorithm
Outro algoritmo que usa as árvores mínimas é o algoritmo de Christofides, porém ele tem uma melhor eficiência.
algoritmos baseados Buscas heurísticas locais podem ser usados em instancias euclidianas para achar caminhos de forma surpreendentemente boa, os melhores conhecidos são, 2-opt, 3-opt and Lin-Kernighan
Para o problema da mochila, os algoritmos gulosos e suas aproximações também podem ser usadas;
Programação dinâmica é um termo usado para se referir a otimizações em geral, pelo menos no campo da ciência da computação
A programação dinâmica consiste em resolver subproblemas apenas uma vez e salvar essas informações para resolver problemas maiores
O principio da otimização Segundo Bellman é que uma solução para otimização é compostas pelas soluções otimizadas de seus subproblemas
A solução para o problema da mochila também pode ser pensada com a estratégia da programação dinâmica, resolver subproblemas para depois resolver um problema maior
As funções de memória consistem em inicializar arrays ou tables com símbolos NULL, para os problemas de programação dinâmica, com isso é possível verificar se um valor que será armazenado já foi calculado, ou seja, se o index referente a ele for diferente de NULL