What is a greedy algorithm for this problem that is minimally optimal + proof?

user_14179436 0
Viewed 145

The details are a bit cringe, fair warning lol:

I want to set up meters on the floor of my building to catch someone; assume my floor is a number line from 0 to length L. The specific type of meter I am designing has a radius of detection that is 4.7 meters in the -x and +x direction (diameter of 9.4 meters of detection). I want to set them up in such a way that if the person I am trying to find steps foot anywhere in the floor, I will know. However, I can't just setup a meter anywhere (it may annoy other residents); therefore, there are only n valid locations that I can setup a meter. Additionally, these meters are expensive and time consuming to make, so I would like to use as few as possible.

For simplicity, you can assume the meter has 0 width, and that each valid location is just a point on the number line aformentioned. What is a greedy algorithm that places as few meters as possible, while being able to detect the entire hallway of length L like I want it to, or, if detecting the entire hallway is not possible, will output false for the set of n locations I have (and, if it isn't able to detect the whole hallway, still uses as few meters as possible while attempting to do so)?

Edit: some clarification on being able to detect the entire hallway or not

greedy algorithm
2 Answers

To prove that your solution is optimal if it is found, you merely have to prove that it finds the lexicographically last optimal solution.

And you do that by induction on the size of the lexicographically last optimal solution. The case of a zero length floor and no monitor is trivial. Otherwise you demonstrate that you found the first element of the lexicographically last solution. And covering the rest of the line with the remaining elements is your induction step.

Technical note, for this to work you have to be allowed to place monitoring stations outside of the line.

user_5854110

Given:

  • L (hallway length)
  • a list of N valid positions to place a meter (p_0 ... p_N-1) of radius 4.7

You can determine in O(N) either a valid and minimal ("good") covering of the whole hallway or a proof that no such covering exists given the constraints as follows (pseudo-code):

// total = total length; 
// start = current starting position, initially 0
// possible = list of possible meter positions
// placed = list of (optimal) meter placements, initially empty
boolean solve(float total, float start, List<Float> possible, List<Float> placed):

   if (total-start <= 0): 
        return true; // problem solved with no additional meters - woo!
   else:
        Float next = extractFurthestWithinRange(start, possible, 4.7);
        if (next == null):
             return false; // no way to cover end of hall: report failure
        else:
             placed.add(next); // placement decided
             return solve(total, next + 4.7, possible, placed);

Where extractFurthestWithinRange(float start, List<Float> candidates, float range) returns null if there are no candidates within range of start, or returns the last position p in candidates such that p <= start + range -- and also removes p, and all candidates c such that p >= c.

The key here is that, by always choosing to place a meter in the next position that a) leaves no gaps and b) is furthest from the previously-placed position we are simultaneously creating a valid covering (= no gaps) and an optimal covering (= no possible valid covering could have used less meters - because our gaps are already as wide as possible). At each iteration, we either completely solve the problem, or take a greedy bite to reduce it to a (guaranteed) smaller problem.

Note that there can be other optimal coverings with different meter positions, but they will use the exact same number of meters as those returned from this pseudo-code. For example, if you adapt the code to start from the end of the hallway instead of from the start, the covering would still be good, but the gaps could be rearranged. Indeed, if you need the lexicographically minimal optimal covering, you should use the adapted algorithm that places meters starting from the end:

// remaining = length (starts at hallway length)
// possible = positions to place meters at, starting by closest to end of hallway
// placed = positions where meters have been placed
boolean solve(float remaining, List<Float> possible, Queue<Float> placed):

   if (remaining <= 0): 
        return true; // problem solved with no additional meters - woo!
   else:
        // extracts points p up to and including p such that p >= remaining - range
        Float next = extractFurthestWithinRange2(remaining, possible, 4.7);
        if (next == null):
             return false; // no way to cover start of hall: report failure
        else:
             placed.add(next); // placement decided
             return solve(next - 4.7, possible, placed);
user_154720
Related