Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programação Dinamica - Coggle Diagram

- - - - ALGORITMO
        
        Defina um vetor V de tamanho n+1, onde V[i] representa o valor máximo que pode ser obtido usando as primeiras i moedas.
        
        Inicialize V[0] = 0 e V[1] = A[1], ou seja, o valor máximo que pode ser obtido com nenhuma moeda é 0, e o valor máximo que pode ser obtido com uma moeda é o valor da primeira moeda.
        
        Para i = 2 até n, calcule V[i] usando a seguinte fórmula: V[i] = max(V[i-1], V[i-2] + A[i]), ou seja, o valor máximo que pode ser obtido com as primeiras i moedas é o máximo entre o valor máximo que pode ser obtido com as primeiras i-1 moedas (ignorando a i-ésima moeda) e o valor máximo que pode ser obtido com as primeiras i-2 moedas mais o valor da i-ésima moeda.
        
        O valor máximo que pode ser obtido usando todas as moedas é V[n].
  - - - ALGORITMO
        
        Defina um vetor C de tamanho V+1, onde C[i] representa o número mínimo de moedas necessárias para formar o valor i.
        
        Inicialize C[0] = 0 e C[i] = infinito para i > 0, ou seja, o número mínimo de moedas para formar o valor 0 é 0, e o número mínimo de moedas para formar qualquer outro valor ainda não foi calculado.
        
        Para cada moeda j no conjunto de moedas, para i = j até V, calcule C[i] usando a seguinte fórmula: C[i] = min(C[i], C[i-j]+1), ou seja, o número mínimo de moedas para formar o valor i é o mínimo entre o número mínimo de moedas necessário para formar o valor i usando as moedas anteriores e o número mínimo de moedas necessário para formar o valor i-j mais uma moeda de valor j.
        
        O número mínimo de moedas necessário para formar o valor V é C[V].
  - - - ALGORITMO
        
        .
        
        Defina uma matriz A de tamanho m+1 x n+1, onde A[i][j] representa o valor máximo que pode ser obtido coletando moedas da célula (1,1) até a célula (i,j) da grade.
        
        Inicialize A[1][1] = valor da célula (1,1) e A[i][1] = A[i-1][1] + valor da célula (i,1) e A[1][j] = A[1][j-1] + valor da célula (1,j), ou seja, o valor máximo que pode ser obtido na célula (1,1) é o valor da célula em si, e o valor máximo que pode ser obtido na primeira coluna e primeira linha é a soma acumulada do valor das células.
        
        Para i = 2 até m, e para j = 2 até n, calcule A[i][j] usando a seguinte fórmula: A[i][j] = max(A[i-1][j], A[i][j-1]) + valor da célula (i,j), ou seja, o valor máximo que pode ser obtido na célula (i,j) é o máximo entre o valor máximo que pode ser obtido na célula acima ou à esquerda, mais o valor da célula (i,j) em si.
        
        O valor máximo que pode ser obtido coletando moedas da célula (1,1) até a célula (m,n) é A[m][n].
- - - - Algoritmos de aproximação gulosa: esses algoritmos seguem uma estratégia gulosa, ou seja, a cada etapa escolhem a opção que parece ser a melhor no momento, sem considerar as consequências futuras. são frequentemente usados para resolver problemas de otimização que exigem soluções rápidas,
      - Algoritmos de aproximação baseados em programação linear: esses algoritmos buscam uma solução ótima para um problema linear, mas permitem que algumas variáveis assumam valores fracionários. usados para resolver problemas de otimização que podem ser formulados como um problema de programação linear inteira mista
      - Algoritmos de aproximação baseados em arredondamento: esses algoritmos arredondam as soluções fracionárias de um problema de programação linear para obter uma solução inteira. usados para resolver problemas de otimização de programação inteira
      - Algoritmos de aproximação baseados em heurísticas: esses algoritmos usam técnicas heurísticas para encontrar soluções próximas da solução ótima. usados para resolver problemas NP-difíceis que não possuem soluções polinomiais exatas conhecidas
    - - Problema do Caixeiro Viajante
        
        objetivo é encontrar o menor caminho que visite todos os vértices de um grafo ponderado. O problema é conhecido por ser NP-difícil e não há algoritmos conhecidos para resolvê-lo em tempo polinomial para todas as entradas.
        
        ALGORITMOS PARA RESOLVER
        
        Algoritmo do vizinho mais próximo: este é um algoritmo guloso simples que começa em um vértice arbitrário e visita o vizinho mais próximo a cada etapa. Esse algoritmo é fácil de implementar e geralmente produz soluções razoáveis, mas não é garantido que produza a solução ótima.
        
        Algoritmo 2-ópt: este algoritmo é uma heurística de busca local que tenta melhorar uma solução existente, removendo duas arestas cruzadas e as substituindo por duas arestas não cruzadas. Este algoritmo é rápido e geralmente produz soluções próximas à solução ótima, mas não é garantido que produza a solução ótima.
        
        Algoritmo de Lin-Kernighan: este algoritmo é uma heurística de busca local que tenta melhorar uma solução existente, removendo uma sequência de arestas e as substituindo por uma nova sequência de arestas. Este algoritmo é muito eficiente e produz soluções muito próximas da solução ótima em muitos casos.
        
        Algoritmo de Christofides: este algoritmo produz uma solução que é no máximo 1,5 vezes a solução ótima. O algoritmo começa encontrando uma árvore geradora mínima do grafo ponderado. Em seguida, adiciona-se um circuito euleriano na árvore, que visita cada aresta exatamente duas vezes. Finalmente, remove-se as repetições para obter um caminho hamiltoniano.
        
        algoritmos de aproximação possam produzir soluções próximas à solução ótima, eles não são garantidos para encontrar a solução ótima.
        
        escolha do algoritmo de aproximação depende do tamanho do grafo, da disponibilidade de recursos computacionais e da precisão desejada na solução.
    - - knapsack problem
        
        problema de otimização combinatória que envolve escolher um subconjunto de itens de um conjunto de itens, cada um com um valor e peso associados, de modo a maximizar o valor total dos itens selecionados sem exceder a capacidade da mochila (que é limitada pelo peso máximo que ela pode carregar).
        
        O problema da mochila é conhecido por ser NP-difícil, o que significa que não há algoritmos conhecidos para resolvê-lo em tempo polinomial para todas as entradas.
        
        ALGORITMOS PARA RESOLVER
        
        Algoritmo guloso, que seleciona os itens mais valiosos primeiro, até que a capacidade da mochila seja atingida. No entanto, esse algoritmo não leva em conta o peso dos itens, o que pode levar a soluções subótimas.
        
        Algoritmo de programação dinâmica, que divide o problema em subproblemas menores e resolve-os de forma recursiva. No entanto, esse algoritmo pode ser impraticável para grandes conjuntos de itens.
        
        Algoritmo de aproximação FPTAS (Fully Polynomial-Time Approximation Scheme). Esse algoritmo usa a técnica de escalonamento para reduzir o valor dos itens para que eles possam ser resolvidos em tempo polinomial usando programação dinâmica. O algoritmo FPTAS é garantido para produzir uma solução que é no mínimo (1 - ε) vezes a solução ótima, onde ε é um parâmetro de precisão especificado pelo usuário. Ele é um dos mais eficazes para esse problema
        
        Algoritmo PTAS (Polynomial-Time Approximation Scheme), que é semelhante ao FPTAS, mas permite um parâmetro de precisão mais amplo e é mais geral em sua aplicação.
        
        A escolha do algoritmo de aproximação depende do tamanho do conjunto de itens, da disponibilidade de recursos computacionais e da precisão desejada na solução.