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

Watch
Announcements
#1
(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.
0
3 years ago
#2
(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.
0
#3
(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.
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!
0
3 years ago
#4
(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.
0
#5
(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...
1
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### Poll

Join the discussion

#### What support do you need with your UCAS application?

I need help researching unis (27)
13.3%
I need help researching courses (13)
6.4%
I need help with filling out the application form (9)
4.43%
I need help with my personal statement (85)
41.87%
I need help with understanding how to make my application stand out (51)
25.12%
I need help with something else (let us know in the thread!) (3)
1.48%
I'm feeling confident about my application and don't need any help at the moment (15)
7.39%