# Travelling Salesman Problem

# via the Greedy Algorithm

Dhayaalan Raju

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.

Upvote

Dhayaalan Raju

iOS Developer at Ivy Mobility

Related Articles