Answer and Explanation:
What is the travelling salesperson problem?
TSP is a problem where we have a list of cities and the distance between each pair of cities. It's required that the salesperson visits all the cities. Naturally, there can be many paths by which the salesperson can visit all the cities. The problem requires us to obtain a path such that the salesperson travels every city exactly once excluding the start city which will also be the end city such that the total distance traversed by this path is the minimum.
What are the applications of the travelling salesman problem?
There are many real-world applications of this problem. One of them being constructing roads to interconnect many cities such that the cost to build the roads is minimised.Another such example though it may be irrelevant to a common man is flight paths. Suppose I'm the owner of an airline company, I will have a limited number of aeroplanes. I will want to provide air travel between cities such that I can allocate more flights on a busier route and have fewer planes flying between cities which have fewer customers to maximise my profit while providing connectivity between all the cities.
Some other applications are:
Vehicle routing (A generalised name for the above examples)
The order-picking problem in warehouses
Computer wiring
Drilling of printed circuit boards
According to solution approaches in the paper, which technique you will use to solve the travelling salesmen problem in task 2?
We can use the brute force method to find the optimal path
First, we calculate the distance between each pair of points and tabulate the Distance Matrix.
Then we select the city which is closest to city A . Then we select the city which is closest to that city and so on till we are left with no more cities to travel.