贪心算法：机器人

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

编辑：要从需要最少的机器人总数来清除棋盘的意义上看出该算法是最优的，观察没有机器人做出比最优机器人更差的移动："greedy stays ahead"。这是使这个论点更正式的尝试：

设G为贪心算法，R为任意最优算法。

从单个机器人的角度来看，有一组S组硬币触手可及。例如，从起始位置开始，所有硬币都触手可及（当然，有些硬币可能是相互排斥的）。当机器人 r 移动时，S 的子集 V 对 r 来说变得不可到达。很明显，对于任何一次移动，只需要一个额外的机器人来拿走 V 中的所有硬币。因此在某种意义上，最糟糕的可能的个人移动将是 V 不为空，并且没有办法进行一次移动会导致算法需要两个或更多额外的机器人。

对于 G 中的机器人，除非 S 为空，否则 V 始终是 S 的真子集。换句话说，G 不会进行任何 "obviously stupid" 移动。结合 G 和 R 收集所有硬币的事实，我们看到机器人唯一不同的有趣地方是他们在拿走同一枚硬币后做出不同的选择（向下或向右）。

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

g 向右，r 向下。
g向下，r向右。

第一种情况，右边有一枚硬币，r往下走。因此，在该步骤中，对于 r，V 不为空，并且根据前面的论点，g 的决定不会更糟。

第二种情况，右边没有硬币，g往下走。很明显V对于g是空的，r的决定再好不过了

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

Answer 2

I just don't know how to express it in a greedy algorithm

使用Manhattan/taxicab distance

那么贪婪的启发式可能是

对于任何机器人：
1. 寻找right-down最近的硬币（使用taxicab dist min(deltaX, deltaY)）
2. 收藏起来
3. 从当前点开始，从步骤1开始重复

只是 "retire" 一个在第 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

贪心算法：机器人

Greedy Algorithm: The Robot

algorithm

pseudocode

greedy