Year 12s: what will be the first way you research your future options? >>

Travelling Salesman Problem

Hi everyone,

I need help with the thought process behind finding lower bounds in the TSP. When finding the lower bound why do we bother to cut off one vertex and then apply Prim instead of just applying Prim to the whole thing? Surely that would also find a lower bound that satisfies the problem of finding a lower bound that connects all the vertices?

Thanks.

Reply 1

Sayonara

Because using Prim's algorithm on the whole network always provides a lower "lower bound" than the best method (cutting off one vertex and then applying Prim and then adding the two shortest edges).

A higher lower bound is the best lower bound to use.

Hope this explains it all.

(edited 11 years ago)

Reply 2

Malabarista

Original post by AlanDu

Thanks, I see why the higher lower bound is always best to use but why does that method provide a higher lower bound?

Reply 3

Sayonara

Original post by Malabarista

Thanks, I see why the higher lower bound is always best to use but why does that method provide a higher lower bound?

Because using the better method always uses more than one edge than the minimum spanning tree while connecting to every vertex, therefore it will always be bigger than the minimum spanning tree.

Reply 4

Malabarista

Original post by AlanDu

Because using the better method always uses more than one edge than the minimum spanning tree while connecting to every vertex, therefore it will always be bigger than the minimum spanning tree.

Thanks very much, this has helped a lot, I think I get it.

Reply 5

Malabarista

Original post by AlanDu

Actually, one more question: Why, when we apply the method of deleting a vertex to all the vertices do we choose the highest of these, could the lowest of these not yield a feasible solution?