2

我将在下面以我想要的精确形式表达这个问题：

给定：两个浮点列表N且D长度相同k（k是 2 的倍数）。众所周知，对于所有人i=0,...,k-1来说，都存在j != i这样的情况D[j]*D[i] == N[i]*N[j]。（我使用从零开始的索引）

返回： 一个（长度k/2）对的列表，(i,j)例如D[j]*D[i] == N[i]*N[j]。返回的对可能不是唯一的（任何有效的对列表都可以）

该算法的应用是找到广义回文特征值问题的特征值的倒数对。等式条件等价于N[i]/D[i] == D[j]/N[j]，但也适用于分母为零的情况（这是一种确定的可能性）。特征值问题中的简并性导致配对不唯一。

更一般地说，该算法等价于：

给定X：长度列表k（k是 2 的倍数）。众所周知，对于 all i=0,...,k-1，存在j != i这样的IsMatch(X[i],X[j])返回 true ，其中IsMatch是一个布尔匹配函数，它保证至少j != i为 all之一返回 true i。

返回：一个（长度k/2）对列表，对于列表中(i,j)的IsMatch(i,j) == true所有对。返回的对可能不是唯一的（任何有效的对列表都可以）

显然，我的第一个问题可以用第二个问题来表述IsMatch(u,v) := { (u - 1/v) == 0 }。现在，由于浮点精度的限制，永远不会有完全相等，所以我想要最小化匹配错误的解决方案。换句话说，假设IsMatch(u,v)返回值u - 1/v并且我希望算法返回一个列表，IsMatch 为其返回最小的错误集。这是一个组合优化问题。我在想我可以先天真地计算所有可能的索引对i和之间的匹配错误j，但是我需要选择一组最小错误，我不知道该怎么做。

澄清

该IsMatch函数是自反的（IsMatch(a,b)暗示IsMatch(b,a)），但不是传递的。然而，它是 3-传递的：IsMatch(a,b) && IsMatch(b,c) && IsMatch(c,d)意味着IsMatch(a,d).

附录

这个问题显然是图论中的最小权重完美匹配问题。但是，就我而言，我知道应该有一个“好的”完美匹配，因此边缘权重的分布并不是完全随机的。我觉得应该以某种方式使用这些信息。现在的问题是，对于最小权重完美匹配问题是否有一个很好的实现，它使用我的先验知识在搜索的早期获得解决方案。我也对任何此类算法的简单实现持开放态度。

4

7 回答 7

1

我希望我有你的问题。

好吧，如果那样的IsMatch(i, j) and IsMatch(j, l)话IsMatch(i, l)。更一般地，该IsMatch关系是传递的、交换的和自反的，即。它是一个等价关系。该算法转换为列表中出现次数最多的元素（使用 IsMatch 而不是 =）。

于 2009-11-27T00:24:08.293 回答
0

（如果我理解问题......）这是匹配两个列表中每对产品的一种方法。

  1. 将每对 N 相乘，并将其与乘积以及构成乘积的元素的下标一起保存到一个结构中。
  2. 将每一对 D 相乘并将其保存到结构的第二个实例中，其中包含乘积，以及构成乘积的元素的下标。
  3. 对产品上的两个结构进行排序。
  4. 使合并类型通过两个排序的结构数组。每次从一个数组中找到一个与另一个数组足够接近的产品时，您可以记录每个排序列表中的两个下标以进行匹配。
  5. 您还可以将一个排序列表用于 ismatch 函数，对产品进行二进制搜索。
于 2009-11-27T01:45:17.680 回答
0

好。。将每一对D相乘，并将其保存到结构的第二个实例中，乘积，以及构成乘积的元素的下标。

于 2009-11-27T01:53:29.703 回答
0

我刚问了我的 CS 朋友，他想出了下面的算法。他在这里没有帐户（显然不愿意创建一个），但我认为他的答案值得分享。

// We will find the best match in the minimax sense; we will minimize
// the maximum matching error among all pairs. Alpha maintains a
// lower bound on the maximum matching error. We will raise Alpha until
// we find a solution. We assume MatchError returns an L_1 error.

// This first part finds the set of all possible alphas (which are
// the pairwise errors between all elements larger than maxi-min
// error.
Alpha = 0
For all i:
    min = Infinity
    For all j > i:
        AlphaSet.Insert(MatchError(i,j))
        if MatchError(i,j) < min
            min = MatchError(i,j)
    If min > Alpha
        Alpha = min

Remove all elements of AlphaSet smaller than Alpha

// This next part increases Alpha until we find a solution
While !AlphaSet.Empty()
    Alpha = AlphaSet.RemoveSmallest()
    sol = GetBoundedErrorSolution(Alpha)
    If sol != nil
        Return sol

// This is the definition of the helper function. It returns
// a solution with maximum matching error <= Alpha or nil if
// no such solution exists.
GetBoundedErrorSolution(Alpha) :=
    MaxAssignments = 0
    For all i:
        ValidAssignments[i] = empty set;
        For all j > i:
            if MatchError <= Alpha
                ValidAssignments[i].Insert(j)
                ValidAssignments[j].Insert(i)

        // ValidAssignments[i].Size() > 0 due to our choice of Alpha
        // in the outer loop

        If ValidAssignments[i].Size() > MaxAssignments
            MaxAssignments = ValidAssignments[i].Size()
    If MaxAssignments = 1
        return ValidAssignments
    Else
        G = graph(ValidAssignments)
        // G is an undirected graph whose vertices are all values of i
        // and edges between vertices if they have match error less
        // than or equal to Alpha
        If G has a perfect matching
            // Note that this part is NP-complete.
            Return the matching
        Else
            Return nil

它依赖于能够计算一个图的完美匹配，这是 NP 完全的，但至少它被简化为一个已知问题。预计该解决方案是 NP 完全的，但这没关系，因为实际上给定列表的大小非常小。我将等待几天的更好答案，或者等待有人扩展如何以合理的方式找到完美匹配。

于 2009-11-27T02:25:04.897 回答
0

你想找到 j 这样 D(i)*D(j) = N(i)*N(j) {我假设 * 是普通的实数乘法}

假设所有 N(i) 都是非零的，让

Z(i) = D(i)/N(i)。

问题：求 j，使得 Z(i) = 1/Z(j)。

将集合拆分为正面和负面并分别处理。

为了清楚起见，记录日志。z(i) = log Z(i)。

间接排序。例如，在排序视图中，您应该有类似 -5 -3 -1 +1 +3 +5 的内容。读出 +/- 对，这应该会给你原始索引。

我错过了什么，还是问题很容易？

于 2009-11-27T09:17:51.370 回答
0

好的，我最终使用了这个移植的 Fortran 代码，在这里我只需使用以下命令指定密集的上三角距离矩阵：

complex_t num = N[i]*N[j] - D[i]*D[j];
complex_t den1 = N[j]*D[i];
complex_t den2 = N[i]*D[j];
if(std::abs(den1) < std::abs(den2)){
    costs[j*(j-1)/2+i] = std::abs(-num/den2);
}else if(std::abs(den1) == 0){
    costs[j*(j-1)/2+i] = std::sqrt(std::numeric_limits<double>::max());
}else{
    costs[j*(j-1)/2+i] = std::abs(num/den1);
}

这很好用，对我的目的来说足够快。

于 2009-11-27T09:52:10.513 回答
0

您应该能够对 (D[i],N[i]) 对进行排序。您不需要除以零 - 您可以乘以，如下所示：

bool order(i,j) {
  float ni= N[i]; float di= D[i];
  if(di<0) { di*=-1; ni*=-1; }

  float nj= N[j]; float dj= D[j];
  if(dj<0) { dj*=-1; nj*=-1; }

  return ni*dj < nj*di;
}

然后，扫描排序列表找到两个分离点：（N == D）和（N == -D）；您可以从那里开始匹配互惠对，使用：

abs(D[i]*D[j]-N[i]*N[j])<epsilon

作为有效性检查。将 (N == 0) 和 (D == 0) 点留到最后；无论您认为它们是消极的还是积极的都没关系，因为它们都会相互匹配。

编辑：或者，您可以分别处理 (N==0) 和 (D==0) 案例，将它们从列表中删除。然后，您可以使用 (N[i]/D[i]) 对其余索引进行排序。您仍然可能希望从 1.0 和 -1.0 开始，以确保您可以将接近零的情况与完全为零的情况相匹配。

于 2009-11-27T11:39:22.133 回答