1

考虑一个二维 m*n 网格，其中每个单元格可以包含 1 或 0。通过移动通过该网格找到遍历可以获得的最大值。可以通过对角线穿过 1 个单元格来增加该值。网格的遍历遵循以下规则：

  1. 从左上角的单元格开始。
  2. 在每个单元格处，遍历可以向下移动一个网格、向右移动一个网格或沿对角线移动（向下移动一个网格并向右移动一个网格）。如果单元格包含 1 并且遍历沿对角线移动，则遍历值增加 1。
  3. 遍历不能移出网格（如果在右边缘不能向右移动，如果在底部边缘不能向下移动）。
  4. 在右下角结束。

一个简单的算法会考虑所有 3*m*n 遍历并选择最大值。有人可以帮我想出更好的解决方案吗？有没有解决类似问题的算法？

这不是一个面试问题，我需要这个来尝试优化 Smith-Waterman 算法。

例子：

以下网格的最大值为 2：

在此处输入图像描述

这个最大值为 7：

在此处输入图像描述

4

3 回答 3

3

使用动态规划：

dp[i, j] = maximum value obtainable from [1, 1] to [i, j]
dp[1, _] = dp[_, 1] = 0 -> we cannot get to any of these diagonally
dp[i, j] = max(dp[i - 1, j], -> come from above
i, j > 1       dp[i, j - 1], -> come from the left
               dp[i - 1, j - 1] + v[i, j] -> come diagonally and add what is at [i, j]
              )

答案将在dp[m, n].

复杂度是O(n*m)，这是最优的，因为仅仅读取输入就需要这么多。

笔记：

一个简单的算法会考虑所有 3*m*n 遍历并选择最大值

这实际上应该是3 to the power of (n*m)，因为对于每个单元格，如果您强制使用它，您将有 3 种可能性。

于 2014-03-09T07:08:16.570 回答
1

您的问题可以转化为图形问题，其中顶点代表您的单元格，边代表相邻单元格或对角相邻单元格之间的可能连接。

你所有的边的权重都是 0，除了那些代表从 1 个单元格开始的对角线旅行。

您现在已将问题转换为有向无环图 (DAG) 上的最长路径问题。这等效于解决具有负等效权重的 DAG 上的最短路径问题（即所有权重为 1 的边都变为权重 -1）

对于具有负权重的 DAG 中的最短路径，请使用 Bellman-Ford 算法。http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

于 2014-03-25T15:48:19.877 回答
0

可能有一种方法可以递归地在对角线上进行分支，并智能地修剪最高值，但这种方法太复杂了。

我问了这个问题以获得可并行化的 Smith-Waterman 算法，最后我将使用这个http://biochem218.stanford.edu/Projects%202002/Byang.pdf

于 2014-03-09T23:23:54.283 回答