Of course it is , because both problems are NP-COMPLETE. But the transformation is non-trivial, it only comes from the definition fo NP-Completeness
2008/12/16 Golabi Doon <golabid...@gmail.com> > > Hello folks, > > I am trying to solve a non-standard TSP problem with no success so > far. I would really appreciate some help/hint on this problem. > > The problem is a typical TSP problem: Given a complete graph, we want > to visit all the nodes and each node exactly once in a way that the > cost of traverse is minimal. > > The cost function is defined for every "two consecutive edges", which > makes it a nonstandard TSP, For example, if I go from A to B and then > to C, then I get cost(A,B,C) (in a typical TSP, costs are defined per > edge, i.e. in form of cost(X,Y) and so here it would be cost(A,B)+cost > (B,C)). The cost function in my problem is symmetric, i.e. going from > A to B and then to C has the same cost as going from C to B and then > to A. > > Finally, note that if I visit nodes A,B,C,D respectively, the total > cost would be cost(A,B,C)+cost(B,C,D). > > Is it possible to map this problem to a standard TSP? > > Thank you for your time! > > Golabi > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---