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.
  • 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.