Cálculo do tempo necessário para visitar cidades interligadas

Descrição do Exercício:

João mora na cidade e precisa visitar cinco clientes,
localizados em cidades diferentes da sua. Cada trajeto
possível pode ser representado por uma sequência de
letras. Por exemplo, o trajeto ABCDEFA, informa que ele
sairá da cidade , visitando as cidades e
nesta ordem, voltando para a cidade A. Além disso, o
número indicado entre as letras informa o custo do
deslocamento entre as cidades. A Figura do Enunciado mostra o custo de
deslocamento entre cada uma das cidades.
Como João quer economizar, ele precisa determinar qual o
trajeto de menor custo para visitar os cinco clientes.
Examinando a figura, percebe que precisa considerar
somente parte das sequências, pois os trajetos e
têm o mesmo custo. Ele gasta para
examinar uma sequência e descartar sua simétrica, conforme
apresentado.
O tempo mínimo necessário para Joao verificar todas as
sequências possíveis no problema é de:
A)
B)
C)
D)
E)

Figura do Enunciado
1

Conforme a Figura do Enunciado, a cidade tem conexão com todas as outras cidades (assim como cada uma das outras cidades).

2

Portanto basta calcular todos os anagramas de (observe que o ponto de partida é giaul ao ponto final). O número total de possibilidades de visitar cada uma das cidades é .

3

Como João não precisa calcular o preço do deslocamento do caminho simétrico, o cálculo deve ser feito com .

4

Temos que , logo João demorará para analisar todas as possibilidades.

5

A Resposta é a letra .

enviado por Carlos Humberto de Oliveira em

quanto isto lhe ajudou ?