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

Watch
bluenotewitt
Badges: 11
Rep:
?
#1
Report Thread starter 3 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 17
#2
Report 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.
Name:  Untitled.jpg
Views: 89
Size:  26.8 KB
0
reply
bluenotewitt
Badges: 11
Rep:
?
#3
Report Thread starter 3 years ago
#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.
Name:  Untitled.jpg
Views: 89
Size:  26.8 KB
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
reply
ghostwalker
  • Study Helper
Badges: 17
#4
Report 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
reply
bluenotewitt
Badges: 11
Rep:
?
#5
Report Thread starter 3 years ago
#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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

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.

Personalise

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%

Watched Threads

View All