这个问题的贪心算法是什么，如何证明它是最优解？

Question

这个问题的贪心算法是什么，如何证明它是最优解？

3

细节有点尴尬，提前警告一下哈：我想在建筑物的地板上设置仪表来捕捉某个人。假设我的楼层是从0到长度L的数轴。我设计的具体类型的仪表探测半径在-x和+x方向上为4.7米（9.4米探测直径）。我想设置它们的方式是，如果我要找的人在楼层的任何地方踏上脚，我都会知道。但是，我不能随便设置仪表（这可能会惹恼其他居民）；因此，我只能在n个有效位置中设置一个仪表。另外，这些仪表很昂贵，制作也耗时，所以我想尽可能使用尽可能少的仪表。

为简单起见，您可以假设该仪表具有0宽度，并且每个有效位置就是上述数轴上的一个点。请问有什么贪心算法能够尽可能地使用尽可能少的仪表来监测整个长度为L的走廊，或者如果无法监测整个走廊，则对于我拥有的n个位置集合输出false呢？即使它无法监测整个走廊，它仍然会尽可能少地使用仪表。

- John Adams

你能举个例子说明你的问题吗？我有点难以理解。 - lier wu

@lierwu 他们可以，但如果我在每个位置都放置一个计量器，可能会太多了。这些都是有效的位置，我可以在这些位置放置计量器而不会打扰其他居民，但如果我不想在每个位置都放置计量器，仍然能够检测整个走廊。 - John Adams

我不想使用比必要更多的米数；那么在这种情况下，你想要真还是假？因为你也说过：“什么是贪心算法，可以尽可能少地放置仪表，同时能够检测到长度为L的整个走廊…” - lier wu

你说它会覆盖整个走廊，但我不认为它能覆盖到距离走廊末端13英尺的位置…… 你真的想要覆盖整个走廊吗？ - lier wu

@lierwu 如果算法在检测整个走廊的长度时放置尽可能少的米数，则返回true，如果在给定n个有效位置放置仪表的情况下无法检测到整个走廊的长度，则返回false。 - John Adams

显示剩余7条评论

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Answer 1

如果找到了最优解，为了证明您的解决方案是最优的，您只需要证明它能够找到字典序最后一个最优解。

而您可以通过对字典序最后一个最优解的大小进行归纳来实现。零长度地板和没有监视器的情况是微不足道的。否则，您要证明已经找到了字典序最后一个解的第一个元素。然后使用剩余元素覆盖其余部分即可完成归纳步骤。

技术说明：为了使此方法有效，您必须被允许在线路之外放置监测站。

- tucuxi · Answer 2

给定：

L（走廊长度）
一个包含 N 个有效位置的列表，用于放置半径为 4.7 的仪表（p_0 ... p_N-1）

您可以按照以下伪代码的方式，在 O(N) 时间内确定整个走廊的有效且最小（“好”）覆盖或证明在给定约束条件下不存在这样的覆盖：

// 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) 在没有 range 范围内的 candidates 时返回null，否则返回 candidates 中最后一个位置 p，使得 p <= start + range -- 并且还删除 p，和所有满足 p >= c 的候选项 c。

关键在于，通过始终选择将仪表放置在下一个位置，并且a) 不留空隙并b) 离上一个放置位置最远，我们同时创建了一个有效的覆盖（=没有空隙）和一个最佳覆盖（=没有可能使用更少的仪表进行有效的覆盖--因为我们的空隙已经尽可能宽）。在每次迭代中，我们要么完全解决问题，要么采用贪心策略来将其减少为（保证）较小的问题。

请注意，可能存在其他具有不同仪表位置的最佳覆盖，但它们将使用与此伪代码返回的仪表数量完全相同的数量。例如，如果您调整代码以从走廊的末端而不是从开头开始，则覆盖仍将很好，但间隙可能会重新排列。实际上，如果您需要字典序最小的最佳覆盖，则应使用从末尾开始放置仪表的适应算法：

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