Pergunta

In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance.

I understand how MTZ works, but I'm confused why MTZ is considered a better algorithm for checking for sub-cycles and rejecting them as answers than just keeping a list of connected nodes.

I can imagine a look-up table of each node along with a corresponding boolean that defines whether a node is connected or not. Consequently, the running time of checking if a connection is valid would be O(1). If it isn't a run-time consideration, what is the reason that MTZ is preferred?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top