Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic Programming (Programação Dinâmica), Algoritmos, Algoritmos de…

- - - - Análise
        
        Particionamos todas as seleções de moedas permitidas em dois grupos
        
        Aqueles que incluem a última moeda
        
        Aqueles que não incluem a última moeda
        
        A maior quantidade 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 valor máximo que podemos obter do segundo grupo é igual a F (n - 1)
    - - F(n)=max{Cn+F(n-2),F(n-1)}
      - F(0)=0
      - F(1)=C1
      - F(n)=Quantidade máxima que pode ser obtida da linha de n moedas
    - - A informação sobre qual elemento é maior pode ser registrado em matriz extra
    - - θ(n)
        
        Eficiência temporal e espacial
        
        Muito superior a aplicação da recorrência top down e superior a resolução por pesquisa exaustiva
  - - - Número mínimo de moedas cujo valores somam n
    - - j=1,2,3,...m
    - - F(n)=min F(n-dj)+1
      - F(0)=0
    - - Temporal
        
        θ(nm)
      - Espacial
        
        θ(n)
    - - m
        
        tamanho do array de denominações
      - n
        
        montante
  - - - Um robô no canto superior esquerdo precisa coletar o máximo de moedas e trazer para a célula inferior direita
        
        Em cada etapa o robô pode mover para direita ou para baixo
        
        Quando o robô visita uma célula com moeda ele sempre pega
    - - O maior número de moedas que o robô pode coletar e trazer para a célula (i,j)
        
        Pode alcançar essa célula a partir da célula acima (i-1,j) ou à esquerda (i,j-1)
        
        Maior número de moedas para a célula à esquerda
        
        F(i-1,j)
        
        Para as células da primeira linha não tem célula acima
        
        F(i-1,j)=0
        
        Maior número de moedas para a célula acima
        
        F(i,j-1)
        
        Para as células da primeira coluna não tem célula à esquerda
        
        F(i,j-1)=0
        
        Portanto, o maior número de moedas que o robô pode trazer para a célula (i,j) é o máximo entre os 2 números mais a moeda em (i,j), se existir
        
        F(i,j)=max{F(i-1,j),F(i,j-1)}+Cij
        
        F(0,j)=0
        
        Cij
        
        1, se houver moeda em (i,j)
        
        0, se não houver moeda em (i,j)
        
        F(i,0)=0
    - - Espacial e temporal para calcular o valor de F(i,j)
        
        Θ(nm)
        
        Calcular o valor de F(i,j) é constante em todas as células
        
        Tabela n x m
    - - Se F(i-1,j) < F(i,j-1)
        
        Deve vir da célula da esquerda
      - Se F(i-1,j) = F(i,j-1)
        
        Pode vir da célula acima ou da esquerda
      - Se F(i-1,j) > F(i,j-1)
        
        Deve vir da célula de cima
      - Eficiência para achar um caminho ótimo
        
        Θ(n+m)
- - - - F(i,j)=max{F(i-1,j),vi+F(i-1,j-wi)}
      - F(0,j)=0
      - F(i,0)=0
    - - Encontrar F(n,w)
        
        Encontrar o valor máximo de um subconjunto de n itens que cabem na mochila de capacidade w e um subconjunto ideal
  - - - Valor de um subconjunto ótimo F(i-1,j)
    - - Valor de um subconjutno ótimo é composto por esse item e um subconjunto ideal dos primeiros i-1 itens que cabem na mochila de capacidade j-wi
        
        (vi+F(i-1,j-wi))
- - - - Só existe um circuito euleriano no multigrafo obtido pela duplicação de cada aresta no grafo dado
- - - - Repetir a seguinte operação até que todas as cidades tenham sido visitadas
        
        Vá para a cidade não visitada mais próxima da última visitada
    - - Retorne à cidade inicial
    - - Escolha uma cidade arbitrária como início
- - - - 3-opt
      - Lin-Kernighan
      - 2-opt
  - - - A cada iteração o algoritmo explora uma vizinhança substituindo arestas no passeio atual por outras arestas
        
        Se as alterações produzirem um passeio mais curto o algoritmo tornará o caminho atual o mais curto e continuará explorando a vizinhança
        
        Se não produzir um caminho mais curto, o passeio atual é retornado e o algoritmo para
  - - - Operação 2-change
      - Há apenas uma maneira de reconectar os terminais
        
        A exclusão forma fragmentos disjuntos
  - - - Problema do caixeiro viajante
        
        Estudo
        
        Muitas aplicações
      - Desenvolvimento de heurísticas eficazes e implementação eficiente
      - Alguns aplicativos levam a instâncias que ainda são muitos grandes para serem resolvidos em tempo razoável
      - Como saber quão boa/ruim é uma solução aproximada se não se sabe a duração de uma solução ideal?
        
        Resolver o problema de programação linear que descreve a instância em questão ignorando as restrições de integralidade
        
        Fornecimento de limite inferior
        
        Held Karp Bound
        
        Tipicamente muito próximo da duração de um passeio ideal e pode ser calculado em pouco tempo
      - Razão de precisão
        
        As instâncias assimétricas (matriz não simétricas de distâncias) são mais dificeis de resolver do que as euclidianas
        
        f(sa)/HK(s*)
        
        Uso do Held Karp Bound
        
        r(sa)=f(sa)/f(s*)
- - - - Algoritmos que analisam conjuntamente pesos e valores
        
        Uso da razão valor/peso e seleciona a ordem decrescente
    - - Etapa 2
        
        Ordene os itens de forma não crescente
      - Etapa 3
        
        Repita as seguintes operações até que nenhum item seja deixado na lista
        
        Se o item atual da lista couber na mochila coloque-o na mochila e passe para o próximo
        
        Se não, prossiga para o próximo item
      - Etapa 1
        
        Calcule as razões valor/peso para os itens
    - - Não garante que a capacidade da mochila será usada eficientemente
    - - Os itens mais pesados podem não ser os mais valiosos
    - - Basta escolher o melhor entre a abordagem obtida pelo algoritmo guloso e a que consiste de um único item de maior valor que cabe na mochila
      - Relação de desempenho deste algoritmo guloso aprimorado é 2
        
        O valor do subconjunto ótimo nunca será mais que 2 vezes maior que o valor do subconjunto sa obtido pelo algoritmo guloso aprimorado
  - - - Ordene de forma não crescente
    - - Repita o seguinte processo até que a mochila esteja totalmente cheia
        
        Se o item atual na lista cabe na mochila em sua totalidade, coloque-o e passe para o próximo
        
        Se não, pegue sua maior fração que pode encher a mochila e completamente, coloque -o na mochila e passe para o próximo
    - - Calcule as razões valor/peso
  - - - Subconjunto de maior valor é retornado
    - - θ(n)
      - O(kn^k+1)
- - - - Classifique as arestas em ordem crescente de peso
        
        Inicie o conjunto de arestas a serem construídas como conjunto vazio
    - - Repita esse passo n vezes onde n é o número de cidades da instância
        
        Adicionar a próxima aresta na lista de arestas desde que essa aresta não crie um vértice de grau 3 ou um ciclo de comprimento menor que n
        
        Se não houver essa possibilidade, pule para a próxima aresta
    - - Retorne o conjunto de arestas do passeio
- - - - d[i,j]<=d[i,k]+d[k,j]
    - - d[i,j]=d[j,i]
- - - - Comece em um vértice arbitrário e execute uma caminhada na minimum spanning tree registrando todos os vértices que passa
    - - Faça a varredura nos vértices da etapa 2 e elimine as ocorrências repetidas do mesmo vértice (exceto o vértice inicial no fim da lista)
        
        Esse último é para completar o ciclo
    - - Construa uma árvore geradora de peso mínimo do grafo correspondente a uma instância do problema
    - - Solução do problema
    - - O twice around the tree algorithm é um algoritmo 2-approximation para o problema do caixeiro viajante com distâncias euclidianas
- - - - Heurística
        
        Regra de senso comum extraído com a experiência ao invés de ser uma afirmação matematicamente comprovada
  - - - s* - solução exata
    - - Problemas de minimização
        
        r(sa)=f(sa)/f(s*)
      - Problemas de maximização
        
        r(sa)=f(s*)/f(sa)
      - Quanto mais perto de 1 melhor a aproximação
        
        Para a maioria das instâncias não se sabe a solução exata (s*)
        
        Deve-se obter um bom limite superior dos valores de r(sa)
  - - - O melhor (menor) valor de c para qual a desigualdade é válida para todas as instâncias do problema
      - Principal métrica que indica a qualidade do algoritmo de aproximação
      - Desejável algoritmos com RA mais próximo de 1
      - Algoritmos com RA infinitamente grande
        
        Não exclui os algoritmos mas exige tratamento de suas saídas
- - - - Não existe algoritmo de aproximação de tempo polinomial para este problema de modo que para todas as instâncias f(sa)<=cf(s*) para c constante
- - - - Muitas dessas resoluções não são usadas para resolver o problema total
  - - - Obter um método que resolva apenas subproblemas que são necessários e faz isso apenas uma vez
        
        Esse método existe e é baseado em memory function
        
        Resolve um problema de maneira top-down e mantém a tabela do bottom-up
        
        A tabela é inicializada com null em todas as células
        
        Se um novo valor precisa ser calculado o método verifica a tabela
        
        Se a entrada não for nula, o valor é recuperado da tabela
        
        Se a entrada for nula é calculada pela recursão e registrado na tabela
        
        Ganho em fator constante usando o método de memory function para o problema da mochila
    - - Algoritmos de programação dinâmica
        
        Cálculo de um valor leva mais que um tempo constante
        
        Menos eficiente em termos de espaço do que uma abordagem bottom up na versão mais eficiente levando em consideração o espaço