Least weight cycle through all vertices

Concept of a Least Weight Cycle Through All Vertices

• This concept is also known as the Travelling Salesman Problem (TSP), a classic algorithmic problem that focuses on optimisation.
• The main aim is to find a cycle of least total weight in a graph that visits each vertex exactly once, returning to the originating vertex.
• Real-world applications of the TSP include logistics for delivery routing, manufacturing of circuit boards, and DNA sequencing.

The Brute-force Approach

• This involves exhaustively enumerating all possible permutations of the cities (vertices), which is extremely time-consuming and impractical for large data sets due to factorial growth.

The Nearest Neighbour Algorithm

• A greedy algorithm that selects the next unvisited vertex that is nearest in terms of weight to the current vertex.
• While this is easy to implement and relatively efficient, the solution may not always be the most optimal.

The Repeated Nearest Neighbour Algorithm

• An extension of the Nearest Neighbour algorithm, it repeatedly applies the Nearest Neighbour algorithm from each unvisited vertex, and finally selects the shortest tour.
• It offers a better chance of getting the optimal solution than the simple Nearest Neighbour algorithm, at the expense of running time.

The Cheapest Link Algorithm

• Another greedy algorithm, it keeps selecting the shortest edge available that doesn’t create a cycle (unless it closes a circuit of the correct size), ensuring each vertex has an even degree.
• It doesn’t guarantee the optimal solution, but often provides acceptable solutions.

Common Pitfalls and Errors

• It’s crucial to remember that the approach of simply selecting the shortest available edge at all stages could sometimes lead to a non-optimal solution in the long run, known as a greedy trap.
• While solving the problem, recall that visiting all the vertices exactly once and minimizing the total weight are the fundamental requirements.

Practical Application and Exercises

• Demonstrating real-world scenarios, such as planning the shortest possible route for a delivery truck that needs to make stops in multiple locations, helps to comprehend the concept.
• Attempting to code the Nearest Neighbour Algorithm or Cheapest Link Algorithm can reinforce the understanding of these concepts.
• Visualising sequences of the processing steps can aid in grasping how these algorithms function.