问贪心算法最小基准点

EN

为了证明贪心算法的正确性，我们必须证明它产生有效解，具有贪婪选择性质，并且问题有最优子结构。贪婪的选择属性表明，算法做出的第一个决策始终可以是最优解中的一个选择。最优子结构是指给定问题的最优解包含每个子问题的最优解。

对于这个答案，我将假设您只能在房子里放置一个配电箱，而不是放在它们之间。我还假设每一所房子最多与它相邻的房子相距d。

假设current_distance是到前一个盒子的距离(或到算法开始时街道上第一个房子的距离)

虽然有些房子没有电，但(current_distance <= d)如果我们可以在离最后一个盒子超过d之前搬到下一个房子(即current_distance + distance_to_next_house <= d)，那么就搬到下一个房子，否则在当前房子里放一个盒子

本质上，这个算法所做的是尽可能远离前一个盒子，然后放置一个新的盒子。然后，它从最后一个盒子尽可能远地移动，并重复，直到所有的房子都在配电箱的d个范围内。

首先，让我们确保我们的解决方案是有效的，并为每个家庭提供电力。假设它是无效的，并且至少有一个房子hi距离放置在hk的配电箱x，其中x> d。因为hi和hk之间的距离大于d，我们知道在它们之间必须至少有一个房子hj，使得hi和hj <= d之间的距离。因为我们的算法只会将一个盒子放置在离前一个盒子<= d的房子上，我们知道这是不可能的，我们的算法将总是产生一个有效的解决方案。

接下来，让我们证明贪婪的选择性质。假设O是放置盒子的房屋的最优解集合，使得大小(O)最小。假设O中的第一个盒子o1与我们的算法选择的h1不在同一个房子里。我们知道h1比o1在这条街上更远，因为我们的算法总是选择最远的房子来放置盒子。我们还知道从o1到o2的距离小于或等于d，让我们称这个距离为d0。因为h1比o1沿着这条街走得更远，所以我们知道h1和o2 (称之为dh)之间的距离小于du。这意味着dh < du <= d.因此，我们可以用h1替换o1，这意味着我们的算法的第一选择总是最优解中的一个选择。我们已经证明了贪婪选择性质。

最后，让我们证明这个问题有最优子结构。我们可以通过证明对于任何放置的盒子，我们的算法将进一步下降，或者在街道上的同一位置，作为任何最优解。在我们证明这一点之后，我们必须证明我们的算法解的大小与最优解的大小相同。让最优解称为O(其中为一个盒子选择的每个房子是01，o2，...，on)，让我们的算法创建的解决方案称为H(其中每个房子是h1，h2，...，hn)。

我们知道我们的第一选择总是最优解决方案的一部分，所以h1必须总是比o1走得更远，或者是在同一座房子里。假设hk比ok走得更远，或者和ok在同一座房子里。现在让我们证明hk+1一定比ok+1在街上更远或者在同一点。假设这不是真的，ok+1比hk+1走得更远。设dx表示ok和ok+1之间的距离，dy表示hk和hk+1之间的距离，dz表示hk+1和ok+1之间的距离。我们知道dx <= d。我们也知道dy +dz <= dx，因此dy + dz <= d，所以我们的算法不会在hk+1停止，至少会继续到ok+1。因此hk+1必须在相同的点，或者比ok+1更远。

我们知道大小(H)不能小于大小(O)，因为O是最优解。为了证明size(O) = size(H)，首先假设size(O) < size(H)。我们知道，对于任何k，hk等于或大于ok。然而，我们的集合的大小大于O的大小，所以我们必须在hk之后放置额外的盒子。现在假设k=size( O )，所以ok是O中最后一个有盒子的房子。我们知道ok和街道上最后一个房子(称为dz)之间的距离小于或等于d。但由于我们的算法总是在最优解之前或等于最优解，我们知道hk和街道上最后一个房子(dh)之间的距离必须小于或等于dz。这意味着我们的算法不会在hk和最后的房子之间放置一个盒子，H的大小等于O的大小，然后是最小的大小。

在这里，我们已经证明了我们的算法产生了一个有效的答案，具有贪婪的选择特性，并且具有最优子结构。因此，我们已经为这个问题产生了一个正确的算法。