Clear questions and runnable code
get the best and fastest answer
Re: Graph Traversalby tedv (Pilgrim)
|on Nov 08, 2000 at 23:46 UTC||Need Help??|
I don't think it's that different. It's just a weighting
problem with a threshold. Give each node a weight and
divide by distance and you have a rough heuristic for how
important it is to get there. Choose an appropriate threshold
and you've reduced it to the TSP. In theory, a slightly better
solution is to make a large graph and weight entire sections
of the graph (ie. groups of nodes). This tells you that 9
average nodes are better than 1 great node and 8 worthless ones.
But that's just another way of simplifying N nodes into 1 node,
and you still have to apply a heuristical threshold to end up
with a the TSP again.