Traveling Salesman Problem (TSP)
The problem requires a tour beginning at specificlocation and visiting the remaining n-1 locations, each beingvisited only once, with a return to the beginning point so as tominimize the total distance traveled. Although the problem sound verysimple, its exact solution is not. In a small problem with fivelocations, there are (n-1)!/2 possible solutions. The division by2 reduces the problem since we assume that thedistance from i to j is the same as the distance from j to i.
Thus, afive-city problem has 12 possible solutions. However, a problem with10 cities has more 180,000 possible solutions.Although exact solutions to the problem exist, theyare not efficient. Many operations researchers consider this problemso difficult that it will never solved efficiently. (If you can solve it,You can becomefamous!)
Data mining & Knowledge Management Research Group
Departement of Computer Science
Faculty of Computer System & Software Engineering
Universiti Malaysia Pahang
www.sajadinbiring. multiply. com
No comments yet.