最大超体积单纯形算法

Question

给定一组 D 维空间中的点。找到最大可能 D-simplex 的最佳算法是什么，其所有顶点都在集合中？从代数上讲，这意味着我们必须找到 D + 1 点的子集，例如 D * D 矩阵的行列式，它由作为坐标增量的行构成，每个第一个 < strong>D 点和最后的 D + 1-st 点，在集合上具有最大可能值(绝对值)。

我确定，所有 D + 1 所需的点都是给定点集的凸包的顶点，但我需要该算法，该算法未使用任何凸包算法，因为它们需要单纯形，反过来，需要像开始多胞体这样的算法。

如果不可能在小于指数时间的时间内获得单纯形，那么算法是什么，它给出了可调整的比率运行时间/近似精度来近似求解问题？

Answer 1

我想不出一个精确的解决方案，但您可能可以通过迭代方法获得合理的近似值。请注意，我在这里假设 N 大于 D+1；如果不是，那么我误解了这个问题。

首先，使用贪心算法构造初始单纯形；选择前两个顶点作为两个最远的点，下一个顶点在两个维度上最大化你的尺寸测量，下一个在三个维度上最大化它，依此类推。这在 N 和 D 中具有多项式复杂度。
一个你有初始单纯形，你可以切换到迭代改进。例如，对于单纯形中的给定顶点，您可以遍历不在其中的点，测量如果交换它们会导致的尺寸测量变化。最后，你将它与增加最大的那一个(如果有的话)交换。对单纯形中的每个顶点执行一次同样是 N 和 D 中的多项式。
要在运行时成本和生成的单纯形有多大之间进行权衡，只需选择您愿意执行此操作的次数。

这是一个相对粗糙的局部优化算法，因此不能保证它会找到最大单纯形。然而，已经发现这些方法可以对旅行商问题等问题的解决方案产生相当好的近似值，因为虽然它们不是最优的，但它们导致的距离不会比大多数情况下的实际解决方案。