模拟退火和对称

*欧几里德旅行商问题。

*

*为基础的解决办法的本地搜索启发式

*非过境道路和近邻

-/*

* Simulated annealing and the Symetric

* Euclidian Traveling Salesman Problem.

*

* Solution based on local search heuristics for

* non-crossing paths and nearest neighbors

*

* Storage Requirements: n^2+4n ints

*

* Problem: given the coordinates of n cities in the plane, find a

* permutation pi_1, pi_2, ..., pi_n of 1, 2, ..., n that minimizes

* sum for 1<=i<n D(pi_i,pi_i+1), where D(i,j) is the euclidian

* distance between cities i and j

*

* Note: with n cities, there is (n-1)!/2 possible tours.

* factorial(10)=3628800　factorial(50)=3E+64　factorial(150)=5.7E+262

* If we could check one tour per clock cycle on a 100 MHZ computer, we

* would still need to wait approximately 10^236 times the age of the

* universe to explore all tours for 150 cities.

*

* gcc-O4-o tsp tsp.c-lm　 tsp | ghostview-

*

* Usage: tsp [-v] [n=dd] [s=dd] [filename]

*　　-v　　　 : verbose

*　　 n=　　　 : nb of cities (cities generated randomly on E^2