|
|
 |
| |
|
|
|
Monte Carlo Simplification Model for Traveling Salesman Problem |
|
|
|
PP: 721-727 |
|
|
|
Author(s) |
|
|
|
Dong WANG,
Dong-mei LIN,
|
|
|
|
Abstract |
|
|
| Traveling Salesman Problem (TSP) is one of classical NP-hard problems in the field of combinatorial optimization. It is
because of the problem complexity that almost all of the accurate computing algorithm could not find the global optimal solution
(GOS) in a reasonable time. The complexity is characterized by the large number of edges in the initial edge set of TSP. By analyzing
the relationship between GOS and high-quality local optimal solutions, it is found that the edge union set of some local optimal solutions
could include most even all edges of GOS, and that their edge intersection could fix partial edges of GOS with high probability. The
method reducing the initial edge set of TSP is established based on the probability statistic principle. The search space in which to
solve the problem is cut down greatly, and the edge quantity in the new edge set is about twice times of the problem scale. Accureate
algorithm can find GOS with high probability for TSPs whose scale are up to 200 nodes based on the simplified initial edge set. The
method could be applied to many kinds of algorithms also used for solving TSP. |
|
|
|
|
|
|
|
