cft

Travelling Salesman Problem

via the Greedy Algorithm


user

Dhayaalan Raju

3 years ago | 1 min read

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

  1. It is quite easy to come up with a greedy algorithm for a problem.
  2. Analyzing the run time for greedy algorithms is much easier than for other techniques cause there is no branching or backtracking.

Disadvantages

  1. It does not give the optimal solution.
  2. 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:

  1. Minimum Spanning Tree
  2. Dijkstra’s algorithm for shortest paths from a single source
  3. 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.

Upvote


user
Created by

Dhayaalan Raju

iOS Developer at Ivy Mobility


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles