这个问题的最小最优+证明的贪心算法是什么？

Question

细节有点尴尬，公平警告哈哈：

我想在我的大楼的地板上安装仪表来抓人；假设我的地板是从 0 到长度 L 的数字线。我正在设计的特定类型的仪表在 -x 和 +x 方向上的检测半径为 4.7 米（检测直径为 9.4 米）。我想以这样一种方式设置它们，如果我试图找到的人踩到地板上的任何地方，我就会知道。但是，我不能随便在任何地方设置一个电表（这可能会惹恼其他居民）；因此，我只能在 n 个有效位置设置仪表。另外，这些仪表制作起来又贵又费时，所以我想尽量少用。

为简单起见，您可以假设仪表的宽度为 0，并且每个有效位置只是上述数字线上的一个点。什么是尽可能少的贪婪算法，同时能够像我想要的那样检测长度为 L 的整个走廊，或者，如果检测整个走廊是不可能的，将为 n 个位置的集合输出 false我有（而且，如果它不能检测到整个走廊，在尝试这样做时仍然使用尽可能少的米）？

编辑：关于是否能够检测整个走廊的一些说明

Answer 1

要证明找到的解是最优的，您只需证明它找到了字典序上的最后一个最优解。

然后你通过归纳字典序上最后一个最优解的大小来做到这一点。零长度地板和没有监视器的情况是微不足道的。否则，您证明您找到了字典顺序最后一个解决方案的第一个元素。用剩余元素覆盖该行的其余部分是您的归纳步骤。

技术说明，要使其正常工作，您必须被允许将监控站放置在线路之外。

Answer 2

给定：

L（走廊长度）
用于放置半径为 4.7

p_0

p_N-1

您可以在 O(N) 中确定整个走廊的有效和最小（“良好”）覆盖物，或者证明在给定如下约束的情况下不存在此类覆盖物 (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);

其中 extractFurthestWithinRange(float start, List<Float> candidates, float range) returns null 如果在 start 的 range 内没有 candidates，或者 returns candidates 中的最后位置 p 使得 p <= start + range -- 并且还删除了 p，以及所有候选者 c 使得 p >= c.

这里的关键是，通过始终选择在 a) 不留间隙且 b) 离 previously-placed 位置最远的下一个位置放置仪表，我们同时创建了一个有效的覆盖 (=没有间隙）和最佳覆盖（=没有可能的有效覆盖可以使用更少的米 - 因为我们的间隙已经尽可能宽）。在每次迭代中，我们要么完全解决问题，要么贪婪地咬一口将其减少为（保证）较小的问题。

请注意，可以有 other 个具有不同仪表位置的最佳覆盖，但它们将使用与从 pseudo-code 返回的那些完全相同的仪表数。例如，如果您调整代码以从走廊的尽头开始而不是从一开始，覆盖物仍然很好，但可以重新排列间隙。事实上，如果你需要字典序最小的最优覆盖，你应该使用从末尾开始放置米的自适应算法：

// 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);

这个问题的最小最优+证明的贪心算法是什么？

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

algorithm

greedy