Flashcards
2021-11-26
How could you formulate the travelling salesperson problem in terms of Hamiltonian cycles??
Finding the shortest Hamiltonian cycle on a graph.
For small graphs, how can you solve the travelling salesperson problem??
Try every Hamiltonian cycle.
What is the nearest neighbour algorithm used for??
Finding a Hamiltonian cycle that can be used as an upper bound for the TSP.
What are the 4 steps of the nearest neighbour algorithm??
- Choose any start vertex
- Go to the nearest vertex that hasn’t been included
- Repeat 2 until all vertices have been included
- Return directly to the start vertex
What would be the first step in using the nearest neighbour algorithm on this distance matrix??
Crossing out the $A$ row and labelling the $A$ column with a $1$.
What is the next step when trying to use the nearest neighbour algorithm??
Crossing out the $E$ row and labelling the $E$ column with a $2$.
How can you use the nearest neighbour algorithm to get an upper bound on a graph??
Use the algorithm starting at each vertex to find a Hamiltonian cycle and pick the lowest one.
What is the key difference between the matrix version of Prim’s algorithm and nearest neighbour algorithm??
In the nearest neighbour algorithm, you only try and find smallest value for the most recently added vertex.
2021-11-27
When using a minimum spanning tree as a lower bound for the TSP, what do you have to do??
Double the minimum spanning tree.
What is the 3 stage technique for finding a lower bound for the TSP??
- Delete one vertex and all edges associated with it.
- Find a minimum spanning tree for this reduced graph.
- Include the two shortest edges that were connected to the deleted vertex.
If the upper and lower bound are the same, what must be true??
The value at the bound is the optimal solution.
2012-12-07
What is triangle inequality for an edge $AB$??
$$ \text{weight} AB \le \text{weight} AX + \text{weight} XB $$
What is the TSP for complete graphs that satisfy the triangle inequality called??
The classical problem.
How can you turn a non-complete graph that doesn’t satisfy the triangle inequality into one that does??
Rewrite it using the shortest distances between all points and jot down which paths you male.
How can you rewrite a graph matrix to show the shortest distances between each point for the TSP??
Draw the graph and do it visually.
Backlinks
Metadata
date: 2021-11-26 09:11
tags:
- '@?further-maths'
- '@?school'
- '@?public'
- '@?decision'
title: Further Maths - Travelling Salesperson Problem
