修改后的 Nearby School/Postoffice 示例的贪婪算法方法

Question

我一直在尝试解决我教授笔记中的练习题，但找不到最佳答案solution.The问题如下。

沿着一条东西向的街道，有 m public 所学校，到街道西端的距离分别为 S[1] < S[2] < … < S[m]。除了 m 所学校外，还有 n 栋房子，它们到街道西端的距离分别为 H[1] < H[2] < … < H[n]。目前，任何家庭的学生都可以在 200 米的步行距离内找到一所学校。现在，因为预算不足，我们希望关闭一些学校。请设计一个 O(n+m) 贪婪算法来 select 最少数量的学校开放，这样任何家庭仍然可以找到其中一所 select 步行距离内 200 米范围内的学校。你需要展示一个伪代码来证明你算法的正确性。

Answer 1

从问题的初始状态我们知道|S[1] - H[j]| <= 200，对于一些 j，所以我们可以从那里开始。

如果 |S[2] - H[j]| 我们选择放弃第一所学校<= 200，如果 |S[3] - H[j]|，我们将放弃第二所学校<= 200 ...等等等等。这个想法是贪心并最大化学校的覆盖范围，使其与需要覆盖的下一所房子的距离最大。

一般来说，对于S[i]的学校和H[j]的房子，如果|S[i+1] - H[j]|我们将放弃学校<= 200。如果 |S[i+1] - H[j]| > 200 然后我们将学校保持在 S[i] 并找到不在 S[i] 距离内的下一所房子。一旦所有的房子都被覆盖，算法就完成了。运行时间为 O(n+m)，因为在最坏的情况下我们迭代 S 和 H 一次。

为了证明正确性，您应该尝试考虑一个最优序列并证明您的贪心解决方案不会做得更差。例如。给定学校 O[1] < O[2] < ... < O[K] 的最优解和 G[1] < G[2] < ... < G[L] 的贪婪解，证明L <= K.

Answer 2

高层思考

首先，我们知道解决方案总是存在的，只要不移除任何学校。

对于最低限度的学校选择，我们换个角度思考：

For each house at h[i], think as a range [h[i]-200, h[i]+200] inclusively

因此，对于每个这样的范围，我们希望在 s[j] 找到一些学校，其中 h[i]-200 <= s[j] <= h[i]+200

由于h[]和s[]都排序了，我们从最左边的房子[h[0]-200, h[0]+200]来看，我们必须选择一所学校房子，直觉上，我们希望尽可能选择最右边的学校，因为这所学校更高的机会与下一所房子共享

这个想法在一般情况下是正确的：

For range h[i], we always want to choose school which is already chosen school by h[i-?], or the rightmost non chosen school

正确性

设一个解是一个有序的学校集S，用描述的方法找不到

让我们的贪心法找到的解决方案是一组有序的学校G

考虑 S[0] 和 G[0]、S[0] <= G[0]，因为我们会为第一所房子选择最合适的学校。那么要么

S[0] <= G[0] <= S[1]，我们可以用G[0]替换S[0]，它提供相同的集大小
S[0] < S[1] < ... < S[X] <= G[0] <= S[X+1]，我们可以将所有S[X] <= G[0]替换为G[0]，这提供了更小/更优化的尺寸

（是的，案例 1 确实是案例 2 的子案例）

对于这两种情况，删除 G[0] 和任何 S[X] <= G[0]，场景与两个缩减集相同，我们可以使用类似的参数，递归地，说 our贪婪的方法不会比任何可能的解决方案都差，这是最优的

伪代码

Pointer house_pointer = first house, school_pointer = first school;

for( each house ){
   if( NOT ( current school is chosen and within current house's range ) ){
       while(current school is NOT the rightmost school within range){
            school_pointer = current school = next school
       }
       mark current school chosen
   }
   house_pointer = next house
}

算法中好像有两个循环，也就是O(nm)，其实不然。对于这些使用两个指针遍历数组的结构类型（例如 KMP algorithm），通常您可以观察到每个元素被访问的 maximum # 次.

对于房子，因为每次迭代都会移动到下一个房子，每个房子最多被访问1次。

对于学校，由于指针只向前移动，不向后移动，所以每所学校最多也被访问1次，虽然不是均匀分布在每个房屋迭代中（取决于实现，有些学校可能访问2次但那不重要）

因此，结合两者，复杂度仍然是O(n+m)

修改后的 Nearby School/Postoffice 示例的贪婪算法方法

Greedy Algorithm approach to a modified Nearby School/Postoffice example

algorithm

greedy