I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.
The question I think I need the answer to: given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities? Alternatively, what is the smallest number of cameras I need to have 100% coverage of all points of interest? The latter is the real underlying form of the question, but the former may be an XY problem.
How do I optimize this problem?
My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:
Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could put cameras ("sentries").
Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.
I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.
My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. set([1,3,4])) or a numpy array that's a bitmask of targets viewable (e.g. numpy.array([False,True,False,True,True],dtype=bool)), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).
I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.
My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will always be preferred.
