TSP question

 


Considering that paths with the same weights are decided in alphabetical order, select the alternative with the correct heuristic and starting vertex used to obtain the following Traveling Salesperson Problem solution:


A. Closest neighbor, starting in a.

B. Cheapest insertion, starting in a.

C. Closest neighbor, starting in b.

D. Cheapest insertion, starting in b.

E. None of the above.

Original idea by: Pedro Zaffalon.

 

Comentários

  1. Joao Meidanis2 de novembro de 2025 às 15:18

    Questão interessante, mas cheapest insertion requer um ciclo para começar.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Network Flow Question

Which of the following alternatives contains a false statement regarding network flow? a) The residual network is obtained by subtracting the flow’s edge weights from their corresponding edges in the original network. b) Residual networks obtained from maximum flows have no augmenting path. c) To push flow into an edge, the original vertex needs to have excess flow and the same height as the destination vertex. d) The sum of the weights of all edges of a single vertex in a flow is always zero, except for the source and the sink. e) None of the above. Original idea by: Pedro Zaffalon da Silva
Leia mais

BFS Question

Imagem
A BFS was performed on an unknown graph, producing the following visitation order: a-c-d-b-f-g-e-h There are four candidate graphs: I) II) III) IV)  Assuming that neighbors are always visited in  ascending order , which of the graphs are valid candidates for the original graph? a) I and II b) I and III b) II and IV d)  III and IV e) None of the above Original idea by: Pedro Zaffalon da Silva
Leia mais
Imagem
Which of the following alternatives contains a graph with only one Strongly Connected Component (SCC)?  a) b) c)  d)   e) None of the above Original idea by: Pedro Zaffalon da Silva  
Leia mais