Define the travelling salesman problem .

The travelling salesman problem is to find a route of minimum length that visits every vertex in an undirected network. The route is a tour , so it returns to the vertex it started from.

What is the difference between the classical and the practical travelling salesman problem?

In the classical problem each vertex is visited exactly once . In the practical problem a vertex may be revisited , so each one is visited at least once.

Why is the travelling salesman problem tackled with bounds rather than solved directly?

There is no efficient algorithm guaranteed to find the optimal tour. Instead an upper and a lower bound are found, and the optimal solution must lie somewhere between them.

True or False? If the upper and lower bounds are equal, the optimal solution has been found.

True. The optimal tour must lie between the two bounds, so if they meet there is only one value left for it to take. That is the standard way of showing that a route really is optimal.

Define a table of least distances .

A table of least distances gives the shortest distance between every pair of vertices, which is not always the direct route. It makes the network complete , so it is guaranteed to contain a Hamiltonian cycle.

What does a table of least distances do to a travelling salesman problem?

A table of least distances turns a practical problem into a classical one. Because every pair of vertices now has a direct entry, a tour can visit each vertex exactly once without needing to pass back through another.

How is a table of least distances constructed?

Take each vertex in turn, entering the distance to every adjacent vertex and checking that the direct route really is the shortest one. Then fill in the non-adjacent pairs with their shortest routes, and copy each finished row down its matching column, since the table is symmetrical.

How is an initial upper bound reduced?

Find a shortcut , replacing a repeated pathway through the tree with a single edge that is not in the tree. Subtract the weight of the pathway and add the weight of the shortcut, so a pathway of 30 replaced by an edge of 14 saves 16.

Which algorithm finds the minimum spanning tree when you are looking for an upper bound?

Use Prim's algorithm where the information comes as a table of least distances. Use Kruskal's algorithm where you have only the graph itself.

What are the steps of the deleted vertex method for a lower bound?

Remove one vertex and all of its edges, then find the residual minimum spanning tree of what is left. Add to its weight the two shortest edges that reconnect the deleted vertex, and that total is a lower bound.

Why are exactly two edges added back to the residual minimum spanning tree?

Because a tour must enter the deleted vertex once and leave it once, so two edges are needed. The two shortest such edges are used, since a lower bound must never exceed the true optimum.

How do you find the best lower bound?

Repeat the deleted vertex method for every vertex in turn and take the largest result. The largest is the best, because a higher lower bound narrows the interval the optimal tour must lie in.

What are the steps of the nearest neighbour algorithm?

From the current vertex, always move along the shortest edge to an unvisited vertex , repeating until every vertex has been visited. Then add one final edge back to the starting vertex to close the tour.

True or False? The nearest neighbour algorithm produces a lower bound for the travelling salesman problem.

False. It produces a Hamiltonian cycle that genuinely exists, so its weight is an upper bound. Running it from every vertex in turn and taking the smallest result gives the best upper bound.

How does the nearest neighbour algorithm differ from Prim's algorithm?

Nearest neighbour always moves on from the current vertex, taking the shortest edge from where it stands. Prim's algorithm takes the shortest edge from any vertex already in the tree, and it builds a tree rather than a tour.

What must be true of a network before the nearest neighbour algorithm can be used?

The network must be complete and must satisfy the triangle inequality . Where it is not, a table of least distances has to be found first.

What is the only method guaranteed to solve the travelling salesman problem?

The only guaranteed method is to list every Hamiltonian cycle and take the one of least weight. No efficient algorithm is known that is certain to find the shortest cycle, so this works only on very small networks.

Why is listing every Hamiltonian cycle impractical for larger networks?

The number of routes grows extremely quickly: from a fixed starting vertex, a complete network with 4 vertices gives 6 routes, one with 5 gives 24, and one with 6 gives 120. Each extra vertex multiplies the count again, so the method very soon becomes unusable.

You are told the lower bound is 53 and asked to show it is optimal. What do you do?

Find an actual Hamiltonian cycle whose total weight is also 53. Producing a real route that attains the lower bound proves that nothing shorter exists, without having to check every cycle.

What is the difference between the travelling salesman and route inspection problems?

The travelling salesman must visit every vertex , like a salesman selling at each destination. The route inspection problem requires every edge to be travelled, like a postman walking along every road.

True or False? The travelling salesman problem can be solved by finding a minimum spanning tree.

False. A minimum spanning tree connects every vertex but is not a tour : it does not return to the start and is not a cycle at all. The spanning tree is used to build bounds for the problem, not to solve it.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsThe Travelling Salesman Problem

The Travelling Salesman Problem (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/23

0Still learning

Know0

FrontThe Travelling Salesman Problem
Define the travelling salesman problem.

Was this flashcard helpful?

Cards in this collection (23)

Define the travelling salesman problem.
The travelling salesman problem is to find a route of minimum length that visits every vertex in an undirected network.
The route is a tour, so it returns to the vertex it started from.
What is the difference between the classical and the practical travelling salesman problem?
In the classical problem each vertex is visited exactly once.
In the practical problem a vertex may be revisited, so each one is visited at least once.
Why is the travelling salesman problem tackled with bounds rather than solved directly?
There is no efficient algorithm guaranteed to find the optimal tour.
Instead an upper and a lower bound are found, and the optimal solution must lie somewhere between them.
True or False?
If the upper and lower bounds are equal, the optimal solution has been found.
True.
The optimal tour must lie between the two bounds, so if they meet there is only one value left for it to take.
That is the standard way of showing that a route really is optimal.
Define a table of least distances.
A table of least distances gives the shortest distance between every pair of vertices, which is not always the direct route.
It makes the network complete, so it is guaranteed to contain a Hamiltonian cycle.
What does a table of least distances do to a travelling salesman problem?
A table of least distances turns a practical problem into a classical one.
Because every pair of vertices now has a direct entry, a tour can visit each vertex exactly once without needing to pass back through another.
Complete the triangle inequality for three vertices, where $A B$ is a longest length:
$A B \leq A C +______$
The completed inequality is:
$A B \leq A C + C B$
Every entry in a table of least distances satisfies it, which is what guarantees that going directly is never longer than going via another vertex.
How is a table of least distances constructed?
Take each vertex in turn, entering the distance to every adjacent vertex and checking that the direct route really is the shortest one.
Then fill in the non-adjacent pairs with their shortest routes, and copy each finished row down its matching column, since the table is symmetrical.
Complete the initial upper bound found from a minimum connector:
$initial upper bound =______\times weight of the minimum spanning tree$
The completed result is:
$initial upper bound = 2 \times weight of the minimum spanning tree$
Doubling every edge guarantees a closed walk that reaches every vertex and returns to the start, which is why it is certainly an upper bound.
How is an initial upper bound reduced?
Find a shortcut, replacing a repeated pathway through the tree with a single edge that is not in the tree.
Subtract the weight of the pathway and add the weight of the shortcut, so a pathway of 30 replaced by an edge of 14 saves 16.
Which algorithm finds the minimum spanning tree when you are looking for an upper bound?
Use Prim's algorithm where the information comes as a table of least distances.
Use Kruskal's algorithm where you have only the graph itself.
What are the steps of the deleted vertex method for a lower bound?
Remove one vertex and all of its edges, then find the residual minimum spanning tree of what is left.
Add to its weight the two shortest edges that reconnect the deleted vertex, and that total is a lower bound.
Why are exactly two edges added back to the residual minimum spanning tree?
Because a tour must enter the deleted vertex once and leave it once, so two edges are needed.
The two shortest such edges are used, since a lower bound must never exceed the true optimum.
How do you find the best lower bound?
Repeat the deleted vertex method for every vertex in turn and take the largest result.
The largest is the best, because a higher lower bound narrows the interval the optimal tour must lie in.
What are the steps of the nearest neighbour algorithm?
From the current vertex, always move along the shortest edge to an unvisited vertex, repeating until every vertex has been visited.
Then add one final edge back to the starting vertex to close the tour.
True or False?
The nearest neighbour algorithm produces a lower bound for the travelling salesman problem.
False.
It produces a Hamiltonian cycle that genuinely exists, so its weight is an upper bound.
Running it from every vertex in turn and taking the smallest result gives the best upper bound.
How does the nearest neighbour algorithm differ from Prim's algorithm?
Nearest neighbour always moves on from the current vertex, taking the shortest edge from where it stands.
Prim's algorithm takes the shortest edge from any vertex already in the tree, and it builds a tree rather than a tour.
What must be true of a network before the nearest neighbour algorithm can be used?
The network must be complete and must satisfy the triangle inequality.
Where it is not, a table of least distances has to be found first.
What is the only method guaranteed to solve the travelling salesman problem?
The only guaranteed method is to list every Hamiltonian cycle and take the one of least weight.
No efficient algorithm is known that is certain to find the shortest cycle, so this works only on very small networks.
Why is listing every Hamiltonian cycle impractical for larger networks?
The number of routes grows extremely quickly: from a fixed starting vertex, a complete network with 4 vertices gives 6 routes, one with 5 gives 24, and one with 6 gives 120.
Each extra vertex multiplies the count again, so the method very soon becomes unusable.
You are told the lower bound is 53 and asked to show it is optimal. What do you do?
Find an actual Hamiltonian cycle whose total weight is also 53.
Producing a real route that attains the lower bound proves that nothing shorter exists, without having to check every cycle.
What is the difference between the travelling salesman and route inspection problems?
The travelling salesman must visit every vertex, like a salesman selling at each destination.
The route inspection problem requires every edge to be travelled, like a postman walking along every road.
True or False?
The travelling salesman problem can be solved by finding a minimum spanning tree.
False.
A minimum spanning tree connects every vertex but is not a tour: it does not return to the start and is not a cycle at all.
The spanning tree is used to build bounds for the problem, not to solve it.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:The Route Inspection AlgorithmNext:Critical Path Analysis