|
|
Re: genetic algorithm Traveling Salesman Problem data representation
Posted:
Jun 3, 2006 9:52 PM
|
|
Kent Paul Dolan wrote:
|Jack Saalweachter wrote:
|> Kent Paul Dolan wrote:
|
|>> That said, "cut and branch" solutions for the TSP
|>> supposedly can check that a solution is the
|>> correct one, in polynomial time, even though, I
|>> think, they can't find that solution in
|>> polynomial time.
|
|> Are you certain about that?
|
|Well _I'm_ not certain, it's been a decade and a
|half or more since I could read math that complex,
|but the people who did the work are quite certain,
|per the writeup in the link I gave earlier.
There are cases in which they can prove that a solution
is optimal, but I don't see any place where they make
claim to be able _always_ to do this in polynomial time,
(assuming the optimal solution has been given, of course).
|> The actual NP-complete problem at the heart of the
|> Traveling Salesman Problem is "Is there a tour of
|> length B or less?" It seems odd to me that
|> answering the question "Is this tour optimal?"
|> doesn't answer that question as well.
|
|As David Kinny notes in another followup, since
|_finding_ that solution still requires exponential
|time, that's not a free lunch.
|
|Nothing about a problem being NP complete prevents
|that you just might _guess_ the solution on the very
|first try, the odds are just rather overwhelmingly
|the other direction. In this case, since the
|solution was found by the LKH _heuristic_, which
|provides no guarantee that it has converged to a
|solution when it does converge, it does indeed count
|as a "guess", though a tremendously sophisticated
|one.
|
|Further, and now I'm working on really fuzzy
|memories, it is characteristic of NP complete
|problems that the problem is (considered to be) in
|need of expontial time to solve it, but that there
|can be a certificate that the problem _has been_
|solved, which can be checked in polynomial time. In
|this case, the certificate happens to _be_ the
|solution, but that isn't required to be the case.
Well, first, the NP complete problems are by definition
yes/no questions, and it is the problem "Is there a tour
of length <=B?" that's the NP complete problem. Simply
being in NP means that when the answer to the question
is "yes" there is a certificate of the fact that can be checked
in polynomial time. NP complete problems are ones to
which all problems in NP can be reduced in a certain way.
The expectation that exponential time is required for them
needs to be qualitied a bit. Say we have an NP complete
problem X that can be solved in time O(2^n). Then let's
consider a problem Y obtained by "padding out" the
problems in X, so that the problems in Y whose answers
are "yes" correspond one-to-one with the ones in X in some
simple way, but with the length of the problem in Y being
n^3 where n is the length of the problem in X. (Require that
the problem in X be repeated n^2 times, for instance.) Then
we get that Y is also NP-complete, but can be solved in time
O(2^n^{1/3}). So, for "exponential", understand that in some
cases it might be O(2^n^{1/k}) for some k>1. The "usual"
NP complete problems don't seem to be "padded" like this,
so one doesn't expect this, but when one is talking about
NP-complete problems *in general*, one has to keep such
cases in mind. And as usual the belief that NP complete
problems are as hard to solve as all that is still only conjectural.
If it were the case that for each shortest tour, there always
was a certificate that it was the shortest, that could be checked
in polynomial time, then whenever the answer to the question
"Is there a tour of length <= B?" was "no", there would be a
certificate of the fact, in the form of the shortest tour, plus a
certificate of the fact that there wasn't a shorter one.
The yes/no problems where if the answer is "no" there's a
certificate, are the NP problems with yes and no swapped,
and they're called the co-NP problems. As you point out, there
is still no "free ride" to be had here. There's nothing to guarantee
that if a problem is in the intersection of NP with co-NP, then
it can be solved in polynomial time.
"Is n prime?" is obviously in co-NP, since if n is not prime, one
can check that it is not given factors of it. Less obviously, it was
known to be in NP, given a number-theoretic certification of
primality, showing that it has a primitive root, recursively
proving how n-1 factors into primes. Before the recent proof
that "is n prime?" is in P (can be solved in polynomial time), it
was one of the more famous examples of something in the
intersection of NP and co-NP but not known to be in P. There
was even a probabilistic algorithm for it, and an algorithm
known to be polynomial if the Riemann hypothesis holds!
Since Travelling Salesman is NP complete, however, if it were
in co-NP, then all of co-NP would be reducible to something
in NP. Hence it would follow that NP = co-NP. The belief that
NP <> co-NP is also still only a conjecture, however, it seems
pretty unlikely that NP = co-NP.
So I think this is not a matter of always being able to come up with
a proof of optimality, but just that the techniques are powerful
enough to get proofs of optimality in reasonably large "ordinary"
cases of the problem. TSP is one of those problems where the
worst-case difficulty seems to be rather different from the typical
case difficulty. It's sort of interesting that this kind of grey zone
of problems has been mapped out by these folks. They seem to
be making a lot of use of linear programming, which is interesting
in having a polynomial time algorithm for it, but not in any
obvious way, and also in that the simplex algorithm is still one
of the favorites in spite of having bad worst-case behavior.
The moral of the story is, just because certain cases are very hard
doesn't mean one should give up on solving typical cases.
Keith Ramsay
|
|
