The traveling salesman problem is a well-known example of a problem for which it is easy to guess and test the solution, but which takes exponential time to solve. Here, unofficially, the problem: you are given a map of 100 cities in the United States with the distance between each pair of cities. Your task is to start from a specific city (say, Boulder); visit each of the other 99 cities exactly once; and then return to Boulder. Naturally, there are many routes you can take to achieve this goal. Your goal is to find a minimum total distance route that will reach your goal. (Sometimes a goal is formulated by specifying a target value: that is, your goal is to find any route that visits each city exactly once and requires no more than M miles.) A sure-fire approach to this problem is to (firstly) list all possible routes from 99 cities (we assume that Boulder is the first and last city); sort the list by miles driven; and choose the cheapest route. How long is our list of possible routes from 99 cities? In response, write your answer in the form of a coefficient and a factorial symbol (i.e. X!).

Dryunya1989    2   05.08.2020 13:56    0