Please enable JavaScript.

Coggle requires JavaScript to display documents.

M17 - Coggle Diagram

- - - - Algoritmo de Aproximação de 2-Approximation (para TSP com distâncias que satisfazem a desigualdade triangular)
      - Passo 1: Calcular a árvore geradora mínima (MST) do conjunto de cidades.
      - Passo 2: Fazer um passeio pré-ordem na MST, visitando cada cidade.
      - Passo 3: Ajustar o passeio para garantir que cada cidade seja visitada exatamente uma vez.
      - Garantia de Aproximação: A solução obtida é no máximo duas vezes a solução ótima.
- - - - Passo 1: Calcular a relação valor/peso (vi/wi) para cada item.
      - Passo 2: Ordenar os itens com base nessa relação de forma decrescente.
      - Passo 3: Adicionar itens à mochila na ordem dessa relação até que a capacidade seja atingida.
      - Garantia de Aproximação: Este algoritmo pode não garantir uma aproximação específica, mas é simples e rápido de implementar.