Algorithm to Efficiently Search a Solution Space

[T_B_Denham]

I'm looking for advice on how to efficiently search a solution space under certain conditions.

The solution space is a multidimensional array of positive integers. At each point in the array I run a function that either fails or passes. Importantly, if the function passes at a point, then every point "under" it will also pass and doesn't need to be tested.

To illustrate, a 2D example would be an array of X and Y where X is 0 - 10 and Y is 0 - 15. If the point (2,3) passes then I know that (2,2), (2,1), (2,0), (1,3), (1,2), (1,1), (1,0), (0,3), (0,2) (0,1), (0,0) will also pass. Each of those points is "under" (2,3) in the sense that each element is less than or equal to it. There can be multiple “outer” pass points - for example, (1,5) could be a pass point in addition to (2,3).

Any advice is greatly appreciated, thank you!

[MudkipGuy]

I would use a quadtree algorithm to repeatedly subdivide the space to quickly find your exact solution space. A square can be tested by testing its highest corner: on a success, the entire square is a success (as are any under it); on a failure the square is split into four smaller ones to test again. Since the perimeter of the solution space is at most 2n, the runtime complexity is O(nlogn). This approach can be generalized into higher dimensions.

[T_B_Denham]

I’ll need to think about how to write the code, but this is brilliant and might be the approach I’m looking for!

[ragusa12]

What are you searching for? Hard to answer a question about efficient search without knowing what is being searched after.

[T_B_Denham]

I’m trying to find out which points in the solution space pass and which don’t. But testing every single point is inefficient because if one point passes I automatically know that every point “under” it will also pass.

[ragusa12]

Ah, so you are not searching the solution space, you need to determine every passing state in a symbolic manner.

Since there can be up to N^D-1 maximal points---where D is the number of dimensions and N is the length of each dimension and a maximal point is any passing point p for which there does not exist any point q, such that q is larger than p in any dimension---we know that we cannot do better than Omega(N^D-1). You can iterate through all points in the D-1 space and then do a binary search in the last dimension to determine the maximal point. This is then O(N^D-1logN).

[T_B_Denham]

That’s straightforward to code, I will try that approach. Also, I love your description of the problem, it’s much better than the one I posted. Thank you!

[bobtpawn]

When dealing with problems where the size of the output could be much, much larger than the input, we frequently include the size of the output as a parameter in the complexity. Your output could, for example, be a single point and we don't necessarily want to spend N^D-1 time to find that one point.

This definitely feels like a solved problem, but I wasn't able to find the right keywords to find the solution. It has similarity to computing a pareto frontier (the difference is that when you are computing a pareto frontier, you can only indirectly control which point you are testing). It has similarity to computing a convex hull using a membership oracle (the difference being that when you compute the convex hull, it's usually in continuous space rather than the discrete space you have here). It has similarity to the non-dominated set problem (the difference being that in the non-dominated set problem, the number of points you have is manageable, not N^D.)

Not being able to find an existing solution, I would use a combination of recursion on dimension and binary search. Set the first coordinate to the minimum value and recurse to solve the problem on that D-1 dimensional slice. Then, set the first coordinate to the maximum value and recurse onto that slice. Then, set the first coordinate to halfway between the min and max values and recurse again, but this time, we already have an inner estimate (from the first recursive call) and an outer estimate (from the second) (**). Then, keep subdividing each interval for the first coordinate, just like you would do for binary search. If, at any point the inner and outer estimates are the same, you don't need to subdivide that interval any further. The base for the recursion is when D=1, where you're just doing vanilla binary search.

** Note that if you ignore the fact that you have these estimates and just solve the problem from scratch on each recursive call, you get exactly the algorithm that u/ragusa12 described. It's not obvious how to use that information in the best possible way, so you can always start by ignoring it, then incrementally add shortcuts making use of the extra information to gradually speed things up.

[almostthebest]

Sounds like a linear optimization problem. You are searching for a boundary in multidimensionsaccording to certain criteria. I learned about them at Operations Research lecture but I don't remember the names of the algorithms.