Re: Distance normalized TSP algorithm

JSH wrote:
....
I have a new idea. It came to me as a clever trick, and as I ponder
it more, I like it more, but it still might be crap.

I don't think that approaching a problem from two ends is a new idea. I
have not seen it applied to TSP, but I suspect that is mainly because it
is not particularly useful for that problem. It does little or nothing
for the difficult aspect, the need to make decisions that are globally
optimal without being locally optimal.

The point here really is puzzling out this approach, where I'm still
telling myself, hey, at least this thing will give a round trip
solution and hit every node, so maybe down the line I program it and
see what kind of funny little graphs it makes anyway.

Finding a Hamiltonian path in a complete graph is not difficult enough
to be interesting. You really need to pick some problem that is a bit
more challenging than that, but perhaps a bit less challenging than
finding a polynomial time algorithm for an NP-complete problem. Most of
computer science is somewhere in that range.

I am not familiar, beyond the general idea that there are usable
methods, with the state of research into TSP approximation and
probabilistic algorithms. Also, some of your ideas amount to looking for
special cases of TSP that are polynomial time solvable.

If you are interested in TSP why not study what has already been done in
one of those areas, and see if you can add to it?

Patricia
.

Relevant Pages

  • Re: Why isnt NP simply "not polynomial"?
    ... Why can't NP be defined as the class of decision problems ... It is certainly possible to define a class Not-P (I'll use a different ... there is no *known* polynomial time algorithm. ...
    (comp.theory)
  • Re: Aspiring highest-order programmer
    ... >> active knowledge into dead secrets in such a way that one can never, ... the moment someone comes up with a polynomial time ... > polynomial time algorithm to solve the problem which makes the problem ... Doesn't this fail to answer the question as to the practicality of the ...
    (comp.programming)
  • hi guys...need insight into this interesting algorithm..Repost
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.math)
  • Interesting algorithm...need insights..
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.logic)