Hi,

I am writing an algorithm to solve for a competitive dog sports friend. It is for a game called the "gambler", where you have a time constraint, and traversing an obstacle rewards points. You need to perform a course which maximizes points, and ends at a specific location, in the allocated time. You cannot take an obstacle more than twice, and you cannot take an obstacle twice in a row. Dog agility looks like this in video, and a course looks like this on paper

The problem turns out to be some evil mix of knapsack (maximize points in given time) and TSP (the current time cost for choosing a given obstacle depends on your position). Dynamic programming doesn't seem to work (except if you memoize every possible position at every possible time), and neither does Branch and Bound (there's no strong bound function that isn't either NP hard itself or extremely weak, because the problem comprises multiple NP hard problems itself).

The good news is that there never will be more than 25 obstacles and the time constraint will never be more than 50 seconds.

Here is a pastebin of my current algorithm in python, using numpy (I only use numba to jit the algorithm; completely optional), with example data. It works, but it's not particularly fast. The example data shows how the input data is formatted. Hopefully the comments are enough to explain. You should be able to paste this into a python console and get it running right away.

The algorithm does a divide-and-conquer brute force search, and uses a heuristic Branch-and-Bound technique, where we only search the x% closest obstacles at any iteration (so 100% would be a pure BFS).

I guess this would be parallelizable, but I'm not sure the gains would be significant.

Any help appreciated.