The Travelling Salesman Problem (Edexcel A-Level Further Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Lower bound in TSP represents
Lower bound in TSP represents
The smallest possible distance for a valid TSP route
Upper bound in TSP represents
Upper bound in TSP represents
An achievable (not necessarily optimal) route length
Lower bound formula for TSP
Lower bound formula for TSP
Weight of MST + two smallest edges from starting vertex
Method to find upper bound in TSP
Method to find upper bound in TSP
Nearest Neighbour Algorithm
Algorithm used to find lower bound in TSP
Algorithm used to find lower bound in TSP
Minimum Spanning Tree (MST) method
What to add to MST weight for lower bound?
What to add to MST weight for lower bound?
Two smallest edge weights from the starting vertex
How to improve upper bound in TSP?
How to improve upper bound in TSP?
Use shortcuts while maintaining Hamiltonian cycle
What is an MST?
What is an MST?
Tree connecting all vertices with smallest total weight and no cycles
Triangle inequality in TSP
Triangle inequality in TSP
First step for lower bound if graph incomplete?
First step for lower bound if graph incomplete?
Convert to complete network using shortest paths