Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
This is more of a general computer science/graph traversal question than a perl question; but I'm coding in perl and I know that this is a very smart crowd so I thought I'd see what help you could offer.

I've recently started playing the online game CashWars (note: this post is not a troll to get people to play CashWars, but if you do want to try it out, use the following link CashWars and I will get some nominal credit for refering you).

The game is played on a 721x721 grid. Every day you get so many moves (I'm currently at 350 per day, but you can have as many as 600). Moving 1 square horizontally or vertically costs 1 movement point. Certain squares contain resources (Oil) that you can gather. You can only gather resources from a particular square once per day. I have a large list of the squares that contain oil. What I am trying to do is compute an "optimal or near optimal path" to visit as many oil squares as possible in a given number of moves from a particular starting location.

I've already tried out a few algorithms:

  • weighting - I weigh each of the 4 squares adjacent to the current square based on some function of the distance from that square to nearby untapped squares with oil in them. I've tried a few diffrent weighting algorithms and this hueristic has worked ok.
  • spanning tree - I read that a spanning-tree algorithm can be used to produce a close-to-optimal solution to the Travelling Salesman Problem so I decided to give it a try. It did slightly better than the weighting algorithm, but I feel I could do better (since my problem isn't the classic TSP "visit every node in the minimum # of moves" problem, it is "visit as many nodes as possible in N moves" which is slightly diffrent and would lead to diffrent optimizations).
  • limited game tree - I store the 200 current best paths, then I add all possible moves to each one, and then rate the paths again; keeping only the 200 best out of that lot (best is determined by total path length to # of oil suqares ratio). This is the best algorithm so far, but I still feel that I can do better.
I'd like the other monk's thoughts about any other hueristics or algorithms that I could try that might give a good solution to this "visit as many X as possible in Y moves" problem.

I can post my code for any of those algorithms I've tried already if anyone is interested.


In reply to Graph Traversal by lhoward

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others romping around the Monastery: (5)
    As of 2015-07-04 02:18 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









      Results (57 votes), past polls