The traveling salesman problem (TSP) is a popular AI problem that asks for the most efficient trajectory possible given a set of points and distances that must all be visited. In computer science, the problem can be applied to the most efficient calculation. Study the paper attached in the project 2. The paper is "Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches".Read this paper and understand some questions like what the traveling salesman problem is and its applications. After you read the paper in the task 1, you would provide the answers to the following questions. These answers are required to be written into the project report. What is the traveling salesman problem?What are applications of the traveling salesman problem?

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.

Refer below.

Explanation:

What is the traveling salesman problem?

The travelling salesman problem poses the accompanying inquiry: "Given a rundown of urban areas and the separations between each pair of urban areas, what is the most limited conceivable course that visits every city and comes back to the cause city?" It is a NP-difficult problem in combinatorial streamlining, significant in tasks look into and hypothetical software engineering.

The travelling consumer problem and the vehicle directing problem are the two speculations of TSP.

What are applications of the traveling salesman problem?

The arrangement of TSP has a few applications, for example, arranging, planning, coordinations and pressing. As a rule - complex improvement problems. In numerous applications, extra limitations, for example, restricted assets or time windows might be forced.