Question

O problema do caixeiro viajante consiste em partir de uma origem (ponto 0), passar por todas as cidades de uma rota e voltar ao ponto 0 com a menor distância percorrida possível. Para tanto, é óbvio que se devem evitar repetições (passar mais de uma vez na mesma cidade). Um caminhão de entregas deve sair do ponto 0, passar pelas cidades 1, 2 e 3 (não necessariamente nesta ordem) e voltar à cidade 0. Ele deve percorrer a menor distância possível. As distâncias estão expressas na figura a seguir em quilômetros.


Dinam2


Fonte: Nogueira,2018.


A rota ótima a ser seguida pelo caminhão será:


Alternativas:


a)

0 — 3 — 2 — 1 — 0.


b)

0 — 2 — 1 — 3 — 0.


c)

0 — 3 — 1 — 2 — 0.


d)

0 — 2 — 3 — 1 — 0.


e)

0 — 1 — 2 — 3 — 0.

Answer 1

a)

0 — 3 — 2 — 1 — 0  = 150+70+80+100 =400

b)

0 — 2 — 1 — 3 — 0 = 90+80+80+150= 400

c)

0 — 3 — 1 — 2 — 0= 150+80+80+90=400

d)

0 — 2 — 3 — 1 — 0 = 90+70+80+100=340

e)

0 — 1 — 2 — 3 — 0 = 100+80+70+150 = 400

Letra D tem a rota a ser seguida

Answer 2

Resposta:

d)

0 — 2 — 3 — 1 — 0.

Explicação passo a passo: