0

我有一个超过 50,000 个点的数据库。每个点都有 3 个维度。让我们标记它们 [i,j,k]

我希望以其他方式寻找比其他点更好的点。

例如，对象 A [10 10 3]、对象 B[1 1 4]、对象 C[1 1 1]、对象 D[1 1 10]

那么所需的输出将是 A 和 D（因为 C 比它们都差，并且 B 在维度 [k] 中击败 A，但 D 在维度 [k] 中击败 B）

我尝试了一些基本的比较算法（即 if else 语句），这些算法在我减少数据库大小时确实有效。但是有 50,000，需要 10 多分钟才能找到所需的输出，这当然不是一个好的解决方案。

有人可以推荐我一两种方法来以最快的方式做到这一点吗？

谢谢

编辑：

谢谢 我想我明白了

4

3 回答 3

2

您正在寻找帕累托最优点。这些形成一个凸包。这在二维中最容易看到。使用迭代算法确定前 N 个点的帕累托最优点。对于 N=1，这只是第一点。对于 N=2，下一个点要么被第一个控制（丢弃第 2 个），控制第一个（丢弃第 1 个），位于左上方或右下方（因此也是帕累托最优）。

您可以通过保持凸包的简化上限和下限来加速分类，例如，仅单点{minX, minY, minZ}和{maxX, maxY, maxZ}. 如果P={x,y,z}由{minX, minY, minZ}then 支配，则到目前为止它由所有帕累托最优点支配并且可以被丢弃。如果 P 支配{maxX, maxY, maxZ}，它也支配了迄今为止帕累托最优的所有点，您可以丢弃所有这些点。

一个快速的 O(log N) 初始步骤是首先按 X 顺序对集合进行排序以找到最大 X 的点，然后 Y 找到最大 Y 的点，最后找到最大 Z 的点。在 ths 中找到帕累托最优点N=3 子集很容易，并且可以硬编码。然后，您可以将此集合用作第一个近似值。

一个更精细的解决方案是然后按X+Y、和排序X+Z，并找到这些最大值。同样，这产生了很好的初始候选点，因为它们将支配许多其他点。Y+ZX+Y+Z

例如，在您的情况下，按 X 排序和按 Y 排序都会产生点 A；按 Z 排序会产生 D 点，两者都不占优势，然后您可以快速丢弃 B 和 C。

于 2013-04-12T09:42:09.610 回答
2

您可以对代码进行许多优化：

{
vector<bool> isinterst(n, true);

for (int i=0; i<n; i++) {
  for (int j=0; j<n; j++) {


    if (isinterst[i]) {
        bool worseelsewhere=false;

        for (int k=0; k<d; k++)
        {
            if (point[i][k]<point[j][k])
            {
                worseelsewhere=true; 
                break;   //you can exit for loop if worseelsewhere is set to true
            }
        }                          
        if(worseelsewhere == false)
        {
              continue; //skip the rest if worseelsewhere is false
        }

        bool worse=true;
        for (int k=0; k<d; k++)
        {
            if (point[i][k]>point[j][k])
            {
                worse=false;
                break; //you can exit for loop if worse is set to false
            }
        }

        if (worseelsewhere && worse) {
            isinterst[i]=false;
            //cout << i << " Not desirable " << endl; 
            }
        }
    }
}
于 2013-04-12T04:51:38.153 回答
1

在不知道您对“更好”的定义的情况下，在这里提出具体建议有点困难。但是，我注意到您似乎在使用空间数据。处理空间数据时经常使用的数据结构是 R-Tree ( http://en.wikipedia.org/wiki/R-tree )。这为多维信息提供了有效的索引。

也许 boost::geometry 库有一些可以提供帮助的工具：http: //www.boost.org/doc/libs/1_53_0/libs/geometry/doc/html/geometry/introduction.html

于 2013-04-12T07:27:57.277 回答