贪婪算法：机器人

Question

任何想法？我已经尝试将其绘制出来，并且缩小了您需要的最小数量的机器人，但我不知道如何用贪婪的算法表达它或如何证明它。这是我们讲课的一个额外问题，所以我们不必知道如何去做，但我觉得这是一个很好的练习。提前致谢！

Answer 1

until robot is at the bottom row: 
    while there's a coin to the right on the same row: 
     go right 
    go down one step 
go to the right corner 

或者更简洁：

If there are coins to the right: go right 
Otherwise: go down 

编辑： 要看到，该算法是在这个意义上最佳的，它需要机器人的最少总数量清除板，观察到没有机器人做出比最佳机器人差的举动：“贪婪保持领先”。这里试图使这个论点更加正式：

设G是贪婪算法，R是任何最优算法。

从单个机器人的角度来看，存在一定范围内的硬币S。例如，从起始位置开始，所有硬币都可以触及（尽管当然有些硬币可能是互斥的）。当机器人r进行移动时，S的子集V变得对r不可达。很明显，对于任何一次移动，只需要一个额外的机器人就可以将所有的硬币加入V.因此，在某种意义上，最坏的可能的个人移动将使得V不是空的，并且没有办法一次移动会导致算法需要两个或更多的附加机器人。对于G中的机器人，除非S为空，否则V总是S的真子集。换句话说，G不会做出任何“明显愚蠢”的动作。结合G和R收集所有硬币的事实，我们发现机器人不同的唯一有趣的地方就是他们在拍摄同一枚硬币后做出不同的选择（向下或向右）。

考虑R中的机器人r和G中的机器人在它们不同的地方。有两种可能性：

1. g正确，r下降。
2. g下降，r右转。

在第一种情况下，右侧有一个硬币，r下降。因此，在这一步V对于r来说不是空的，并且在前面的论证中，g的决定不会更糟。

在第二种情况下，右侧没有硬币，g下降。很显然，V对于g而言是空的，而r的决定不可能比这更好。

我们看到，在R和G不同的情况下，G至少和R一样好，这是最优的，因此G也必须是最优的。

Answer 2

我只是不知道如何表达它在一个贪婪算法

使用Manhattan/taxicab distance

那么贪心试探法可能是

• 任何机器人：

  1. 寻找最接近的硬币右下（使用出租车DIST min(deltaX, deltaY)）
  2. 收集它
  3. 从目前来看，从步骤1

就“退休”一个机器人看看再说在步骤1没有硬币。

Answer 3

距离使用曼哈顿距离。

While robot cannot move: 
    if robot is at right edge: 
     nextStep = down 
    if robot is at bottom edge: 
     nextStep = right 
    nextStep = F(right,down) 

F(right,down): 
    if(distanceAll(right)<distanceAll(down)) 
     return right 
    else return down 

distanceAll(location): 
    return the sum of distance between this location to remaining coins 

distanceAll可以是启发式函数，也许你可以定义一个范围来计算距离的总和。 5X5或3X3