1
$\begingroup$

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images with minimum possible number of guards.

My suggestion for an algorithm:

Place a guard at $x_1+0.5$ then loop from $i=2$ to $i=n$, if image $x_i$ is protected by the previous guard then do nothing, else place a new guard at point $x_i+0.5.$


I proved that my algorithm returns a valid solution, but am stuck on proving that it returns the minimum solution.

I am trying to prove this claim:

Let $s_i$ be the number of guards placed until and including the point $x_i + 0.5$ Then for each i there is an optimal solution which used exactly $s_i$ guards until and including the point $x_i + 0.5.$

I proved this in 3 pages in case the algorithm adds new guard in step $k$, and only now I discovered a HUGE problem in the induction. what if in step $k$ my algorithm didn't add a new guard?

How can I still prove that the optimal solution which is guaranteed for $k-1$ is still valid (I think in some cases it's not and we need to make some changes to it by moving some or all guards...)?

$\endgroup$
10
  • $\begingroup$ Do you mean that the $n$ images are placed on a line? $\endgroup$
    – phan801
    Jun 8 at 13:12
  • $\begingroup$ @phan801 yes I do $\endgroup$
    – coolmo
    Jun 8 at 15:59
  • $\begingroup$ Are you sure, you want to prove "minimal" and not "minimum"? $\endgroup$ Jun 8 at 17:03
  • 1
    $\begingroup$ Updated thanks for your note :) $\endgroup$
    – coolmo
    Jun 8 at 18:26
  • 1
    $\begingroup$ I can't tell what kind of answer you are looking for. I'm not sure how we're supposed to answer "What if?" Also that doesn't sound like a question for us to answer; it sounds like you identifying a flaw in your proof. I suggest spending some more time on identifying what the question you want answered is, and then organizing your post so that comes across clearly with no possibility of confusion. The easier you make it for readers to understand what you are asking, the more likely that you get a useful answer. $\endgroup$
    – D.W.
    Jun 8 at 20:42
2
$\begingroup$

Here is a simple reasoning that shows your greedy algorithm is correct. No mathematical induction is required.

Call an image critical if the greedy algorithm places a guard $0.5$ after it.

The algorithm ensures that each critical image is more than $1.5$ away from the previous critical image (except the first image, before which there is no image). That means any two critical images are more than $1.5$ apart.

Since a guard covers an interval of length $1.5$, it can cover at most one critical image. So, any solution must place at least as many guards as critical images. The greedy algorithm places exactly one guard for each critical image. So, the greedy algorithm is optimal.$\quad\checkmark$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.