Re: Graph Traversal
by nop (Hermit) on Nov 08, 2000 at 23:53 UTC
|
All this effort for a game?!?
But since the problem
is interesting...
As the problem is certainly NP, try hueristics.
Simulated annealing, GAs, tabu search; whatever. The hard part is how you encode the problem. One clever way uses a sort sequence:
- Each depot gets an key, a float between 0 and 1
- To determine a tour, sort the depots by key
- Visit the depots in sorted-by-key order. Return to base (closing the loop) as late as possible (eg going to one more depot would leave you insufficient moves to get home).
Start by randomly assigning keys. Your original tour will be horrible. Improve the tour by any optimization hueristic (annealing, tabu, genetic algs) with reasonable mutuation operators such as
- randomly swap the keys of two depots
- randomly peturb the keys of some depots
- randomly "cross-over" two tours, by taking key values from each
The nice thing about the encoding is that it creates/maintains good subtours, and is robust to mutations
(every list of keys is a well-formed tour).
I've used this approach in a machine-scheduling problem with good results. Easily coded, unlike breaking out the heavy machinery of integer programming. Good luck.
nop
| [reply] [Watch: Dir/Any] |
Travelling Salesman Problems
by tedv (Pilgrim) on Nov 08, 2000 at 23:40 UTC
|
If you want some good insight into travelling salesman
problems, try playing the board game Elflands by Alan Moon.
I've only played it a few times, but I'm sure that after
10 games, I'd have a much better feel for coming up with
an adequate TSP solution. Note that the perfect TSP solution
is an NP complete problem, so don't aim for the optimal
solution. Aim for "good enough".
-Ted | [reply] [Watch: Dir/Any] |
Re: Graph Traversal
by Fastolfe (Vicar) on Nov 08, 2000 at 22:18 UTC
|
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/. | [reply] [Watch: Dir/Any] [d/l] |
|
| [reply] [Watch: Dir/Any] |
|
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
| [reply] [Watch: Dir/Any] |
|
Re: Graph Traversal
by brick (Sexton) on Nov 09, 2000 at 01:38 UTC
|
I worked on a vaguely similar problem--nodes-path-ish--and
we ended up making a tree of paths, sorting it depthwise and
breadthwise and then finding an optimized path. You may want
to consider looking at the discrete computing stuff, things
isomorphisms and node graphing. There's a red book with white
webs all over the cover, who's author I can't remember. The
title is something like -Discrete Algorithms-; it was pretty
helpful.
-B. | [reply] [Watch: Dir/Any] |
RE: Graph Traversal
by Blue (Hermit) on Nov 09, 2000 at 00:54 UTC
|
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] |
Automate it all!
by orkysoft (Friar) on Nov 08, 2000 at 23:20 UTC
|
While you're at it, give it a HTTP-client interface to save yourself a couple of hours of your time. Cashwars is boring, even with only the standard (200? 50? I can't recall, I quit when I went on holiday to Canada :-) moves per day. | [reply] [Watch: Dir/Any] |
|
Actually, the programs that I have work with
CashBrowser.
Cahsbrowser is a
UI for CashWars that makes it much easier to play
(it has a visual map of the game, you can move to a location by
clicking on it and it'll move you there across multiple squares, etc...). My programs load the map file that CashBrowser produces.
My program then produces as "automover" file (basically a list of waypoints) that CashBrowser
can load and uses to do all its movement. I just start up CashBrowser once a day and let
it do all the work. What I'm working on is generating a better file
for the automover to use.
| [reply] [Watch: Dir/Any] |
|
Cool, this sounds like a good "Free Lunch" thingy for those who have bandwidth >:-> >:-> >:->
But how much time will it take to figure out how it all works, eh?
| [reply] [Watch: Dir/Any] |
|
|
Re: Graph Traversal
by MadraghRua (Vicar) on Nov 11, 2000 at 02:45 UTC
|
Another alternative is to try a non-hierarchical binning approach. Use euclidian distances as a means of measuring distances between your grid, bin your distances in terms of distance between your important grids. Select the bin with the least travel cost, hopefully meaning it is optimized. You could use successive series of nodes to organize your moevments and help cut down on travel costs
Just do a web search on non-hierarchical analysis...
MadraghRua yet another biologist hacking perl.... | [reply] [Watch: Dir/Any] |
Re: Graph Traversal
by Anonymous Monk on Jun 26, 2009 at 17:53 UTC
|
One possible hurestic and can be modeled as gravitational pull between all resource and current location.
Like comet gets attracted to large bodies. | [reply] [Watch: Dir/Any] |