OCR D1 - I don't get upper and lower bounds

if you can get a copy of the jan05 d1 paper, i can help you. i assume you have the paper tomo morning as do i but its hard to explain without the paper in front of you, x

OMG I have the same problem! I just don't get them!

I'm just having a go through Jan 2009 OCR (which I don't actually have the mark scheme for, does anyone know where I could get a copy because there is none on the OCR site?), and on question 3 I managed to find an upper bound which was smaller than the lower bound I found >.<

Pm me your email, I got all the mark schemes for OCR maths exams

do you have the mark scheme for the specimen paper? xx

The travelling salesman problem
Basically this is used when the network is too big to work out the exact minimum cycle.

If it asks for the upper bound, you'd use the nearest neighbour algorithm:

You start at one node and you go to the next nearest node which you have not been visited yet. Go to the next nearest node, and the next nearest, etc after you've visited all the nodes you go back to the original node that you started on to form a hamiltonian cycle.

The sum of all these arcs / weights / lengths is the upper bound of the 'best' cycle in a network.

If it asks for the lower bound, you'd use the lower bound algorithm ( creative name!), or Modified Prim's. [Same thing]

Lower bound is the shortest length (which may or may not exist) you can go aorund a network.
a) Remove any node, X, from your network and any arcs connected to it,
b) Acquire the minimum spanning tree (use prim's method here)
c) Connect the 2 smallest arcs from X and add it to your minimum spanning tree.
The sum of all these arcs will be your lower bound.

So basically your optimum route will be [</]
Lower Bound </= Optomum Route </= Upper Bound

Not sure if that helps... i suck at explaining

Thankyou very much Andylol
You are a life saver!