Hey there! Sign in to join this conversationNew here? Join for free

Decision Maths help: Tour Improvement & Lower and Upper Bounds. Watch

    • Thread Starter
    Offline

    0
    ReputationRep:
    Hey..
    I have my D1 exam tomorrow and I'm having some problems

    So basically, I was wondering if anyone could tell me how to do the tour improvement algorithm and lower and upper bounds for graphs..

    thank you!
    Offline

    1
    ReputationRep:
    Basically i dont think that you need to learn the tour improvement algorithm but can recognise from the graph any shortcuts that you need to take by inspection.

    Upper bound = nearest neighbour
    lower bound = delete a node and then construct a minimum spanning tree using either prim or kruskal. then add the weights of the 2 shortest arcs connecting to the node.

    The best upper bound is the lowest value
    The best lower bound is the highest value
    Offline

    0
    ReputationRep:
    (Original post by crazy4it2007)
    Basically i dont think that you need to learn the tour improvement algorithm but can recognise from the graph any shortcuts that you need to take by inspection.

    Upper bound = nearest neighbour
    lower bound = delete a node and then construct a minimum spanning tree using either prim or kruskal. then add the weights of the 2 shortest arcs connecting to the node.

    The best upper bound is the lowest value
    The best lower bound is the highest value
    please tell me you are not talking 'bout MEI D1 would you.cuz i have no idea what this is
    Offline

    1
    ReputationRep:
    no, OCR
    Offline

    0
    ReputationRep:
    to do the lower bound:

    take your starting node and find the two smallest arcs coming out of it.
    eliminate this node and all of the arcs coming from it from the larger network
    then using either prims of kruskals algorithm find a minimum connector/spanning tree for the remaining network of nodes.
    Add this value for the minimum spanning tree to the value of the two arcs coming from your starting node.
    This value will be the lower bound.
    (note not all lower bounds are attainable, the actual optimal solution for this problem will lie between the lower and upper bounds. The upper bound is aquired by applying the nearest neighbour method)

    A logical way to improve the tour would be too eliminate the starting node from the network in the same way you did to find the lower bound. To get a good solution you would need to find the two smallest arcs coming from the starting node (the one you eliminated) and then see which nodes these arcs are connected to. This will tell you the two nodes where you will have to start and end up when you are going round your ''new'' network. (by new i mean the network now that the starting node has been eliminated).
    Now that you know a start and end point for your ''new'' network you can try to find the shortest path, by comparing possible paths to the one you found using the nearest neighbour it should make it easier to find an optimal solution. However this optimal may rely on the arcs you eliminated when you eliminated when your starting node. Make sure therefore that large arc weights are not skewing your results
    • Thread Starter
    Offline

    0
    ReputationRep:
    Thank you guys !

    The exam was okayish... and they did ask for lower and upper bounds, so thankyeeeee
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you rather give up salt or pepper?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Write a reply...
    Reply
    Hide
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.