1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.
  2. Hi Guest, welcome to the TES Community!

    Connect with like-minded education professionals and have your say on the issues that matter to you.

    Don't forget to look at the how to guide.

    Dismiss Notice

Help please - Travelling salesperson lower bound

Discussion in 'Mathematics' started by Informant, Dec 14, 2011.

  1. Informant

    Informant New commenter

    AQA D1 paper (June 2006 5a)
    Gill is solving a travelling salesperson problem. Write down the best upper bound chosen from 7.5, 8, 7, 7.5, 8.5 (it's 7 and I agree)
    Now which is the best lower bound chosen from 6.5, 7, 6.5, 5, 7 ? They say 7, but why not the smallest value of 5?
    Also, although I haven't had this question from a student yet, when applying lower bound algorithm and finding minimum connector for network with two edges removed, does this have to create a tour allowing start and finish vertex to coincide, or is a minimum spanning tree (which does not) permissible to obtain this theoretical minimum value. Textbook suggests the latter.
    Any advice/wisdom appreciated thanks.
  2. Imagine Lower bound value / solution / upper bound value
    5, 6.5, 7 / solution / 7, 7.5, 8, 8.5
    the closest lower bound to the solution is 7. As this case has 7 as the best upper bound the solution value will be 7. Other wise it is stated as L<= solution <= U.
    The lower bound is defined as the lowest possible value for a tour, but the tour may not exist.
    You don't have to find a tour for the lower bound just the minimum spanning trees. and then the highest value of (MST + 2 sides).
    Imagine a cycle ABCDE is possible. If vertex A is removed BCDE may or may not be a MST, so weight of BCDE >= weight MST
    weigth of AB + AE >= sum of the weights of the two shortest edges at A
    So BCDE + AB + AE (which is our required solution) >= MST + sum of two removed edges.
    This must work for whichever vertex is removed so we must look for the largest value of (MST + edges).
    The algorithm is just finding a value that the solution will not be less than, it is not necessarily going to find a value that corresponds to a tour.
    Its a difficult concept to explain - hope this goes some way to making it clearer. I found that drawing diagrams helped.

Share This Page