<p>You problem is closely related to pareto optimal path computation in multi-criteria networks, e.g., as described in <a href="http://www.dbs.ifi.lmu.de/Publikationen/Papers/arXiv-SheJosSch14.pdf" rel="nofollow noreferrer">this paper</a>. </p>

<p>If you would just have one criteria (like distance) associated with each edge, then <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow noreferrer">Dijkstra</a> lets you quickly find all possible paths (optimizing distance). This is possible since you can "discard" a path that arrives at a node if another path reaching that node already has a lower distance.</p>

<p>The problem arises when you have two or more criteria (e.g., distance and reward) associated with each edge. Now, if two paths (starting form your start node) lead to the same node and path_1 has a lower distance than path_2, but path_2 has higher reward than path_1 you cannot discard either. However, if both criteria of a path are worse than in another path you are able to discard it. </p>

<p>One possible algorithm to do the complete search is described in <a href="http://www.dbs.ifi.lmu.de/Publikationen/Papers/arXiv-SheJosSch14.pdf" rel="nofollow noreferrer">the above paper</a>.</p>

<p><strong>Edit</strong></p>

<p>My answer above will not consider elements reappearing during the route. If you want to include this, you would have to know when and where elements reappear during route planning. This however, will make things a lot more complicated since you could achieve a higher reward by "waiting" for elements to respawn.</p>
Reasonably efficient algorithm for reward driven graph traversal
<p>I'm wondering if there is a more elegant solution to this problem.  The brute-force approach (depth-first search) is too computationally intensive.</p>

<p>You are given a network of nodes interconnected with paths.  Each path has a distance and zero or more elements along the path that can only be collected once every five minutes.  Collecting those elements increases your score.</p>

<p>The goal is to plan out the next five minutes of path traversal, keeping in mind the paths that have been traversed already in the last five minutes, so as to maximize the score increase.</p>

<p>The brute force algorithm is to try every possible route from the current location, avoiding places we have already been, stopping when we have traveled our max planning distance or time, and keep a virtual tally of rewards collected.  Then all we have to do is choose the route with the highest score.</p>

<p>Unfortunately, the number of nodes and paths in the graph is high enough that planning out even just five minutes worth of travel requires too much computation.  </p>

<p>Is there a known algorithm that solves this problem more efficiently than the brute-force method?  Even if it only finds an approximate solution, and not an optimal one.</p>

<p><strong>EDIT</strong></p>

<p>Thank you @SaiBot, here is my final solution, in case anyone should ever find themselves asking this same question:</p>

<p>I assigned every path, going from node A to node B, a unique ID.  The path from B to A had its own ID.  Outside the DFS search function but accessible to it, I kept a hash keyed by the ID, and the value consists of both the distance traveled prior to taking this path, and the size of the reward received so far.  To minimize extra work, I made sure that at each node, the outgoing paths were sorted shortest to longest.  Then, when the DFS algorithm was asked to evaluate a path it has evaluated before, the first thing it inspects is that cached result.  If the cached result arrived with:</p>

<pre><code>( reward &lt;= previous_reward &amp;&amp; distance &gt;= previous_distance )
|| reward / distance &lt;= previous_score
</code></pre>

<p>Then it is reasoned that there will be no benefit to recursing this path again, so it returns immediately with a score of 0 to immediately disqualify it from consideration.  Otherwise, it records the new incoming reward, distance, and score in the cache, and proceeds normally.</p>

<p>In addition, I did one other thing.  I reasoned that I wanted a certain amount of novelty in the path, meaning I didn't want it to just find one tiny little path that gets maximum reward, I wanted it to explore the map.  So I added a filter to outgoing nodes, saying that if the node has been visited in the past X minutes, remove it from consideration.  This had the side-effect of allowing the algorithm to route itself into a corner, so I added a fall-back, where if there were no available options, it would sort the outgoing paths by last visited, oldest first, and try in that order.  </p>

<p>The result was decent, but I'm going to do some more experiments to see if I can get even better results. </p>