Re: Distance normalized TSP algorithm

On Jul 25, 6:46 pm, Joshua Cranmer <Pidgeo...@xxxxxxxxxxxxxxx> wrote:
JSH wrote:
On Jul 25, 12:40 pm, Patricia Shanahan <p...@xxxxxxx> wrote:
JSH wrote:

...> As that's fairly easy I'd like to focus first on getting a full path
from an arbitrary start at just any node, say, chosen randomly.
...

Unless you are aiming for a probabilistic algorithm, which may get
different results for the same problem on different runs, don't pick the
start node at random. Make up some rule, no matter how arbitrary.
That solution is to try EACH node in turn as a starting point, and
calculate the path, so it doesn't matter which one your start with, so
yeah, you could do it randomly.

That doesn't quite solve the problem: if going to node A and node B have
the same cost, what criteria should I use to choose between them?
Patricia would probably be satisfied with an answer like "the latter you
looked at" instead of saying "choose randomly".

That works for me!

The idea is to be as complete as possible, as I assume that there
would be cases where paths came out with equal values.

But what about starting at another node?

That doesn't work either. Make a larger graph containing two of these
"traps" and you'll note that you can't start from both of them at the
same time. I haven't tested it myself, but your solution gets around the
problem by (essentially) stating "start in the central node of the
subgraph", which can't work if there are two subgraphs like that.

That's a more general assumption than what she made and sounds good
intuitively but you haven't even begun to give any kind of proof.

But it is a route to a counterexample to this idea: use two "traps"
and prove that the algorithm as described cannot give an optimal
path.

I call a graph where costs match well with distance a well correlated
graph, and notice your example is not one, as distances are all units,
so I found a way to get my distance argument back in, with
correlation.

Define "match well with distance," please.

Goes back to when I was arguing that wrapped up in the real world with
any TSP problem is some notion of distance. For instance, long trips
tend to cost more, so it costs more to fly to a distant city than to
drive to the supermarket.

But, as was noted you can have situations where cost has no connection
with distance, and you can have a TSP problem where no distances are
given, which lead me to the distance normalized algorithm where all
nodes are assumed to be equidistant from each other.

However, the algorithm I use at its heart is about distance
correlation, where the longer the distance between nodes the greater
the cost.

So if I'm right, it easily solves TSP when cost matches well with
distance, and has problems if it does not, like with the "traps" you
mention.

I call a graph where distance matches perfectly with cost, a perfect
graph.

So in my terminology your example is a dis-correlated graph, where the
ratio of starting points that give the optimal solution to points that
do not gives the degree of correlation.

In this example, the number, I suppose is 1/4. I'm pretty sure a graph
matching my description comes out to be 0 under this scheme.

That would be an interesting counterexample.

I have suspicions for why your intuition is wrong in this case, but of
course, I want you to be wrong, so that doesn't say much.

But my thinking has to do with rotations in space (don't ask the
dimension), so that there is always an angle--if an optimal path
exists--that cuts through optimally, or maybe I'm just babbling.

Trouble with from scratch problem solving is it can take time, which
is why I sound differently this week than last, as last week, I'd just
come up with this approach. Kind of just came fully formed--why not
use two travelers with one going forward and one going backwards in
time?

So this entire algorithm is like a baby, and everything is fresh
ground as I slowly work my way through theories, implications, rough
guesses and complete b.s. in the hopes of getting an answer.


James Harris

.

Relevant Pages

  • Re: Minimum levenshtein distance for a set of words
    ... > | - set of all words which have the minimum distance if finite ... > The algorithm in there that perhaps comes closest to doing ... > smallest *total* distance to the given strings. ... For example for a set A with two elements and cost values all the same ...
    (sci.math)
  • Re: Distance normalized TSP algorithm
    ... Unless you are aiming for a probabilistic algorithm, ... graph, a perfect one. ... I call a graph where costs match well with distance a well correlated ... do not gives the degree of correlation. ...
    (comp.lang.java.programmer)
  • Re: Verizon Reduces Prices for Phone Service
    ... and the website still indicated it cost $6.95 per month until ... > add a very low rate long distance plan. ... I make a lot of local toll calls. ...
    (comp.dcom.telecom)
  • Re: Algorithm/Theory help: Patterns, comparing, calculating distance between?
    ... The definition and computation distances between strings is a heavily ... To get a handle on the literature, look for Levenshtein distance (check ... Then you find the minimum cost sequence of edits that are required to ... it is common to define a positive cost for each non-trivial edit ...
    (comp.ai)
  • Re: Food snob?
    ... Kind of like Skype; you have to ... It only costs money if you aren't going computer to computer, but it is really cheap, and isn't a monthly cost. ... distance is and that's your DSL bill. ... still isn't much (double that if you've got a crt). ...
    (rec.food.cooking)