* This method will return an approximate minimal traveling salesman tour * (hamiltonian cycle). This algorithm requires that the graph be complete * and the triangle inequality exists (if x,y,z are vertices then * d(x,y)+d(y,z)<d(x,z) for all x,y,z) then this algorithm will guarantee a * hamiltonian cycle such that the total weight of the cycle is less than or * equal to double the total weight of the optimal hamiltonian cycle. The * optimal solution is NP-complete, so this is a decent approximation that * runs in polynomial time
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment