The Travelling Salesperson Problem (AQA A-Level Further Maths): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What is a Hamiltonian cycle in a network?
What is a Hamiltonian cycle in a network?
Closed path visiting each vertex once
How many possible tours exist in a network with vertices?
How many possible tours exist in a network with vertices?
What type of algorithm is the nearest neighbour algorithm?
What type of algorithm is the nearest neighbour algorithm?
Heuristic algorithm
In nearest neighbour, what do you choose at each step?
In nearest neighbour, what do you choose at each step?
Minimum weight arc to unvisited vertex
What provides an upper bound for the TSP?
What provides an upper bound for the TSP?
Length of any known tour
To find a lower bound, after removing vertex , what else is needed besides its two smallest arcs?
To find a lower bound, after removing vertex , what else is needed besides its two smallest arcs?
MST of remaining vertices
If is the optimal tour length, which inequality is correct?
If is the optimal tour length, which inequality is correct?
lower bound upper bound
Which statement about bounds is correct?
Which statement about bounds is correct?
Want largest lower & smallest upper bound
First step to convert practical TSP to classical TSP?
First step to convert practical TSP to classical TSP?
Create complete network with shortest distances
When is a lower bound the optimal solution?
When is a lower bound the optimal solution?
When it forms a tour