Questão FC235918
A figura 1a apresenta um grafo cujo vértice D corresponde a um depósito, e os demais vértices correspondem a locais onde serão feitas entregas a partir desse depósito; os valores s
Tópicos de Matemática (Ensino Superior)
CESGRANRIO · 2012
A figura 1a apresenta um grafo cujo vértice D corresponde a um depósito, e os demais vértices correspondem a locais onde serão feitas entregas a partir desse depósito; os valores sobre os arcos correspondem à distância entre esses pontos. Uma rota deve ser definida partindo do depósito D, passando por todos os pontos de entrega e retornando ao depósito. Buscando minimizar a distância total a ser percorrida utilizou-se uma heurística do problema do caixeiro-viajante, que compreende a formação de “subtour e tour”, agregando um vértice a cada iteração. Numa determinada iteração chegou-se à subtour, apresentada na figura 1b, onde os vértices C2 e C3, além do depósito, já fazem parte da subtour.
Dando continuidade ao procedimento para busca da solução, deve-se, na próxima iteração, incluir na subtour o vértice:
- C4 entre os vértices C2 e D
- C4 entre os vértices D e C3
- C4 entre os vértices C3 e C2
- C1 entre os vértices D e C2
- C1 entre os vértices C2 e C3
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A escolha de inserir C4 entre C3 e C2 decorre do critério da inserção mínima usado na heurística: avalia-se, para cada arco consecutivo (i,j) da subtour, o custo incremental de incluir o vértice v como \( \Delta_{(i,j)}=d(i,v)+d(v,j)-d(i,j)\).
Calcule-se \( \Delta \) para os arcos da subtour atual (D–C3, C3–C2, C2–D). O arco cujo \( \Delta \) for o menor indica a melhor posição de inserção, pois adiciona o menor acréscimo à distância total.
No caso apresentado, o menor \( \Delta \) ocorre para o arco C3–C2; portanto, inserir C4 entre C3 e C2 resulta no menor aumento do comprimento da rota e é a escolha que preserva a otimização local da heurística.
Conteúdo do catálogo FC Concursos · Atualizado em