4

在解决问题之前，让我先解释一些定义：

假设 A 点是一个坐标（可能有双精度值），例如 (1.2,3.5,4.3,2.6)，与 B 点相同。

A 点优于 B 点，当且仅当 1. A 点所有坐标 <= B 点所有坐标，且 2. A 点一个坐标 < B 点对应坐标

例如：给定

A=(2,3,4,5)
B=(2,3,4,6)

A 支配 B，因为条件 1 成立，并且对于条件 2，A 的第四个分量 < B 的第四个分量。

再举一个例子，

A=(2,3,4,5)
B=(2,3,4,5)

A 都不支配 B，反之亦然，因为条件 2 在两种情况下都不成立。

现在给定一个n维坐标列表，我希望找到不被其他人支配的坐标集合，这些坐标称为天际线集合。

假设我有 5 个维度的坐标

(2,1,2,1,2)
(1,2,1,2,1)
(3,3,3,3,3)
(4,4,4,4,4)

天际线集是

(2,1,2,1,2)
(1,2,1,2,1)

现在我想写一个函数：

List<double[]> SkylineSet(List<double[]> Coordinates, int dimension)

给定示例输入：

 List<double[]> newList=new List<double[]>();
 newList.Add(new double[] {2, 1, 2, 1, 2});
 newList.Add(new double[] { 1, 2, 1, 2, 1 });
 newList.Add(new double[] { 3, 3, 3, 3, 3 });
 newList.Add(new double[] { 4, 4, 4, 4, 4 });

SkylineSet(newList,5)将输出

(2,1,2,1,2)
(1,2,1,2,1)

这可以通过每个坐标的成对比较来实现，但是坐标的数量可能非常大，有人知道如何有效地解决这个问题吗？

4

2 回答 2

1

将这些点放在 KD 树（或一些这样的数据结构）中。现在，您可以有效地找到以给定点为主的点。删除那些占主导地位的，重复所有剩余的点。

于 2012-09-13T14:01:08.047 回答
0

我不确定这是否可行。这在我的脑海中似乎是合理的。也可能这正是您已经在做的事情。

建立一个支配矩阵 NxN，其中 N 是点数。矩阵中的值是“相等”、“支配”、“支配”、“都不”。将所有矩阵单元设置为“相等”。该矩阵保存算法结束时的结果。

从第一个坐标开始。

我在这里假设我们有一个数组，其中包含当前坐标的所有值，但也与它们相关的点。

建立部分支配关系，只看当前坐标。支配关系可以具有以下值之一：“平等”、“支配”、“支配”。没有“两者都没有”。

在双嵌套循环中运行此数组（I = 0，N-2；J = I+1，N-1）。给定两点的关系 R 和这两个点的关系矩阵中的单元格 C 将矩阵更新为新值 C，如下所示：

如果 C 是“相等的”，那么 C = R。
如果 C 是“都不”，那么它是不变的。
如果 C 是“支配的”并且 R 是“支配的”，则 C 变为“两者都不是”，否则不变。
如果 C 是“支配的”并且 R 是“支配的”，则 C 变为“两者都不是”，否则不变。

对所有坐标重复该过程，在矩阵中累积结果。

最后遍历每个点的矩阵。取所有与任何其他点没有“支配”关系的点。

于 2012-09-13T14:45:01.543 回答