Question

O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma única vez e regressando à cidade inicial. Com essa informação, assinale a alternativa correta:


A.
O Relaxamento das Restrições remove os componentes restritivos do problema que, neste caso, é o fato de começar em uma cidade qualquer.

B.
O problema do CV é um exemplo de Algoritmo Guloso, uma vez que ele deseja passar por todas as cidades.

C.
O tempo de execução do CV é diretamente proporcional ao tempo de execução de um algoritmo de pesquisa binária, por isso ambos são conhecidos como Algoritmos Lagrangianos.

D.
Este é um problema de complexidade O(n), uma vez que a complexidade aumenta de acordo com o tamanho n de cidades.


E.
O Relaxamento das Restrições remove os componentes restritivos do problema que, neste caso, é o fato de visitar cada cidade precisamente uma única vez.

Answer 1

Resposta:

B) O problema do CV (Caixeiro-Viajante) é um exemplo de Algoritmo Guloso, uma vez que ele deseja passar por todas as cidades.

Espero ter ajudado :-)