用于轻松查找最小值组合的算法/数据结构

Question

我有一个对称矩阵，如下图所示。

我编写了符号A.B，它表示网格点(A, B)处的值。此外，编写A.B.C 给出像这样的最小网格点值:MIN((A,B), (A,C), (B,C)).

另一个例子 A.B.D 给了我 MIN((A,B), (A,D), (B,D)).

我的目标是一次为一行找到所有字母组合(不重复)的最小值，例如对于这个例子，我需要找到关于 A 行的最小值，这些值由计算给出:

A.B = 6
A.C = 8
A.D = 4
A.B.C = MIN(6,8,6) = 6
A.B.D = MIN(6, 4, 4) = 4
A.C.D = MIN(8, 4, 2) = 2
A.B.C.D = 最小值(6, 8, 4, 6, 4, 2) = 2

我意识到某些计算可以重用，这随着矩阵大小的增加而变得越来越重要，但问题是找到实现这种重用的最有效方法。

能否为我指明正确的方向，以找到可用于此问题的高效算法/数据结构？

Answer 1

您需要考虑 lattice of subsets of the letters, ordered by inclusion .本质上，对于大小为 2 的每个子集 S(即，矩阵的每个非对角线元素 - 对角线元素似乎不会出现在您的问题中)，您都有一个值 f(S) ，问题是对于每个大小大于 2 的子集 T，找到 T 中包含的所有大小为 2 的 S 的最小 f(S)。(然后您只对包含特定元素“A”的集合 T 感兴趣 - 但我们暂时忽略它。)

首先，请注意，如果您有 n 个字母，这相当于询问 Omega (2^n) 个问题，每个子集大约一个。 (排除零元素和一元素子集以及那些不包含“A”的子集分别为您保存 n + 1 个集合和一个因子二，这对于 big Omega 是允许的。)因此，如果您想存储所有这些答案即使是中等大的 n，您也需要大量内存。如果您的应用程序中的 n 很大，那么最好存储一些预先计算的数据集合，并在需要特定数据点时进行一些计算；我还没有想过什么是最好的，但是例如只计算格中包含的二叉树的数据除了什么都不预先计算之外不一定对你有任何帮助。

考虑到这些问题，让我们假设您实际上想要计算所有答案并将其存储在内存中。您需要“逐层”计算这些，即从三元素子集开始(因为矩阵已经给出了二元素子集)，然后是四元素子集，然后是五元素子集，依此类推。这样，对于给定的子集 S，当我们计算 f(S) 时，我们已经计算了严格包含在 S 中的 T 的所有 f(T)。有几种方法可以利用它，但我认为最简单的可能是使用两个这样的子集 S:让 t1 和 t2 是 T 的两个不同元素，您可以随意选择；设 S 为删除 t1 和 t2 时得到的 T 的子集。 S加t1记为S1，S加t2记为S2。现在 T 中包含的每一对字母要么完全包含在 S1 中，要么完全包含在 S2 中，或者是 {t1, t2}。在您之前计算的值中查找 f(S1) 和 f(S2)，然后直接在矩阵中查找 f({t1, t2})，并存储 f(T) = 这 3 个数字中的最小值。

如果您从不为 t1 或 t2 选择“A”，那么您确实可以计算您感兴趣的所有内容，而无需为任何不包含“A”的集合 T 计算 f。 (这是可能的，因为只有当 T 至少包含三个元素时，上面概述的步骤才有意义。)好!这只剩下一个问题——如何存储计算值 f(T)。我要做的是使用 2^(n-1) 大小的数组；用 (n-1) 位数表示包含“A”的每个字母表子集，其中第 i+1 个字母在该集合中时第 i 位为 1(因此 0010110，设置了第 2、4 和 5 位，表示字母表“A”..“H”中的子集{“A”、“C”、“D”、“F”} - 注意我正在计算开始的位从右边 0 开始，字母从“A”开始 = 0)。这样，您实际上可以按数字顺序遍历集合，而无需考虑如何遍历 n 元素集的所有 k 元素子集。 (你确实需要包括一个特殊情况，当所考虑的集合有 0 或 1 个元素时，在这种情况下你什么都不做，或者有 2 个元素，在这种情况下你只需从矩阵中复制值。)