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 and returns to where it started. Such a route is called a tour .

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

In the classical problem each vertex is visited exactly once before returning to the start. In the practical problem each vertex must be visited at least once , so a vertex may be passed through again on the way.

True or False? In the travelling salesman problem, a tour is allowed to visit the same vertex more than once.

True. A tour is a walk that visits every vertex and returns to its start, and a walk may pass through a vertex again. A tour that visits every vertex other than the start exactly once is a Hamiltonian cycle , which is the special case the classical problem asks for.

What is a table of least distances ?

A table of least distances gives the shortest distance between every pair of vertices in a network, which is not always the direct edge joining them. It describes a complete network in table form.

Why is a table of least distances worth constructing for a travelling salesman problem?

Because it turns the practical problem into the classical one. The table describes a complete network, and a complete network always contains a Hamiltonian cycle, so every vertex can then be visited exactly once.

You are filling in a row of a table of least distances. What must you check about each direct connection?

Check whether the direct edge really is the shortest route between that pair of vertices, since going round through others is sometimes quicker. Where it is not, the shorter total is the value that belongs in the cell.

Once a row of a table of least distances is complete, what can you fill in straight away?

The matching column for that same vertex, by copying the row's values down it. A complete network is undirected, so the table is symmetrical about its leading diagonal.

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

Because there is no efficient algorithm that always finds the optimal solution. Instead an upper and a lower bound are found, and the optimal route is known to lie somewhere between them.

How do you find an initial upper bound for a travelling salesman problem from a minimum spanning tree?

Find a minimum spanning tree for the network, then double its total weight . Doubling works because travelling out and back along every edge of the tree certainly visits every vertex and returns to the start.

How can an initial upper bound be improved?

By finding shortcuts , replacing a repeated stretch of the tree with a single edge that joins the same two vertices but is not in the tree. The saving is the weight of the stretch less the weight of the shortcut.

How is a lower bound found by the deleted vertex method?

Remove one vertex together with all of its edges, find a minimum spanning tree of what is left, and note its total weight. Then add back the two shortest edges that connect the removed vertex to that tree.

What is a residual minimum spanning tree ?

It is the minimum spanning tree of the network that remains once one vertex and all of its edges have been taken away. Its weight forms the first part of a lower bound calculation.

In the deleted vertex method, why are exactly two edges added back to the residual minimum spanning tree?

Because in any tour the deleted vertex is entered once and left once , so it has to contribute exactly two edges. Taking the two shortest available keeps the total as small as it can be, which is what makes the result a lower bound rather than just an estimate.

How does the nearest neighbour algorithm build a route?

From the current vertex it always takes the edge of least weight to an unvisited vertex, and repeats until every vertex has been reached. One final edge is then added to return to the starting vertex.

What does the nearest neighbour algorithm produce?

A low-weight Hamiltonian cycle , whose total weight serves as an upper bound for the travelling salesman problem. It is not necessarily the least-weight cycle, and the best upper bound is the smallest one that can be found.

True or False? The nearest neighbour algorithm takes the shortest edge from any vertex already visited.

False. Nearest neighbour looks only at the current vertex, taking the shortest edge from wherever it has just arrived. It is Prim's algorithm that takes the shortest edge from any vertex already chosen, which is why the two are so easily muddled.

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

Listing every possible Hamiltonian cycle and taking whichever has the least weight. Nothing is known that finds the shortest cycle without doing this, so the method is only ever practical on small networks.

True or False? Reversing a Hamiltonian cycle produces a route with a different total weight.

False. A reversed cycle uses exactly the same edges as the original, so its total weight is identical. That is why the number of genuinely different tours is only half the number of listings.

Why must a network be complete before its travelling salesman problem can be solved by listing Hamiltonian cycles?

Because a Hamiltonian cycle is only the optimal answer when every vertex is joined directly to every other one. In an incomplete network the best route may have to pass through some vertex twice, which no Hamiltonian cycle ever does.

You have found a route and you already know the lower bound. When can you say the route is optimal?

When the route's weight is equal to the lower bound . No route at all can be shorter than the lower bound, so one that matches it exactly cannot be beaten.

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

The salesman has to reach every vertex , because that is where the selling happens, and may leave edges unused. The postman has to travel every edge , because that is where the letters are delivered, and may pass through a vertex several times.

International A Level (IAL)MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsThe Travelling Salesman Problem

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

Exam code: YMA01

1/28

0Still learning

Know0

FrontThe Travelling Salesman Problem
Define the travelling salesman problem.

Was this flashcard helpful?

Cards in this collection (28)

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 and returns to where it started.
Such a route is called a tour.
What is the difference between the classical and the practical travelling salesman problem?
In the classical problem each vertex is visited exactly once before returning to the start.
In the practical problem each vertex must be visited at least once, so a vertex may be passed through again on the way.
True or False?
In the travelling salesman problem, a tour is allowed to visit the same vertex more than once.
True.
A tour is a walk that visits every vertex and returns to its start, and a walk may pass through a vertex again.
A tour that visits every vertex other than the start exactly once is a Hamiltonian cycle, which is the special case the classical problem asks for.
What is a table of least distances?
A table of least distances gives the shortest distance between every pair of vertices in a network, which is not always the direct edge joining them.
It describes a complete network in table form.
Why is a table of least distances worth constructing for a travelling salesman problem?
Because it turns the practical problem into the classical one.
The table describes a complete network, and a complete network always contains a Hamiltonian cycle, so every vertex can then be visited exactly once.
Complete the triangle inequality, which every entry of a table of least distances has to satisfy:
$length A B \leq length A C +______$
The completed inequality is:
$length A B \leq length A C + length C B$
Here $A B$ is a longest length, so going round by way of $C$ can never beat going directly, which is what makes each entry a genuine least distance.
You are filling in a row of a table of least distances. What must you check about each direct connection?
Check whether the direct edge really is the shortest route between that pair of vertices, since going round through others is sometimes quicker.
Where it is not, the shorter total is the value that belongs in the cell.
Once a row of a table of least distances is complete, what can you fill in straight away?
The matching column for that same vertex, by copying the row's values down it.
A complete network is undirected, so the table is symmetrical about its leading diagonal.
Why is the travelling salesman problem usually tackled with bounds rather than solved outright?
Because there is no efficient algorithm that always finds the optimal solution.
Instead an upper and a lower bound are found, and the optimal route is known to lie somewhere between them.
Complete the relationship that the two bounds establish:
$______\leq optimal solution \leq______$
The completed relationship is:
$lower bound \leq optimal solution \leq upper bound$
The aim is to raise the lower bound and to lower the upper bound, so as to squeeze the interval the answer must lie in.
How do you find an initial upper bound for a travelling salesman problem from a minimum spanning tree?
Find a minimum spanning tree for the network, then double its total weight.
Doubling works because travelling out and back along every edge of the tree certainly visits every vertex and returns to the start.
How can an initial upper bound be improved?
By finding shortcuts, replacing a repeated stretch of the tree with a single edge that joins the same two vertices but is not in the tree.
The saving is the weight of the stretch less the weight of the shortcut.
An upper bound of $70$ is improved by replacing a repeated pathway of weight $30$ with a single edge of weight $14$ . What is the new bound?
The new upper bound is $70 - 30 + 14 = 54$ .
The saving is $30 - 14 = 16$ , so the bound comes down by exactly that much.
How is a lower bound found by the deleted vertex method?
Remove one vertex together with all of its edges, find a minimum spanning tree of what is left, and note its total weight.
Then add back the two shortest edges that connect the removed vertex to that tree.
What is a residual minimum spanning tree?
It is the minimum spanning tree of the network that remains once one vertex and all of its edges have been taken away.
Its weight forms the first part of a lower bound calculation.
In the deleted vertex method, why are exactly two edges added back to the residual minimum spanning tree?
Because in any tour the deleted vertex is entered once and left once, so it has to contribute exactly two edges.
Taking the two shortest available keeps the total as small as it can be, which is what makes the result a lower bound rather than just an estimate.
Deleting a vertex leaves a residual tree of weight $28$ , and the two shortest edges back to it are $7$ and $11$ . What is the lower bound?
The lower bound is $28 + 7 + 11 = 46$ .
The weight of the residual tree and the weights of the two reconnecting edges are simply added together.
How does the nearest neighbour algorithm build a route?
From the current vertex it always takes the edge of least weight to an unvisited vertex, and repeats until every vertex has been reached.
One final edge is then added to return to the starting vertex.
Complete the conditions a network must meet before the nearest neighbour algorithm can be used on it:
The network must be $______$ and must satisfy the $______$ inequality, and it needs at least three vertices.
The completed conditions are:
The network must be complete and must satisfy the triangle inequality, and it needs at least three vertices.
Where the network as given is not complete, a table of least distances has to be found first.
What does the nearest neighbour algorithm produce?
A low-weight Hamiltonian cycle, whose total weight serves as an upper bound for the travelling salesman problem.
It is not necessarily the least-weight cycle, and the best upper bound is the smallest one that can be found.
True or False?
The nearest neighbour algorithm takes the shortest edge from any vertex already visited.
False.
Nearest neighbour looks only at the current vertex, taking the shortest edge from wherever it has just arrived.
It is Prim's algorithm that takes the shortest edge from any vertex already chosen, which is why the two are so easily muddled.
What is the only method guaranteed to solve the travelling salesman problem exactly?
Listing every possible Hamiltonian cycle and taking whichever has the least weight.
Nothing is known that finds the shortest cycle without doing this, so the method is only ever practical on small networks.
Complete the count of Hamiltonian cycles in a complete network with $n$ vertices:
$number of cycles from a fixed start = (n -______)!$
The completed count is:
$number of cycles from a fixed start = (n - 1)!$
Fixing the starting vertex and then arranging all the remaining vertices in every possible order is what produces this.
True or False?
Reversing a Hamiltonian cycle produces a route with a different total weight.
False.
A reversed cycle uses exactly the same edges as the original, so its total weight is identical.
That is why the number of genuinely different tours is only half the number of listings.
A network has $6$ vertices. Why is listing every Hamiltonian cycle not a sensible way to solve it?
Because there are $120$ of them, which is far too many to work through by hand.
The number grows factorially with the number of vertices, so the method becomes hopeless very quickly indeed.
Why must a network be complete before its travelling salesman problem can be solved by listing Hamiltonian cycles?
Because a Hamiltonian cycle is only the optimal answer when every vertex is joined directly to every other one.
In an incomplete network the best route may have to pass through some vertex twice, which no Hamiltonian cycle ever does.
You have found a route and you already know the lower bound. When can you say the route is optimal?
When the route's weight is equal to the lower bound.
No route at all can be shorter than the lower bound, so one that matches it exactly cannot be beaten.
What is the essential difference between the travelling salesman and route inspection problems?
The salesman has to reach every vertex, because that is where the selling happens, and may leave edges unused.
The postman has to travel every edge, because that is where the letters are delivered, and may pass through a vertex several times.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:The Route Inspection AlgorithmNext:Critical Path Analysis