The speed of computers has increased greatly over the history of computing. The

Question

The speed of computers has increased greatly over the history of computing. The traveling salesman problem attempts to find a pathway for a salesman to visit all of the cities on his route using the shortest distance. The brute force method for solving this problem looks at all possible permutations of the cities. There are n! such permutations (where n! = n * (n-1) * (n-2) *…*1). Thus, 5! = 120. Current computers are running with clock speeds in the GigaHz range (10,000,000 times faster than the earliest computers) and they still are not able to solve the traveling salesmen problem using this brute force method for moderate values of n (like 50). If technology keeps moving ahead at the current rate, will this problem soon become feasible (yes or no)? Back up your answer with some sample numbers concerning factorials and speed of computers.

Explanation / Answer

Traveling Salesman Problem's:

        This is one of the most well known difficult problems of time. A salesperson must visit n cities, passing through each city only once, beginning from one of the city that is considered as a base or starting city and returns to it. The cost of the transportation among the cities is given. The problem is to find the order of minimum cost route that is, the order of visiting the cities in such a way that the cost is the minimum.

Algorithm :

                First, find out all (n -1)! Possible solutions, where n is the number of cities.

                Next, determine the minimum cost by finding out the cost of everyone of these (n -1)! Solutions.

                Finally, keep the one with the minimum cost.

                Clearly, this requires at least (n-1)! Steps.

Brute force:

Brute force is a straightforward approach to solve a problem based on the problem’s statement and definitions of the concepts involved. It is considered as one of the easiest approach to apply and is useful for solving small–size instances of a problem.

Step 1: calculate the total number of tours(=where represents the number of nodes

           (cities).

Step 2: draw and list all the possible tours

.Step 3: calculate the distance of each tour

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.