Other
Travelling Salesman Problem:
The goal of the travelling salesman problem (TSP) is to find a tour of a given number of cities, visiting each city exactly once and returning to the starting city where the length of the tour is minimized. The TSP is a NP-hard problem, so unless we settle for an approximated result, computations will be very time consuming [3]. Currently the only known method guaranteed to optimally solve the travelling salesman problem of any size, is by enumerating each possible tour and searching for the tour with smallest cost. Each possible tour is a permutation of 123 . . . n, where n is the number of cities, so therefore the number of tours is n! When n gets large, it becomes impossible to find the cost of every tour in polynomial time. Such a method, which will end up giving the optimal solution, is obviously not very feasible because of the time consumption required to calculate all the tours. It can be seen that even for small instances, the time consump
matlab
算法
tsp
遗传
求解
No comment