Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-18
Computer Science
Data Structures and Algorithms
This is a book containing 350 pages
Scientific paper
In "The Symmetric Traveling Salesman Problem"(math/0508212)[math.CO], an algorithm obtained an approximate solution for a general traveling problem where n is even. Here we extend the algorithm to when n is odd. We also extend the algorithm to one that obtains an exact solution. In chapters 3 and 4, the concept of the :average arc-value" (aav) of a weighted path is introduced. We use it to prove that given any weighted n-circuit(n-cycle)C, it always contains a determining point,d, such that every subpath emanating from d in a fixed orientation has an aav no greater than that of C. Using threads of parallel processors, this allows us to construct an exact solution (not necessarily in polynomial time) to any general traveling salesman problem as well as to numerous heuristics.
No associations
LandOfFree
The General Traveling Salesman Problem, Version 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The General Traveling Salesman Problem, Version 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The General Traveling Salesman Problem, Version 2 will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-292683