Reply to thread

Message: [QUOTE="Patricia Shanahan, post: 3597566"] JSH wrote: .... .... This is the key difference between the NP-complete problems and problems with known polynomial time algorithms. There are a lot of problems that do have the property that the globally optimal solution must be a composition of a series of locally optimal solutions. For example, if the shortest path from X to Y includes node A, the path from X to A must be one of the shortest X to A paths. Polynomial time algorithms for shortest path calculation can use that fact to prune the search. Similarly, any subset of elements in a sorted list appear in sorted order. Sort algorithms such as quick sort and merge sort use that fact. In my favorite TSP example, an optimal solution must go between A and B via C, even though that route is far more expensive than the AB edge, and uses the most expensive edge connected to each of A and B. It has to be done because it is the least bad way of visiting C. A globally optimal TSP solution often requires choices that are not locally optimal. Many NP-complete problems, including TSP, have easy, well behaved cases that can be solved in polynomial time using locally optimal decisions. I don't think you should spend much time on those cases when designing a general algorithm. In general, an algorithm design that is not based on thinking about difficult cases of the problem it is supposed to solve probably won't work for them. The problem I have with understanding the utility of the two travelers is seeing how they influence each other in anything other than tiny problems. If you have e.g. 10,000 nodes, for the first 50 iterations each traveler bars less than 1% of the choices the other traveler could have made if you ran only one traveler. They may have already made at least one globally suboptimal choice long before the time the number of unvisited nodes is small enough that each traveler significantly constrains the other. At a more basic level, you seem to be running a simple greedy algorithm for each traveler, and I don't see anything to backtrack, look ahead, or otherwise ensure that locally suboptimal choices win if they are needed for the globally optimal solution. Patricia [/QUOTE]

Verification