No such thing as a small change PerlMonks

### Re: Graph Traversal

by tedv (Pilgrim)
 on Nov 08, 2000 at 23:46 UTC ( #40614=note: print w/replies, xml ) Need Help??

in reply to RE: Re: Graph Traversal

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.

-Ted

Replies are listed 'Best First'.
RE: Re: Graph Traversal
by Albannach (Prior) on Nov 09, 2000 at 00:09 UTC
Because you have only a limited number of moves, the importance of a single node is also a function of the importance of its neighbours, so that a nearby (to the player) but lonely oil node isn't as important as a more distant oil node that is itself near to other oil nodes.

This is starting to sound like some statistical clustering is in order, then you measure distances to the various clusters along with the maximum number of moves required to suck up all the oil in each cluster. You then increase the cluster sizes and choose the largest cluster you can reach.

Maybe I've just restated another posting, but I feel better! ;-)

Create A New User
Node Status?
node history
Node Type: note [id://40614]
help
Chatterbox?
 [LanX]: Jeez ... the new location for GPW so remote that hotels are cheaper than AirBnB oO

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (11)
As of 2018-03-19 11:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (239 votes). Check out past polls.

Notices?