Caixeiro Viajante

Caixeiro Viajante
Um caixeiro viajante deve seguir por um determinado número de cidades para vender seus produtos. O problema consiste em qual ordem o caixeiro deve seguir para percorrer a menor distância possível. Uma solução seria listar as cidades e fazer uma combinação de todas as possibilidades, para encontrar o caminho mais curto. Vamos supor que o caixeiro deve viajar por 26 cidades, se demorássemos apenas um segundo para calcular a distância de cada uma das possibilidades, demoraria cerca de 1 bilhão de vezes a idade do universo para chegar a resposta exata para o problema.
Por que é impossível chegar em uma resposta?
Calcular o número de rotas é fácil, o difícil seria comparar todas as possibilidades para descobrir qual é o menor percurso. Retomando o exemplo anterior, para calcular o número de rotas, basta calcular o fatorial do número de cidades.
26! = 403.291.461.126.605.635.584.000.000
E se demorasse 1 segundo para calcular cada rota, o tempo total seria de 13 setilhões de anos, que equivale a 1 bilhão de vezes a idade do universo que é de aproximadamente 13 bilhões de anos

Problema da Mochila

Um viajante deve levar consigo, apenas uma mochila. Essa mochila possui uma capacidade de peso limitado e deve ser carregada apenas com objetos que serão úteis durante a viagem sem ultrapassar o limite. Cada objeto é único e possui um peso e um determinado valor. Que objetos dever ser levados pelo viajante de forma a maximizar o valor da mochila?

O problema é que há uma quantidade limitada para cada tipo de item.

A formula Matemática:

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS
Curso de Engenharia Mecânica com ênfase em Mecatrônica

Rafael Aguiar
Tiago Pessotti
Victor Resende

EXERCÍCIOS DE PROGRAMAÇÃO

Belo Horizonte
2014