Please enable JavaScript.

Coggle requires JavaScript to display documents.

M16 - Coggle Diagram

- - - - 1-Se P = NP, não existe algoritmo de aproximação c para o problema do caixeiro viajante, ou seja, não existe aproximação de tempo polinomial
        algoritmo para este problema de modo que para todas as instâncias
        
        Por meio de contradição, suponha que tal algoritmo de aproximação A e uma constante c existem. Seja G um grafo arbitrário
        com n vértices. Mapeamos G para um gráfico completo ponderado G atribuindo peso 1 a
        cada aresta em G e adicionando uma aresta de peso cn + 1 entre cada par de vértices nao adjacente em G
        
        Se G tem um circuito hamiltoniano, seu comprimento em G é n, portanto é a a solução exata s ∗ para o problema dovendedor viajante para G. Observe que se sa é uma solução aproximada obtida para G pelo algoritmo A, então f (sa) ≤ cn pelo suposição.
        Se G não tiver um circuito hamiltoniano em G, o caminho mais curto em
        G conterá pelo menos uma aresta de peso cn + 1 e, portanto, f (sa) ≥ f (s ∗)> cn.
      - 2-O algoritmo de duas voltas na árvore é um algoritmo de 2 aproximações para o problema do vendedor viajante com distâncias euclidianas.
        
        Obviamente, o algoritmo de duas vezes ao redor da árvore é o tempo polinomial se nós
        usar um algoritmo razoável, como Prim's ou Kruskal's na Etapa 1. Precisamos mostrar que para qualquer instância euclidiana do problema do caixeiro-viajante, a duração de um
        toursa obtidos pelo algoritmo de duas vezes ao redor da árvore tem no máximo o dobro do comprimento do tour ótimo s ∗, ou seja:
        f (sa) ≤ 2f (s∗).
        E também temos a inequação f (s∗) > w(T ) ≥ w(T∗).
    - - Se quisermos saber o quao proximo a solução aproximada é perto da real existe um indice de precisão que é;
        r(sa) = f (sa)/f (s∗)
- - - - 1 -Trees Problems
        
        1-Coin-row problem. Há uma fileira de n moedas cujos valores são alguns inteiros positivos c1, c2, ..., cn, não necessariamente distintos. O objetivo é pegar a quantidade máxima de dinheiro sujeita à restrição de que duas moedas adjacentes na linha inicial não possam ser escolhidas.
        
        Seja F (n) a quantidade máxima que pode ser obtida 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. O maior valor que podemos obter do primeiro grupo é igual a cn + F (n - 2) - o valor da enésima moeda mais a quantidade máxima que podemos coletar das primeiras n - 2 moedas.
        
        O o valor máximo que podemos obter do segundo grupo é igual a F (n - 1) pelo
        definição de F (n). Assim, temos a seguinte recorrência sujeita ao óbvio condições iniciais:
        F (n) = max{cn + F (n − 2), F (n − 1)} para n > 1,
        F (0) = 0, F(1) = c1.
        
        2-Coin-collecting problem.
        Várias moedas são colocadas nas 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 qualquer uma das células 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 essa 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 ej-ésima coluna do tabuleiro. Pode alcançar esta célula tanto da célula adjacente (i - 1, j) acima dela ou da célula adjacente (i, j - 1) à esquerda dela. 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, não há células adjacentes acima das células na primeira linha, e não há células adjacentes à esquerda do células na primeira coluna. Para essas células, assumimos que F (i - 1, j) e F (i, j - 1) são iguais a 0 para seus vizinhos inexistentes. 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 possível moeda na própria célula (i, j). Em outras palavras, temos a seguinte fórmula para F (i, j):
        F (i, j ) = max{F (i − 1, j ), F (i, j − 1)} + cij para 1 ≤ i ≤ n, 1 ≤ j ≤ m
        F (0, j) = 0 for 1 ≤ j ≤ m w F (i, 0) = 0 para 1 ≤ i ≤ n,
        
        Onde cij = 1 se houver uma moeda na célula (i, j) e cij = 0 caso contrário. Usando essas fórmulas, podemos preencher a tabela n×m de valores F(i,j) em qualquer linha por linha ou coluna por coluna, como é típico para algoritmos de programação dinâmica envolvendo tabelas bidimensionais.
      - 2- Knapsck problems and memory functions
        
        Problema da mochila: dados n itens de pesos conhecidos w1, ..., wn e valores
        v1, ..., vn e uma mochila de mochila de capacidade W, encontre o subconjunto mais valioso do
        itens que cabem na mochila
        
        Seja F (i, j) o valor de uma solução ótima para este
        exemplo, ou seja, o valor do subconjunto mais valioso dos primeiros i itens que se encaixam na mochila com capacidade j. Podemos dividir todos os subconjuntos dos primeiros i itens que se encaixam na mochila de capacidade j em duas categorias: aquelas que não incluem o i-ésimo
        item e aqueles que fazem
        
        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º item não se encaixa na mochila, o valor de um subconjunto ideal selecionado dos primeiros i itens
        é o mesmo que o valor de um subconjunto ótimo selecionado dos primeiros i - 1 itens.
        Essas observações levam à seguinte recorrência:
        F (i, j ) = max{F (i − 1, j ), vi + F (i − 1, j − wi)} se j − wi ≥ 0
        F (i, j ) = F (i − 1, j) se j − wi < 0
        
        A programação dinâmica tem um problema que é o fato de muitas vezes alguns subproblemas não serem necessários para a resolução do problema final, o que não ocorre na abordagem top-down.
        Pensando isso há o método de memory function que faz apenas os subproblemas necessários e apenas 1 vez cada
        
        Esse método resolve o problema em uma maneira top-down mas mantêm a tabela que seria usada num bottom-up em programa dinâmica. Inicialmente todos os valores são iniciados com um símbolo NULL que indica que eles não foram calculados. Após isso , sempre que um novo valor for calculo, o método checa se a entrada já estava na tabela, se a entrada for diferente de null, ela simplesmente eh recuperada da tabela, se não ela é calculada pela entrada recursiva e gravada na tabela
    - - Em vez de resolver sobrepondo subproblemas repetidas vezes, a programação dinâmica sugere a solução cada um dos subproblemas menores apenas uma vez e registrando os resultados em uma tabela de qual uma solução para o problema original pode então ser obtida.
      - Um conceito muito importante para a programação dinâmica é o de princípio da otimização. Ele
        afirma que uma solução ótima para qualquer
        instância de um problema de otimização é composta de soluções ótimas para suas subinstâncias