唔.....问个算法题，Travelling Salesman Problem(TSP)用哪种算法比较容易？

是对称的TSP,就是d(i,j)=d(j,i),但不满足三角不等式。最起码要比2的n次方要快些......但是编起来又不会太难......发愁ing............Final Project= =

TSP貌似是NPC问题啊

NPC有什么approximation algorithm来着

用演化计算算法，PSO,GA等比较好，常规算法挺难的

NPC有什么approximation algorithm来着
lai 发表于 2011-2-22 17:17

. 1point3acres

    TSP is in general inapproximatable, unless in some special cases like metric-TSP.

是对称的TSP,就是d(i,j)=d(j,i),但不满足三角不等式。最起码要比2的n次方要快些......但是编起来又不会太难......发愁ing............Final Project= =
everwinter 发表于 2011-2-22 15:33

If you can find an algorithm slightly better than O(2^n), then probably you can win this year's Turing Award (quote from Wikipedia):  

It is an open problem if there exists an exact algorithm for TSP that runs in time O(1.9999n)

    As far as I know symmetric doesn't help in terms of complexity, at best cut the solution space to a half.

Life is hard, try to relax the problem a bit (Metric-TSP then Greedy is 2-approximation).
Or don't care exact solution (LP relaxation, evolutionary algos such as Genetic Algorithm, Simulated Annealing)