Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica e algoritmos de aproximação - Coggle Diagram
Programação dinâmica e algoritmos de aproximação
Programação dinâmica - técnica de design de algoritmo que envolve a resolução do problema por meio da resolução e recordação de seus subproblemas
Exemplo : Quando calcular un dos números na sequências de Fibonacci, registrar cada número calculado até então, ou apenas registrar os dois últimos números
Pode ser considerado uma técnica do space-time tradeoff, embora algumas vezes não seja necessário o uso extra de memória
Uma forma de lidar com problemas de otimização
Aproximação Top down - resolve apenas os subproblemas necessários
Aproximação Bottom up - resolve todos os subproblemas
Exemplo : coin-row (pegar uma sequencia de moedas tal que tenha o maior valor máximo possível sem pegar duas moedas adjacentes) >> pegar o maior valor para as duas primeiras moedas, depois comparar o valor da terceira + primeira moedas e o da segunda moeda >> quando for checar uma nova moeda, checar o penúltimo resultado e comparar com o último sem essa nova moeda
Exemplo 2 : knapsack (dado n itens e um limite, achar o valor máximo da soma entre os elementos que não ultrapasse o limite) >> achar considerando a adição do primeiro item, depois checar os casos em que se pode adicionar o segundo, compara os valores máximos, ....
Memory Functions : forma de aplicar programação dinâmica apenas resolvendo os subproblemas necessários apenas uma vez (método para solucionar problemas na forma top down)
Ex : apenas preencher alguns valores na tabela da resolução do problema de Knapsack, ao invés de todos possíveis
Não é necessariamente mais espacialmente eficiente do que a versão bottom up
Algoritmos de aproximação - a solução não precisa ser a melhor possível, mas sim aceitável
NP hard - problemas pelo menos tão difíceis quanto NP complete
Ex : TSP (travelling salesman)
Nearest neighbor >> escolher um vértice de início, ir até a cidade mais perto da última visitada até que todas as cidades tenham sido visitadas, retornar ao início
Multifragmente heuristic >> ordenar as arestas em ordem crescente de peso, adicionar uma arestas se ela não criar um ciclo menor que o número de cidades ou não criar um vértice de grau 3
Ex : Circuito hamiltoniano com MST
Fazer a mst, fazer o caminho para todos os vértices por um inicial (como uma DFS), checar os vértices e eliminar os repetidos, exceto o inicial
Heuristic : regra de senso-comum dada por experiência sem uma prova matemática
Accuracy ratio : Solução encontrada / melhor solução, quanto melhor a aproximação, mais se aproxima de 1
Ex : knapsack
Calcular as razões valor/peso, ordenar os itens em ordem não crescente, se o item atual cabe na knapsack, colocar ele, caso contrário, seguir para o próximo