算法方法 - 寻找最佳路径在网格

问题：有一个米 X Ñ网格（ = M，N < = 500）。网格中的每个单元格包含k个硬币（k可能为负数或0）。你从0,0开始，到m-1，n-1，你可以向下移动1步或向右移动1步，收集尽可能多的硬币。如果k ，那么该特定单元格有一个强盗，你不能移动到该单元格。如果移动到相邻单元中的任何一个，您将被盗取k硬币。当您达到m-1，n-1时，您将拥有多少个硬币？算法方法 - 寻找最佳路径在网格

例如在网格：

0,23,20,-32 13,14,44,-44 23,19,41,9 46,27,20,0

ANS = 129（通过以下路径：0-13-23-46-27-20-0）

时限：5秒

我不认为这个程序可以使用动态编程来解决。而且我还没有研究过图论（可以用来解决这个问题）。简单的递归方法是我能想到的唯一的东西，在给定的约束下效率太低。

那么如何解决这个问题呢？不要只是发布代码，告诉我如何开始。如果它涉及图论，那么说明涉及哪个定理将是非常有用的。

来源

2012-08-25 Rushil

有趣的问题。这是一个家庭作业问题吗？如果是这样，你需要把它标记为家庭作业。该问题仍将由社区进行评估。 – HeatfanJohn

这不是一个家庭作业问题。我正在浏览一个codechef的编程竞赛问题，我遇到了这个问题。在它已经2天，但不能提出一个很好的解决方案。 :-( – Rushil

如果你在开始的网格的内容，它与加权边缘横跨问题的图表。 – msw

我不认为这个程序可以使用动态编程来解决。

为什么不呢？这是动态规划方法的主要候选者。

简单的递归方法是我能想到的唯一的东西，在给定的约束条件下效率太低。

你可以建立一个递归解决方案，例如，一个5x5网格？完善！从那开始，然后通过为您已经解决的单元格添加一个MxN阵列来获得最佳结果。用所有大的负值开始数组，然后在找到更好的解决方案时更新它。比那里已经有了。一旦你完成了单元格，将解决方案放入MxN数组中：下一次你递归到这里时，检查数组中是否有数字，如果有值，返回它，而不继续递归。

备忘解决方案本身相当简单。算法的预处理步骤（从相邻单元中减去负数）需要更多代码。

int solve(int r, int c) { 
    if(memo[r][c] != MIN) { 
     return memo[r][c]; 
    } 
    int res = grid[r][c]; 
    int a = 0, b = 0; 
    if (r+1 != R) { 
     a = solve(r+1, c); 
    } 
    if (c+1 != C) { 
     b = solve(r, c+1); 
    } 
    res = max(res+a, res+b); 
    return memo[r][c] = res; 
}

这里是ideone的解决方案，因为预期它返回129。

来源

2012-08-26 00:11:09 dasblinkenlight

当存在一个网格和多个查询时（通常你不需要再次计算相同的东西），通常memoization就可以工作。这里只有一个查询。这就是让我认为记忆不起作用的原因。 – Rushil

@Rushil这是不正确的：当DP工作时，记忆功能几乎可以工作。您也获得了多个查询：它们来自您自己的解决方案的递归调用。 – dasblinkenlight

@Rushil具体来说，天真的递归解决方案不够快，因为它一遍又一遍地解决了同样的问题。通过计算一次解决方案并存储它，您可以获得'O（M * N）'的时间复杂度。 – dasblinkenlight

对于weighted directed acyclic graph，您的问题被称为longest path problem。

当你到达（X，Y），你可以有硬币的数量最多的为：

coins(x,y) = max(coins(x-1,y), coins(x,y-1)) + change

这是一个recurrence relationship。它可以通过使用递归和记忆来获得性能，也可以通过使用迭代算法来解决。

迭代算法是一次处理一个对角线的网格。从0,0开始。然后计算0,1和1,0。然后是0,2和1,1和2,0。等等......

第1步：

0, ?, ?, ? 
?, ?, ?, ? 
?, ?, ?, ? 
?, ?, ?, ?

第2步：

0, 23, ?, ? 
13, ?, ?, ? 
?, ?, ?, ? 
?, ?, ?, ?

第3步：

0, 23,-33, ? 
13, 37, ?, ? // 37 because of max(23,13) + 14 
36, ?, ?, ? 
?, ?, ?, ?

等等

完成本过程中，答案是最底层的数字，右上角。

来源

2012-08-26 00:08:12

您的问题可以被描述为max-flow problem，因此可以通过Ford-Fulkerson-Algorithm来解决。

转型去如下：

删除负面节点，并从相邻小区减去其金额。
0/0将成为源，m-1，n-1接收器
每个节点连接到下一个和右侧，弧的容量等于其目标节点的值。
现在最大流量等于你可以有

有可能更容易解决硬币的最高金额，这仅仅是来到我的脑海里的第一件事。

编辑：dasblinkenlight在评论中指出，这是行不通的，因为流实际上是多个路径的组合，这当然不是我们想在这里。

来源

2012-08-26 00:10:09 Nick

找出最大流量是什么，我遇到的麻烦。看起来像算法几乎所有我需要的。谢谢！ – Rushil

我不认为这种情况下流量会起作用，因为Ford-Fulkerson会为您找到最适合您的路径，您可能会同时在多个有效路径上收集硬币。例如，如果流量网络的其余部分支持它并且产生的流量最大，那么该算法可以将流的一部分发送到右侧，并且部分流向下，但是这违背了问题的约束（您可以去对或者你可以下去，但你不能同时向右和向下）。 – dasblinkenlight

是的，在这种情况下，它不会工作。不过我会检查一下这个算法。 – Rushil

算法方法 - 寻找最佳路径在网格

回答

相关问题