在每个给定区域找到最小值的有效方法

Question

给出一个 我们首先定义两个实值函数 和 如下:

我们还m(X)为每个矩阵定义一个值,X如下所示:

现在给出一个 ,我们有很多地区G,表示为.这里,G由子矩阵形成的区域是G从一些列和一些行中随机选择的G.我们的问题是计算尽可能少的操作.有没有像构建哈希表或排序以更快地获得结果的方法？谢谢!

========================

例如,如果G={{1,2,3},{4,5,6},{7,8,9}},那么

G_1 could be {{1,2},{7,8}}
G_2 could be {{1,3},{4,6},{7,9}}
G_3 could be {{5,6},{8,9}}

=======================

目前,对于每个G_i我们需要mxn比较来计算m(G_i).因此,m(G_1),...,m(G_r)应该有rxmxn比较.但是,我可以注意到G_i并且G_j可能重叠,因此会有一些更有效的方法.任何关注都将受到高度赞赏!

Answer 1

根据需要最小/最大类型数据的次数，您可以考虑一个矩阵，该矩阵在矩阵值之间保存最小/最大信息，即在值之间的间隙中。因此，对于您的示例 G={{1 ,2,3},{4,5,6},{7,8,9}} 我们将定义一个关系矩阵 R 大小为 ((mxn),(mxn),(mxn)) 并具有来自集合 C 的值= {-1 = 小于，0 = 等于，1 = 大于}。

R 将有九个关系对 (n,1)、(n,2) 到 (n,9)，其中每个值都是 C 的成员。注意（n,n 已定义且等于 0）。因此，R[4,,) = (1,1,1,0,-1,-1,-1,-1,-1)。现在考虑您的任何子集 G_1 ...，了解子集成员的位置关系将为您提供 R 中的偏移量，这将解析为每个 R(N,,) 的索引，这将直接返回所需的关系信息而无需比较。

当然，您必须决定构建 R 的空间和计算开销是否超过每次需要时计算所需内容的成本。某些优化包括认识到 R 矩阵沿主对角线反射，以及您可以声明“等于”，例如小于（意味着 C 只有两个值）。根据原始矩阵 G，如果知道行或列已排序，则可以进行其他优化。

由于某些计算机（大型机、超级计算机等）以列优先顺序将数据存储到 RAM 中，因此存储数据集时，它会填充转置的行和列，从而允许列到列类型操作（向量计算）实际上青睐专栏。检查你的架构。