Algorithm to Efficiently Search a Solution Space
-
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 a point passes, 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 “upper” pass points - for example, (1,5) could be a pass point in addition to (2,3). I've already gleaned that it's more efficient to search the solution space from high to low values, because if an "upper" point passes then there's no need to test the "lower" points. But any advice beyond that is greatly appreciated, thank you!
-
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 a point passes, 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 “upper” pass points - for example, (1,5) could be a pass point in addition to (2,3). I've already gleaned that it's more efficient to search the solution space from high to low values, because if an "upper" point passes then there's no need to test the "lower" points. But any advice beyond that is greatly appreciated, thank you!
-
Your description implies that the search needs to start from the end of the array and work back to the beginning. That is in the case described going from [9, 14] back to [0, 0]. But maybe that is not quite what you do mean.
It’s definitely more efficient to test points from high values to lows. For example, you always want to test point (5,8) before you test point (4,7) because if the former passes there’s no need to test the latter. But beyond that I’m lost on how to improve the efficiency of the search.
-
It’s definitely more efficient to test points from high values to lows. For example, you always want to test point (5,8) before you test point (4,7) because if the former passes there’s no need to test the latter. But beyond that I’m lost on how to improve the efficiency of the search.
-
That may be true, but your question is not clear (to me). Please edit your original post and add some more detail of what you are trying to do.
I edited the post to add more detail.
-
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 a point passes, 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 “upper” pass points - for example, (1,5) could be a pass point in addition to (2,3). I've already gleaned that it's more efficient to search the solution space from high to low values, because if an "upper" point passes then there's no need to test the "lower" points. But any advice beyond that is greatly appreciated, thank you!
-
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 a point passes, 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 “upper” pass points - for example, (1,5) could be a pass point in addition to (2,3). I've already gleaned that it's more efficient to search the solution space from high to low values, because if an "upper" point passes then there's no need to test the "lower" points. But any advice beyond that is greatly appreciated, thank you!
Second option, binary search along the diagonal, e.g. from (0,0), (1,1), ... (n,n) where n is min(max-x, max-y), until you find last pass. Call this point (p,p). If f(p+1, p) passes : binary search for last pass along x axis between [p+2...max-x]. Else if f(p,p+1) passes : binary search for last pass along the y axis between [p+2...max-y]. Else answer is (p,p) assuming I've understood your problem set correctly. If f is not too complex, and your data matrix is not large, then maybe a simple linear search is "good enough" wrt the above.
"A little song, a little dance, a little seltzer down your pants" Chuckles the clown