Sobre o tema
O problema de encontrar o trajeto mais curto para visitar um conjunto de cidades é um exemplo clássico do Problema do Caixeiro Viajante (PCV). Na questão, João precisa visitar cinco clientes partindo e retornando à cidade A, totalizando 7 letras no trajeto. As cidades intermediárias (B, C, D, E, F) podem ser visitadas em qualquer ordem, gerando permutações. Como trajetos simétricos (como ABCDEF e AFEDCBA) têm o mesmo custo, eles são considerados equivalentes, reduzindo pela metade o número de sequências a analisar. A determinação do tempo mínimo para verificar todas as possibilidades envolve o cálculo do número de permutações de 5 cidades (5! = 120) e a divisão por 2 devido à simetria, resultando em 60 sequências. Cada sequência leva 1min30s para ser examinada, totalizando 90 minutos.
Tópicos relacionados
- Permutações simples em matemática
- Problema do Caixeiro Viajante
- Simetria em trajetos
- Cálculo de fatorial (5!)
- Otimização de rotas
Enunciado
João mora na cidade A e precisa visitar cinco clientes, localizados em cidades diferentes da sua. Cada trajeto possível pode ser representado por uma sequência de 7 letras. Por exemplo, o trajeto ABCDEFA, informa que ele sairá da cidade A, visitando as cidades B, C, D, E e F 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 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. somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo. Ele gasta 1min30s para examinar uma sequência e descartar sua simétrica, conforme apresentado.
O tempo mínimo necessário para João verificar todas as sequências possíveis no problema é de
Alternativas
- A)
60 min.
- B)
90 min.
- C)
120 min.
- D)
180 min.
- E)
360 min.
Avaliar: +1 XP. Favoritar: salva pra revisar. Comentar: +5 XP + 1 credito IA.
Comentarios (0)
Carregando comentarios...
Perguntas frequentes
O que é uma permutação simples?
Permutação simples é o número de maneiras de ordenar um conjunto de elementos distintos. Por exemplo, com 5 objetos, o número de ordens possíveis é 5! (5 fatorial), que é 5 × 4 × 3 × 2 × 1 = 120.
Por que trajetos simétricos têm o mesmo custo?
No contexto de rotas de ida e volta entre cidades, o custo de ir de uma cidade a outra é geralmente o mesmo independente da direção. Assim, um trajeto e seu reverso (ordem inversa) percorrem as mesmas arestas, resultando em custo total igual.
O que é o Problema do Caixeiro Viajante?
É um problema de otimização que busca encontrar a rota mais curta que visita um conjunto de cidades exatamente uma vez e retorna à cidade de origem. É um problema NP-difícil, mas para um número pequeno de cidades, pode ser resolvido por enumeração.