You are Here: Home >< Maths

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

1. 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!
2. 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
3. (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
4. no, OCR
5. 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
6. Thank you guys !

The exam was okayish... and they did ask for lower and upper bounds, so thankyeeeee

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 25, 2010
Today on TSR

### He lied about his age

Thought he was 19... really he's 14

### University open days

Wed, 25 Jul '18
2. University of Buckingham
Wed, 25 Jul '18
3. Bournemouth University
Wed, 1 Aug '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams