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

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

(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.

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

Report

#2

(Original post by

(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.

**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.

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

reply

(Original post by

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.

**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.

(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

Report

#4

(Original post by

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!

**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!

**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

(Original post by

'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.

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

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.

**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.

P.S. I would rate you for both your posts, but apparently I have to rate some other member first...

1

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top