# Chapter 5 The Travelling Salesman Problem Flashcards

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

Why won’t this work with the CSP?

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

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?

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

State the nearest neighbour algorithm

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

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

What is a tour?

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

Hat is a walk?

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

What is the classical problem?

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

What is the practical problem?

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

What is the able of least distances?

A table which shows the shortest path between every vertex

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

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

What is a Residual Spanning Tree?

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

Explain the exam technique tip in 5.3?

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

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

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 ≤

What is the point of the nearest neighbour algorithm?

Finding shortcuts takes a long time so use this instead

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

A tour

And not a optimal solution