## What is Travelling Salesman Problem (TSP)

The Travelling Salesman Problem (TSP) is a well-known computational problem in which the goal is to find the shortest possible route that visits a given set of cities and returns to the starting city, while visiting each city exactly once. The TSP is an NP-hard problem, which means that there is no known algorithm that can solve it in polynomial time. However, there are several heuristic and approximation algorithms that can provide reasonably good solutions in a reasonable amount of time. One such algorithm is the greedy algorithm.

## Greedy Algorithm

The greedy algorithm is a simple and intuitive approach to solving the TSP. The basic idea is to start at some city, then repeatedly visit the nearest unvisited city until all cities have been visited. To return to the starting city, the algorithm simply chooses the shortest path back from the final city to the starting city. This approach is known as the Nearest Neighbor algorithm.

## TSP Solving by Greedy Algorithm

The Travelling Salesman Problem (TSP) is a classic optimization problem in which the goal is to find the shortest possible route that visits a given set of cities and returns to the starting city, while visiting each city exactly once. The problem is NP-hard, meaning that it is computationally infeasible to find an optimal solution in a reasonable amount of time for large instances. However, heuristic and approximation algorithms can be used to provide good solutions in practice.

One of the most popular and simple algorithms for solving the TSP is the greedy algorithm. The basic idea of the greedy algorithm is to start at some city and then repeatedly visit the nearest unvisited city until all cities have been visited. To return to the starting city, the algorithm chooses the shortest path back from the final city to the starting city.

### The algorithm can be described in the following steps:

- Start at some city.
- Find the nearest unvisited city.
- Move to that city.
- Mark that city as visited.
- Repeat steps 2-4 until all cities have been visited.
- Return to the starting city via the shortest path.

The algorithm can be implemented using a priority queue to keep track of the nearest unvisited city. The priority queue is initialized with the starting city, and then updated each time a new city is visited.

While the greedy algorithm is simple and easy to implement, it may not always produce the optimal solution. The algorithm may get stuck in a local minimum or fail to consider the global structure of the problem. However, the algorithm can provide reasonably good solutions for small and medium-sized instances of the TSP.

Several modifications and variations of the greedy algorithm have been proposed to improve its performance, such as the 2-Opt algorithm, which iteratively improves the tour by swapping pairs of edges to reduce the total distance.

## Conclusion

The greedy algorithm is a simple and intuitive approach to solving the TSP. While it may not always produce the optimal solution, it can provide reasonably good solutions in a reasonable amount of time. Modifications and variations of the algorithm can be used to improve its performance for larger instances of the problem.

- Q-1.
- What do you understand by time and space complexity? What is asymptotic notation? Why it is important? Discuss using suitable example.
- Q-2.
- What is recurrence? Discuss in detail the master method for solving a recurrence.
- Q-3
- What is a Travelling Salesman problem? Discuss the greedy algorithm for solving the Travelling Salesman Problem.
- Q-4
- What do you understand by height balanced tree? What is a splay tree? Discuss the insertion/deletion operation on splay tree.
- Q-5
- What is Minimum Spanning Tree? Discuss the Steps for finding Minimum Spanning Tree using Kruskal’s Algorithm.
- Q-6
- What is a Graph? Discuss the depth first traversal of a graph and its computational complexity. Also discuss the topological sort using depth first traversal.
- Q-7
- What is a flow network? Explain Ford-Fulkerson Algorithm for Maximum Flow Problem.
- Q-8
- What is bitonic sequence? What is merging network? Explain.