Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic Programming, Approximation Algorithms for NP-Hard Problems -…

- - - - Para resolver esse problema, a dynamic programming sugere resolver cada um dos pequenos subproblemas apenas uma vez e armazanar a solução em uma tabela do qual uma solução para o problema original pode ser obtido.
- - - - Seja F (n) a quantidade máxima que pode ser retirada da linha de n moedas. Para derivar uma recorrência para F (n), particionamos todas as seleções de moedas permitidas em dois grupos: aqueles que incluem a última moeda e aqueles sem ela.
        
        A maior quantia que podemos obter do primeiro grupo é igual a cn + F (n − 2) – o valor da enésima moeda mais a quantia máxima que podemos retirar das primeiras n − 2 moedas.
        
        A quantidade máxima que podemos obter do segundo grupo é igual a F (n − 1) pela definição de F (n). Assim, temos a seguinte recorrência sujeita às condições iniciais óbvias:
        
        F(n) = max{ cn = F(n - 2), F(n - 1)}, for n > 1
        F(0) = 0, F(1) = c1.
        
        Algoritmo
        
        //Aplicar a fórmula bottom-up para encontrar a quantidade máxima de dinheiro
        //Que pode ser retirado de uma linha de moedas sem escolher duas moedas adjacentes
        //Input: Array C[1..n] de inteiros positivos indicando os valores das moedas
        //Output: A qtd máxima de dinheiro que pode ser pego
        F[0] = 0; F[1] = C[1];
        for i < 2 to n do
        F[i] = max(C[i] + F[i-2], F[i-1])
        return F[n]
        
        Resolvemos o problema dado para as i moedas da linha dada.
        
        Para encontrar as moedas com o valor total máximo encontrado, precisamos retroceder os cálculos para ver qual das duas possibilidades produziu os máximos na fórmula do algoritmo.
        
        1 more item...
    - - Coin-collecting problem
        
        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 abaixo de sua localização atual. Quando o robô visita uma célula com uma moeda, ele sempre pega aquela moeda. Projete um algoritmo para encontrar o número máximo de moedas que o robô pode coletar e um caminho que ele precisa seguir para fazer isso.
        
        Seja F (i, j) o maior número de moedas que o robô pode coletar e trazer para a célula (i, j) na i-ésima linha e j-ésima coluna do tabuleiro. Pode chegar a esta célula da célula adjacente (i - 1, j) acima dela ou da célula adjacente (i, j - 1) à esquerda dele. O maior número de moedas que podem ser trazidas para essas células são F(i − 1, j ) e F (i, j − 1), respectivamente.
        
        É claro que não há células adjacentes acima das células da primeira linha e não há células adjacentes à esquerda da linha células da primeira coluna.Então nesse caso assumimos que
        F (i − 1, j ) e F (i, j − 1) são iguais a 0 para seus inexistentes vizinhos.
        
        Portanto, o maior número de moedas que o robô pode trazer para a célula (i, j) é o máximo desses dois números mais uma moeda possível na própria célula (i, j). Como demonstrada na seguinte fórmula.
        
        F(i,j) = max{F(i-1, j) , F(i, j-1)} + cij for 1<= i <= n, 1 <= j<= m
        F(0,j) = 0 for 1<=j<=m and F(i,0) = 0 for 1<=i<=m
        
        1 more item...
        
        Algoritmo
        
        1 more item...
      - Dê o troco para o valor n usando o mínimo número de moedas de denominação d1 < d2 < . . . <dm. Para as denominações das moedas usados nos Estados Unidos, como para aqueles usados na maioria, senão em todos os outros países, há um algoritmo muito simples e eficiente discutido no próximo capítulo. Aqui, consideramos um algoritmo de programação dinâmica para o caso geral, assumindo disponibilidade de quantidades ilimitadas de moedas para cada uma das m denominações d1 < d2 < . . . < dm onde d1 = 1.
        
        Seja F(n) o número mínimo de moedas cujos valores somam n. Logo é conveniente definir F (0) = 0. A quantidade n só pode ser obtida adicionando um moeda de denominação dj no valor n − dj para j = 1, 2, . . . , m tal que n ≥ dj . Portanto, podemos considerar todas essas denominações e selecionar aquela que minimiza F (n − dj) + 1. Como 1 é uma constante, podemos, é claro, encontrar o menor F (n − dj) primeiro e depois adicione 1 a ele. Portanto, temos a seguinte recorrência para F(n):
        
        F(n) = min{F(n-dj)} + 1 for n > 0; j: n>= dj
        F(0) = 0
        
        Algoritmo
        
        // Solicitar um dynamic programming para encontrar o número mínimo de moedas de denominadores d1<d2<...<dm onde d1 = 1 que add para uma qtd dado de n
        //Input: Inteiro positivo n e array D[1..m] de um incremento de inteiro positivo indicando uma moeda denomidada onde D[1]=1
        //Output: O número mínimo de moedas que add para n
        F[0] = 0
        for i = 1 to n do
        temp = INFINITO; j = 1
        while j <= m and i>=D[j] do
        temp = min(F[i - D[j] ], temp)
        j++
        F[i] = temp + 1
        return F[n]
        
        As eficiências de tempo e espaço do algoritmo são obviamente O(nm) e (n), respectivamente.
- - - - Assumimos aqui que todos os os pesos e a capacidade da mochila são inteiros positivos; os valores dos itens não têm que ser inteiros.
  - - - Podemos dividir todos os subconjuntos dos primeiros i itens que se ajustam a mochila de capacidade j em duas categorias: aquelas que não incluem o i-ésimo item e aqueles que o fazem.
        
        1º) Entre os subconjuntos que não incluem o i-ésimo item, o valor de um ótimo subconjunto é, por definição, F (i − 1, j ).
        
        2º) Entre os subconjuntos que incluem o i-ésimo item (portanto, j − wi ≥ 0), um ótimo subconjunto é composto por este item e um subconjunto ótimo dos primeiros i − 1 itens que cabe na mochila de capacidade j − wi . O valor de tal ideal subconjunto é vi + F (i − 1, j − wi ).
        
        Assim, o valor de uma solução ótima entre todos os subconjuntos viáveis do primeiro i itens é o máximo desses dois valores. Claro, se o i-ésimo item não couber na mochila, o valor de um subconjunto ideal selecionado dos primeiros i itens é igual ao valor de um subconjunto ótimo selecionado dos primeiros i − 1 itens.
        
        Isso pode ser observado pela seguinte recurção.
        
        F(i, j) = { max{F((i - 1, j), vi + F(i-1, j-wi)} if j-wi >= 0;
        F(i-1, j) if j-wi < 0 }
        
        É conveniente definir as condições iniciais como:
        
        F(0, j) = 0 for j >= 0 and F(i, 0) = 0 for i >= 0
        
        Nossa meta é encontrar o F(n, W), o valor máximo de um subconjunto dado n itens que cabem dentro de uma mochila de capacidade W, e seja um subconjunto ideal para ele.
        
        Exemplo 01
        
        Consideremos a instância dada pelos seguintes dados:
        
        1 more item...
        
        Funções de memória
        
        A abordagem direta de cima para baixo encontrar uma solução para tal recorrência leva a um algoritmo que resolve subproblemas mais de uma vez e, portanto, é muito ineficiente (normalmente, exponencial ou pior).
        
        A abordagem clássica de programação dinâmica, por outro lado, funciona de baixo para cima: preenche uma tabela com soluções para todos os subproblemas menores, mas cada um deles eles são resolvidos apenas uma vez
        
        1 more item...
        
        Exemplo 02
        
        Vamos aplicar o método da função de memória à instância considerada no Exemplo 1. Apenas 11 dos 20 valores não triviais (ou seja, não aqueles na linha 0 ou na coluna 0) foram calculados.
        
        1 more item...
- - - - f(sa) <= cf(s^)
    - - Os algoritmos de aproximação mais simples para o problema do caixeiro viajante são baseados na técnica gananciosa. Vamos discutir dois desses algoritmos.
      - Nearest-neighbor algorithm
        
        O algoritmo ganancioso popular a seguir segue a heurística do vizinho mais próximo: em cada passo, escolha a cidade não visitada mais próxima como a próxima a ser visitada.
        
        Step 01:
        
        Step 02:
        
        Step 03:
        
        Retorne à cidade inicial.
        
        Continue repetindo a seguinte operação até que todas as cidades tenham sido visitadas: vá para a cidade não visitada mais próxima da última cidade visitada (os loops podem ser desfeitos arbitrariamente).
        
        Escolha uma cidade arbitrária como início.
        
        Exemplo 01
        
        Para a instância representada pelo gráfico da figura a seguir, com o vértice "a" como o vértice inicial, o algoritmo do vizinho mais próximo produz o passeio (circuito Hamiltoniano) como segue: a - b - c - d - a, com comprimento total de 10.
        
        A solução ótima para o problema, que pode ser encontrada por busca exaustiva, é o percurso s∗s∗ de a−b−d−c−aa−b−d−c−a com comprimento 8. Isso significa que a solução ideal é visitar as cidades nessa ordem, resultando em uma distância total de 8 unidades.
        
        Por outro lado, o algoritmo do vizinho mais próximo produz um percurso sa de a−b−c−d−a com comprimento 10. Assim, a razão de precisão dessa aproximação é r(sa)=10 / 8 = 1.25, o que significa que o percurso resultante é 25% mais longo que o ótimo.
        
        1 more item...
        
        Multifragment-heuristic algorithm
        
        Outro algoritmo ganancioso natural para o problema do caixeiro viajante trata de encontrar uma coleção de arestas de peso mínimo em um grafo completo ponderado, de modo que todos os vértices tenham grau 2. Essa abordagem, focada nas arestas em vez dos vértices, lembra o algoritmo de Kruskal para encontrar a árvore geradora mínima em um grafo.
        
        Uma aplicação da técnica gananciosa a este problema resulta no seguinte algoritmo:
        
        Step 01:
        
        Step 02:
        
        2 more items...
        
        Ordene as arestas em ordem crescente de peso. Os loops podem ser desfeitos arbitrariamente. Em seguida, inicialize o conjunto de arestas do passeio a ser construído como um conjunto vazio.
        
        Em geral, o algoritmo heurístico de multifragmentos tende a gerar passeios significativamente melhores do que o algoritmo do vizinho mais próximo. No entanto, é importante notar que a razão de desempenho do algoritmo heurístico de multifragmentos também é ilimitada.
        
        Para um subconjunto significativo de instâncias conhecido como euclidiano, podemos fazer uma afirmação não trivial sobre a precisão tanto dos algoritmos heurísticos do vizinho mais próximo quanto dos multifragmentos. Isso ocorre quando as distâncias entre as cidades satisfazem certas condições naturais, como:
        
        1 more item...
        
        Minimum-Spanning-Tree–Based Algorithms
        
        Existem algoritmos de aproximação para o problema do caixeiro viajante que exploram a relação entre circuitos Hamiltonianos e árvores geradoras no mesmo grafo. Dado que remover uma aresta de um circuito Hamiltoniano resulta em uma árvore geradora, é razoável esperar que a estrutura de uma árvore geradora mínima forneça uma base sólida para construir uma aproximação de percurso mais curto. Um algoritmo que implementa essa ideia de maneira direta é o seguinte:
        
        Twice-around-the-tree algorithm
        
        Step 01: Construa uma árvore geradora mínima do gráfico correspondente a um dado exemplo do problema do caixeiro viajante.
        
        1 more item...
        
        Exemplo 02
        
        1 more item...
        
        2º Teorema
        
        O algoritmo duas vezes ao redor da árvore é um algoritmo de 2 aproximações para o problema do caixeiro viajante com distâncias euclidianas.
        
        O Algoritmo de Christofides é uma abordagem de aproximação com uma melhor taxa de desempenho para o problema euclidiano do caixeiro viajante. Ele utiliza uma árvore geradora mínima de forma mais sofisticada do que o algoritmo duas vezes ao redor da árvore.
        
        1 more item...
- - - - Uma abordagem alternativa para problemas difíceis de otimização é resolver aproximadamente usando algoritmos rápidos, especialmente útil quando uma solução boa, mas não necessariamente ótima, é suficiente. Em situações com dados imprecisos, uma solução aproximada pode ser uma escolha sensata.
        
        heurística
        
        é uma regra de bom senso extraída da experiência e não de uma base matematicamente afirmação comprovada. Por exemplo, ir para a cidade não visitada mais próxima no mundo itinerante. O problema do vendedor é uma boa ilustração dessa noção.
        
        Se usarmos um algoritmo com saída aproximada, é importante saber a precisão dessa aproximação. Isso pode ser quantificado pelo tamanho do erro relativo da solução aproximada em relação à solução ótima real.
        
        re(sa) = ( f(sa) - f(s^) ) / f(s^)
        
        s^ é a solução exata para o problema
        
        r(sa) = f(sa) / f(s^)
        
        Chama-se de taxa de precisão usada para mensurar a medida de precisão sa.
        
        r(sa) = f(s^) / f(sa)
        
        1 more item...
        
        Definition
        
        Um algoritmo de aproximação em tempo polinomial é considerado um algoritmo de aproximação c, onde c ≥ 1, se a taxa de precisão da aproximação
        produz não excede c para qualquer instância do problema em questão:
        
        r(sa) <= c
        
        O melhor (ou seja, o menor) valor de c para o qual a desigualdade vale para todos instâncias do problema é chamada de taxa de desempenho do algoritmo e denotado RA.
        
        O índice de desempenho é a métrica principal que indica a qualidade de um algoritmo de aproximação. Desejamos que o índice se aproxime o máximo possível de 1. No entanto, algumas operações de algoritmos de aproximação podem resultar em índices de desempenho infinitamente grandes (RA = ∞). Isso não invalida necessariamente o uso desses algoritmos, mas requer um tratamento cuidadoso de suas saídas.
- - - - Podemos explorar várias abordagens gananciosas para resolver o problema da mochila. Uma delas é selecionar os itens em ordem decrescente de seus pesos; no entanto, isso pode resultar na exclusão de itens valiosos mais leves.
        
        Por outro lado, selecionar os itens em ordem decrescente de valor não garante a eficiente utilização da capacidade da mochila. Uma estratégia gananciosa que equilibra pesos e valores é calcular as razões valor-peso vi / wi para cada item e selecionar os itens em ordem decrescente dessas razões.
        
        Essa abordagem é eficaz para maximizar o valor total da mochila, conforme visto no algoritmo branch-and-bound.
      - Greedy algorithm for the discrete knapsack problem
        
        Step 01: Calcular os valor-peso dast axas ri = vi / wi, i = 1, . . ., n, para o item dado.
        
        Step 02: Classifique os itens em ordem não crescente das proporções calculadas na Etapa 1.
        
        Step 03 : Continue repetindo esta operação até que não haja mais itens na lista ordenada: se o item atual da lista puder ser acomodado na mochila, coloque-o lá e passe para o próximo item; caso contrário, simplesmente passe para o próximo item.
        
        Exemplo 5
        
        Consideremos o exemplo do problema da mochila com o capacidade da mochila 10 e as informações do item da seguinte forma:
        
        2 more items...
        
        Exemplo 6
        
        1 more item...
        
        Greedy algorithm for the continuous knapsack problem
        
        Step 01: Calcule as razões valor-peso vi /wi , i = 1, . . . , n, para os itens dado.
        
        Step 02: Classifique os itens em ordem não crescente das proporções calculadas na Etapa 1.
        
        Step 03: Continue repetindo esta operação até que a capacidade da mochila seja alcançada ou não haja mais itens na lista ordenada: se o item atual na lista puder ser completamente colocado na mochila, coloque-o e prossiga para o próximo item; caso contrário, coloque a maior fração possível do item na mochila para preenchê-la até sua capacidade máxima e pare.
        
        O algoritmo para a versão contínua do problema da mochila seleciona os itens em ordem de eficiência de aproveitamento da capacidade da mochila.
        
        1 more item...