# Chapter 5 The Travelling Salesman Problem Flashcards

1
Q

State the algorithm that allows us to find an upper bound for the practical salesmen problem?

Why won’t this work with the CSP?

A

It won’t work with the CSP because by definition vertices will be visited more than once

2
Q

State the algorithm which can be used to find a lower bound to the classical salesman’s problem?
How do you make it work for the practical salesman’s problem?

A

This algorithm only works for the classical problem. To make it work for the practical problem you need to apply the algorithm to a table of least distances

3
Q

State the nearest neighbour algorithm

A
4
Q

How can you find the optimum problem in a travelling salesman problem?

A

If you have lower bound of 23 and then you find a solution which a value of 23 then that must be a optimal solution

5
Q

What is a tour?

A

A tour is a walk which visits every vertex which returns to its starting vertex

A tour could visit every vertex more than once but if every vertex is visited only once then it is a hamiltonian cycle

6
Q

Hat is a walk?

A

A walk in a network is a finite sequence of edges such that the end vertex of 1 edge is the start vertex of the next

7
Q

What is the classical problem?

A

In the classical problem, each vertex must be visited exactly once before returning to the start

8
Q

What is the practical problem?

A

In the practical problem, each vertex must be visited at least once before returning to the start

9
Q

What is the able of least distances?

A

A table which shows the shortest path between every vertex

10
Q

What is the problem with the finding a lower bound algorithm and how can it be overcome?

A

It only works for the classical problem

To make it work for the practical problem you need to apply the algorithm to a table of least distances

11
Q

What is a Residual Spanning Tree?

A

The residual spanning tree is the MST for the resulting network after removing a vertex

12
Q

Explain the exam technique tip in 5.3?

A

When finding shortcuts you can draw the spanning tree as a straight line

13
Q

Which bound do you use if you are asked to write down your upper and lower bounds?

A

If asked to write an inequality the lower bound will be < if it doesn’t represent a hamiltonian cycle (as that can’t be a solution)
The upper bound will always be ≤

14
Q

What is the point of the nearest neighbour algorithm?

A

Finding shortcuts takes a long time so use this instead

15
Q

What will the nearest neighbour alg generally give you as a solution?

A

A tour
And not a optimal solution

16
Q

What is the disadvantage of using the nearest neighbour algorithm?

A

You may be forced to use long arcs

17
Q

State the triangle inequality

A