Travelling Salesman Problem
via the Greedy Algorithm
As the name suggests a greedy algorithm, always makes the choice that is best at that moment. This means that it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.
How to decide which choice is optimal?
Assume there is an objective function that needs to be optimized. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.
Greedy algorithms have some advantages and disadvantages
Advantages
- It is quite easy to come up with a greedy algorithm for a problem.
- Analyzing the run time for greedy algorithms is much easier than for other techniques cause there is no branching or backtracking.
Disadvantages
- It does not give the optimal solution.
- Proving that a greedy algorithm is correct is difficult.
The greedy method is quite powerful and works well for a wide range of problems. Many algorithms can be viewed as applications of Greedy algorithms, such as:
- Minimum Spanning Tree
- Dijkstra’s algorithm for shortest paths from a single source
- Huffman codes (data-compression codes)
Let's see how the greedy algorithm works on the Travelling Salesman Problem
Greedy Algorithm for TSP
This algorithm searches for the local optima and optimizes the local best solution to find the global optima. It begins by sorting all the edges and then selects the edge with the minimum cost. It continuously selects the best next choices given a condition that no loops are formed. The computational complexity of the greedy algorithm is O(N 2 log2(N)) and there is no guarantee that a global optimum solution is found.
Implementation
Step 1
Step 2
Step 3
Step 4
The Final answer is A -> B -> D -> C -> A = 2.4 + 5.1 + 5.9 + 6.8 = 20.2
And that’s how a greedy algorithm works for the Travelling Salesman Problem.
