Reply to thread

Message

[QUOTE="Joshua Cranmer, post: 3597139"]
As Patricia points out, this breaks down in at least one case. The case 
is this (graphically put):
       ¢
    A --- B
$ / \ $ / \ $
  /   \$/   \
* --- C --- *
   $$$   $$$

In short, if C is a node with expensive connections to all but A and B 
(which are of moderate expense), while A and B both have cheap 
connections to everywhere but C, and even cheaper between the two of 
them, then the traveler will see get to one of A or B, find the cheapest 
one to be the other one, move to it, and then move back out into the 
rest of the graph, cutting off the cheapest connections to C.

The example Patricia gave violated the Triangle Inequality, but looking 
at the example I have, it is very likely that it fails even if you 
assume the Triangle Inequality (I haven't done any analysis as extensive 
of Patricia).

This, by the way, illustrates the danger of NP-hard problems: when you 
come to a choice, the "best" solution at the onset can lead you into 
pitfalls. Which means that you have to take into account not only the 
cost of moving from one node to another but the loss of savings in not 
moving to a third one (if that makes any sense).

Three unvisited nodes or three nodes including the ones T_1 and T_2 are on?

One exclamation point suffices. I understand it sufficiently to reason 
on it, and I could probably code it up reasonably fast if I cared to. 
It's still ill-formed: you don't mention what to do in case of ties.
[/QUOTE]

Verification