is a problem in combinatorial optimization. This problem is classified as NP-Hard (nondeterministic polynomial-time hard). Or simply put really freaking hard!!! Nonetheless it states that given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
If we view this as a weighted graph problem we can find solutions for specific cases using what is known as the "Greedy Algorithm" This is a heuristic algorithm yielding sub-optimal solutions. For all intensive purposes is sufficient.
One thing I have noticed about this method is that we assume these structures are abelian (commutative) in nature. What this means is we assume that we actually can go from point "a" to point "b" and also from point "b" to point "a",i.e the direction I travel is not determined. What always struck me as an interesting corollary is what if some of these were non-abelian or (non-commutative) i.e "one way" streets. Essentially in some areas,in terms of Graph Theory, we have "Digraphs". How is the "Greedy Algorithm" applied? Moreover can assuming non-abelian allow for polynomial time solutions?
Subscribe to:
Post Comments (Atom)
2 comments:
ummm......come again?
I don't think so. As there is a polynomial time transformation from the directed to undirected case.
You could simply remove edges to form directed graphs and test them in polynomial time.
Post a Comment