Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Re: Graph Traversal

by Fastolfe (Vicar)
on Nov 08, 2000 at 22:18 UTC ( #40589=note: print w/replies, xml ) Need Help??

in reply to Graph Traversal

This sounds exactly like a 'travelling salesman' problem. I don't have anything specific to offer you, but perhaps you can adapt some of the algorithms/research done against this to your own problem. Just s/distance/number of moves/.

Replies are listed 'Best First'.
RE: Re: Graph Traversal
by lhoward (Vicar) on Nov 08, 2000 at 22:23 UTC
    This problem has one feature that make is distinct from the classic TSP (Travelling Salesman Problem). In the TSP you must visit every node exactly once. Even if a node is very far away it must be visited. In my case I only need to visit as many nodes as possible in so many moves and can safely ignore nodes that are "too far away".

    I've tried adpoting spanning-tree approach to solving the TSP with moderate success. But I have already done better with an algorithm of my own.

      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.

        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! ;-)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://40589]
[Eily]: Easy, fetch the list of all the modules that are not on CPAN and remove the ones on Github
[Corion]: Eily: Sure, but I haven't written that yet ;)
[Eily]: wait, *keep* only the ones on Github, otherwise you'll still have an infinit list
[Eily]: Corion so until you write it, the module that lists the module that do not exist on CPAN should return itself
choroba has just learned how to tell a chemist from a blue collar

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2017-04-24 09:13 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (437 votes). Check out past polls.