我正在尝试想出一种动态编程算法,在由相同数字组成的矩阵中找到最大的子矩阵:
示例:
{5 5 8}
{5 5 7}
{3 4 1}答:4个元素由矩阵决定
5 5
5 5 发布于 2011-10-15 05:41:30
这是一个我已经回答了here (和here,修改后的版本)的问题。在这两种情况下,算法都适用于二进制情况(0和1),但对任意数字的修改非常容易(但很抱歉,我将图像保存为问题的二进制版本)。你可以通过两次遍历O(n) time算法-n是元素的数量-来非常有效地做到这一点。然而,这不是一个动态编程-我认为在这里使用动态编程最终将是笨拙和低效的,因为问题分解的困难,正如OP提到的-除非它是一个家庭作业-但在这种情况下,你可以尝试通过这个算法来留下深刻的印象:-)因为显然没有比O(n)更快的解决方案了。
算法(图片描述二进制情况)
假设你想找到自由(白色)元素的最大矩形。

这里遵循两遍线性O(n) time算法(n是元素数):
1)在第一遍中,从下到上按列排列,对于每个元素,表示直到此元素可用的连续元素的数量:

重复,直到:

图片描述了二进制情况。在任意数的情况下,您持有2个矩阵-第一个是原始数字,第二个是上图中填充的辅助数字。您必须检查原始矩阵,如果您发现一个与前一个不同的数字,您只需从1重新开始编号(在辅助矩阵中)。
2)在第二遍中,你按行走,保存潜在矩形的数据结构,即包含当前位置在顶部边缘的矩形。见下图(当前位置为红色,3个可能的矩形-紫色高度1,绿色高度2和黄色高度3):

对于每个矩形,我们保持它的高度k和它的左边缘。换句话说,我们跟踪高度为>= k (即高度为k的潜在矩形)的连续数字的总和。这种数据结构可以用双向链表链接占用项的数组来表示,并且数组的大小会受到矩阵高度的限制。
第二遍伪码(非二进制版本,任意数字):
var m[] // original matrix
var aux[] // auxiliary matrix filled in the 1st pass
var rect[] // array of potential rectangles, indexed by their height
// the occupied items are also linked in double linked list,
// ordered by height
foreach row = 1..N // go by rows
foreach col = 1..M
if (col > 1 AND m[row, col] != m[row, col - 1]) // new number
close_potential_rectangles_higher_than(0); // close all rectangles
height = aux[row, col] // maximal height possible at current position
if (!rect[height]) { // rectangle with height does not exist
create rect[height] // open new rectangle
if (rect[height].next) // rectangle with nearest higher height
// if it exists, start from its left edge
rect[height].left_col = rect[height].next.left_col
else
rect[height].left_col = col;
}
close_potential_rectangles_higher_than(height)
end for // end row
close_potential_rectangles_higher_than(0);
// end of row -> close all rect., supposing col is M+1 now!
end for // end matrix关闭矩形的函数:
function close_potential_rectangles_higher_than(height)
close_r = rectangle with highest height (last item in dll)
while (close_r.height > height) { // higher? close it
area = close_r.height * (col - close_r.left_col)
if (area > max_area) { // we have maximal rectangle!
max_area = area
max_topleft = [row, close_r.left_col]
max_bottomright = [row + height - 1, col - 1]
}
close_r = close_r.prev
// remove the rectangle close_r from the double linked list
}
end function这样你也可以得到所有的最大矩形。所以最后你会得到:

那么复杂性会是什么呢?您可以看到,函数close_potential_rectangles_higher_than是每个闭合矩形的O(1)。因为我们最多为每个字段创建1个潜在矩形,所以在特定行中出现的潜在矩形的总数永远不会大于该行的长度。因此,这个函数的复杂性是O(1)摊销的!
所以整个复杂度是O(n),其中n是矩阵元素的数量。
发布于 2011-10-15 06:04:50
动态解决方案:
定义一个新的矩阵A,它将在A[i,j]中存储两个值:最大的子矩阵的宽度和高度与左上角的i,j,填充这个矩阵从右下角开始,按行从下到上。你会发现四种情况:
情况1:原始矩阵中的右下相邻元素都不等于当前元素,即:M[i,j] != M[i+1,j] and M[i,j] != M[i,j+1]为原始矩阵的M,此时A[i,j]的值为1x1
案例2:右边的相邻元素与当前元素相同,但底部的元素不同,A[i,j].width的值是A[i+1,j].width+1和A[i,j].height=1
情况3:底部的相邻元素相等,但右侧的元素不同,A[i,j].width=1, A[i,j].height=A[i,j+1].height+1
案例4:两个邻居是相等的:A[i,j].width = min(A[i+1,j].width+1,A[i,j+1].width)和A[i,j].height = min(A[i,j+1]+1,A[i+1,j])
位于i,j左上角的最大矩阵的大小为A[i,j].width*A[i,j].height,因此您可以更新在计算A[i,j]时找到的最大值
底部的行元素和最右侧的列元素被视为其底部和右侧的相邻元素不同
在您的示例中,生成的矩阵A将为:
{2:2 1:2 1:1}
{2:1 1:1 1:1}
{1:1 1:1 1:1}being w:h width:height
发布于 2014-07-15 13:01:56
对上述答案的修改:
定义一个新的矩阵A,它将在Ai,j中存储两个值:最大的子矩阵的宽度和高度,其中左上角在i,j处,从右下角开始填充这个矩阵,从下到上按行填充。你会发现四种情况:
情况1:原始矩阵的右下相邻元素都不等于当前元素,即: Mi,j != Mi+1,j和Mi,j != Mi,j+1为M为原始矩阵,此时Ai,j的值为1x1
案例2:右边的相邻元素与当前元素相同,但底部元素不同,Ai,j.width的值是Ai+1,j.width+1,Ai,j.height=1
情况3:底部的相邻元素相等,但右边的元素不同,Ai,j.width=1,Ai,j.height=Ai,j+1.height+1
情况4:两个邻居相等:考虑三个矩形:1.Ai,j.width=Ai,j+1.width+1;Ai,j.height=1;
在上述三种情况下,面积最大的一个将被视为表示此位置的矩形。
左上角在i,j处的最大矩阵的大小是Ai,j.width*Ai,j.height,因此您可以更新在计算Ai,j时找到的最大值
底部的行和最右侧的列元素被视为它们分别位于底部和右侧的邻居是不同的。
https://stackoverflow.com/questions/7770945
复制相似问题