Reply to thread

Message: [QUOTE="Patricia Shanahan, post: 3596824"] JSH wrote: .... I believe that my original example is well-formulated according to the rules you are now using. To save everyone digging back through the depths of the previous thread, I'll repeat it here: "Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to B is the same cost as B to A. C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1." You don't specify any criteria for picking the first node, so I assume the algorithm is supposed to work regardless of that choice. Suppose they start, in my example, at A. As far as I can tell, this procedure would result in T_1 and T_2 moving from A to two distinct nodes chosen from {B, D, E}. Each of those moves has cost 1. However, any path that contains e.g. both AB and DA would not be able to use AC. Since C has only two cost 1000 edges, not using one of them forces use of at least one of the cost 2000 edges. Such a path would have cost either 3003 or 4003. If I am misinterpreting your algorithm, please supply pseudo-code or other specification, including how you choose the starting node. An optimal path, such as ACBDEA, has total cost 2003, but that can only be achieved if T_1 or T_2, starting at A, choses to go to C, at a cost of 1000, rather than to B, D, or E at a cost of 1. How would either T_1 or T_2 know that a cost 1000 move is better for the overall solution than a cost 1 move? The core difficulty in the NP-complete problems is that making a series of locally optimal choices cannot be depended on to lead to a globally optimal solution. Patricia [/QUOTE]

Verification