The Student Room Group

D2: How does the triangle inequality apply to salesman problem?

(D2 Edexcel 2008 spec)
In the Pearson textbook for D2 I read the following:
"To create a complete network of least distances you ensure that the triangle inequality holds for all triangles in the network. (...) If you have a network where the triangle inequality does not hold in one or more triangles you simply replace the longest arc in those triangles by the sum of the two smaller ones, thereby creating a network which shows the shortest distances."

(The triangle inequality is then never mentioned again throughout the book)
I am aware of the triangle inequality and believe I understand it and can apply it properly, but I just don't see how the triangle ineq. applies to the salesman problem. Could someone explain to me, plainly expressed, what their point is/what are they getting at and what 'they' want me to do.
Original post by bluenotewitt
(D2 Edexcel 2008 spec)
In the Pearson textbook for D2 I read the following:
"To create a complete network of least distances you ensure that the triangle inequality holds for all triangles in the network. (...) If you have a network where the triangle inequality does not hold in one or more triangles you simply replace the longest arc in those triangles by the sum of the two smaller ones, thereby creating a network which shows the shortest distances."

(The triangle inequality is then never mentioned again throughout the book)
I am aware of the triangle inequality and believe I understand it and can apply it properly, but I just don't see how the triangle ineq. applies to the salesman problem. Could someone explain to me, plainly expressed, what their point is/what are they getting at and what 'they' want me to do.


Never seen it arise in any D2 question posted on here. But:

The triangle inequality in this instance is saying the direct route is to be the shortest route.

An example where you might need to apply it is if you have two towns (A,B) on opposite sides of a mountain. The direct route over the mountain will generally take longer, than going via a third town (C) at the side of the mountain. So, we'd replace the weight of arc AB, with the sum of the weights of arcs AC and CB.
In attached, 20 is replace by 5+4 = 9.
Untitled.jpg
(edited 6 years ago)
Original post by ghostwalker
Never seen it arise in any D2 question posted on here. But:

The triangle inequality in this instance is saying the direct route is to be the shortest route.

An example where you might need to apply it is if you have two towns (A,B) on opposite sides of a mountain. The direct route over the mountain will generally take longer, than going via a third town (C) at the side of the mountain. So, we'd replace the weight of arc AB, with the sum of the weights of arcs AC and CB.
In attached, 20 is replace by 5+4 = 9.
Untitled.jpg

OK, thank you! I think I understand it a little better now. But I still have some questions: What happens if one doesn't use the triangle inequality, when constructing the table of least differences? (less related) Does the table of least differences only record the direct link from one vertex to another?
(If the table of least differences only records direct links, then I can see how the triangle inequality comes into play, but else I just don't see the point in it).
Thank you so far!
Original post by bluenotewitt
OK, thank you! I think I understand it a little better now. But I still have some questions: What happens if one doesn't use the triangle inequality, when constructing the table of least differences? (less related) Does the table of least differences only record the direct link from one vertex to another?
(If the table of least differences only records direct links, then I can see how the triangle inequality comes into play, but else I just don't see the point in it).
Thank you so far!


'Fraid I'm not going to be much help on these, and had to dig around a bit through my various OR books, and then some.

Near as I can tell:

The "triangle inequality" is a version of the Cauchy-Schwartz inequality (uni. level maths, well STEP anyway). Data conforming to it, has properties that are required for some (if not all) of the various algorithms. And it is part of the theoretical basis of those algorithms.

As to the "table of least distances". There are two possible interpretations that I'm aware of:
a) It represents the direct arcs, and so isn't necessarily complete.
b) Or it represents least distances for all possible pairings.

That doesn't really help you I know - It's going to depend on how your book defines it.

Someone more familiar with the actual syllabus may be able to assist further.
(edited 6 years ago)
Original post by ghostwalker
'Fraid I'm not going to be much help on these, and had to dig around a bit through my various OR books, and then some.

Near as I can tell:

The "triangle inequality" is a version of the Cauchy-Schwartz inequality (uni. level maths, well STEP anyway). Data conforming to it, has properties that are required for some (if not all) of the various algorithms. And it is part of the theoretical basis of those algorithms.

As to the "table of least distances". There are two possible interpretations that I'm aware of:
a) It represents the direct arcs, and so isn't necessarily complete.
b) Or it represents least distances for all possible pairings.

That doesn't really help you I know - It's going to depend on how your book defines it.

Someone more familiar with the actual syllabus may be able to assist further.


Thank you very much for your help and efforts once again. I think I understand now what is going on a lot better, even if I don't understand it completely. I very much doubt that it will come up in an A-level anyway, so I guess I'm OK, just wanted to make sure....
P.S. I would rate you for both your posts, but apparently I have to rate some other member first...

Quick Reply

Latest