Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programação Dinâmica, Algoritmos de aproximação para problemas NP-Hard -…

- - - - Porém se o n for um número maior, então o tempo gasto para calcular algum(s) f(n*) vai ser muito custoso e o mesmo pode precisar ser calculado várias vezes
      - Abordagem Top-Down
    - - Toda vez que for preciso usar um f(n) que já foi calculado, basta pegar o valor na tabela
      - Normalmente essa tabela é construída a partir de uma base (as condições de paradas da recursão) (essa é a abordagem Bottom-Up)
        
        No caso de Fibonacci, a tabela começa o seu processo de construção com os dois primeiros elementos já nela, 0 e 1 (respectivamente)
        
        Dessa forma para calcula o próximo elemento é só calcular a soma dos dois anteriores a ele: (sem precisar construir toda aquela arvore de recursão)
        
        0 1 1 2 3 5 8 ...
        
        Três problemas foram resolvidos no livro com essa técnica:
        
        Problema de linha de moedas
        
        Em um cenário em que há alguma moedas, cada um com seu valor, alinhadas em fila, o objetivo é pegar a maior quantidade de dinheiro possível sem pegar duas moedas adjacentes
        
        Problema de fazer trocos
        
        ??
        
        Problema de coletar moedas
        
        Várias moedas são colocadas em células de um tabuleiro n × m, não mais do que uma moeda por célula. Um robô, localizado na célula superior esquerda do tabuleiro, precisa coletar o máximo de moedas possível e trazê-las para a célula inferior direita. Em cada etapa, o robô pode mover uma célula para a direita ou uma célula para baixo de sua localização atual. O objetivo é encontrar o número máximo de moedas que o robô pode coletar e um caminho que ele precisa seguir para fazer isso.
        
        O Bottom-Up resolve todos os sub problemas antes do problema em questão
- - - - Funções da memoria
        
        Esse método resolve um determinado problema de maneira Top-Down, mas, além disso, mantém uma tabela do tipo que seria usada por um algoritmo de programação dinâmica Bottom-Up.
        
        Inicialmente, todas as células da tabela são inicializadas com um símbolo especial "null" para indicar que ainda não foram calculadas. Depois disso, sempre que um novo valor precisa ser calculado, o método verifica primeiro a célula correspondente na tabela:
        
        Se essa célula não for “null”, o valor é recuperado da tabela
        
        Caso contrário, é calculado pela chamada recursiva cujo resultado é então registrado na tabela.
- - - - Uma solução para achar essas soluções é usar um algoritmo de aproximação, pois esse é eficiente, porém não exato, mas na vida real é melhor levar um tempo curto para achar uma aproximação do que levar centenas de anos para encontrar a resposta com exatidão
        
        Na maioria dos casos, esse algoritmo de aproximação vai usar características dos resultados obtidos para encontrar uma aproximação para qualquer n instância, essa observação é chamada de heurística e ela não leva tanto em conta os aspectos matemáticos do problema e sim a experiência que alguns resultados trazem
        
        A taxa de precisão é calculada da seguinte forma:
        
        r(s a)= f(s*)/f(s a)
        
        Onde "s a" é uma solução obtida pelo algoritmo de aproximação e o s* é a resposta exata do problema
        
        Obviamente quando mais perto de 1 (100%) mais próximo a aproximação está do valor exato
        
        Um algoritmo de aproximação em tempo polinomial é dito com algoritmo de aprocimação-c, se v( s a)<= c, ou seja, se a taxa de precisão não ultrapassar c em nenhuma instância daquele problema
        
        O menor (melhor) c é chamado de razão de desempenho do algoritmo e denotado como RA
        
        Quanto mais próximo de 1, melhor o RA
        
        Mesmo utilizando essa técnica, não é tão simples encontrar um bom algoritmo de aproximação para todos os problemas dessa classe