The Travelling Salesman Problem (Edexcel A-Level Further Mathematics): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What do upper & lower bounds help determine in TSP?
What do upper & lower bounds help determine in TSP?
Proximity to optimal solution
What does the lower bound represent in TSP?
What does the lower bound represent in TSP?
Smallest possible distance for valid route
What is the first step for lower bound with incomplete graphs?
What is the first step for lower bound with incomplete graphs?
Convert to complete network
Which algorithms construct the MST for lower bound?
Which algorithms construct the MST for lower bound?
Prim's or Kruskal's
What is added to MST weight for lower bound?
What is added to MST weight for lower bound?
Two smallest edges from starting vertex
What does the upper bound represent in TSP?
What does the upper bound represent in TSP?
Achievable but not necessarily optimal
How does Nearest Neighbour algorithm select the next vertex?
How does Nearest Neighbour algorithm select the next vertex?
Move to nearest unvisited vertex
How can the upper bound be improved?
How can the upper bound be improved?
Use shortcuts for shorter alternatives
What happens if you forget to add two smallest edges to MST?
What happens if you forget to add two smallest edges to MST?
Results in an underestimate
What defines a Minimum Spanning Tree (MST)?
What defines a Minimum Spanning Tree (MST)?
Smallest total edge weight, no cycles