1

想象一下，有一个函数可以在给定浮点 x 和 y 坐标（以及根据维度的附加组件）的情况下评估表面的高程：

double ComputeElevation(double x, double y, ...., double z) { }

这不是解析函数，因此无法计算导数。我需要做的是找到任何给定 {x, y} 对的表面最陡的方向。一次评估可能非常昂贵（在最坏的情况下考虑几秒钟甚至几分钟）。

我在 2D 情况下的典型方法是在与 {x, y} 相邻的 N 个位置对表面进行采样，然后通过这些样本拟合曲线并搜索曲线的最高点，因为这种搜索不会受到昂贵的评估的影响：

2D 采样算法示例

在上图中，P0 是给定的坐标。{S0, S1, S2, S3} 是 P0 周围随机放置的 4 个样本，PM 是曲线上的最高点。因此，向量 PM-P0 是最陡上升的方向。

但我不知道如何将其扩展到 N 维，或者是否有更智能的算法可以做到这一点。

维度的数量可能非常大（几十到几百），所以当样本少于维度时，我最终使用的任何方法都必须有效。我不是在寻找确切的答案，那是不可能的，但是一个中途的近似值已经很受欢迎了。

附言。我在 C# 中执行此操作，这并不重要，但我无法访问非 C# 语言功能。

4

2 回答 2

2

看起来您正试图从给定点附近的一组随机样本中估计梯度。

不幸的是，如果你有n维度，你需要最少的n+1点来正确估计梯度。使用更少的点，维度需要退出，并且您将估计梯度的较低维度投影。也就是说，如果您捕获k尺寸，您的项目很可能会获得sqrt(k/n)真实渐变的长度。

这是一种方法。假设您k+1在您的点周围采样了随机点，并进一步假设它们是线性独立的。选择其中一个作为您的“原点”，然后您将拥有k维度。找到另一个n-k与之前所有点正交的点，并输入您的原点值。（这将导致这些尺寸不在渐变中表示。）

现在你有了n向量和梯度的点积估计值。取每个标准单位向量，并将其写为向量的线性组合。斜率的相同线性组合将为您提供梯度的该分量的估计值。对所有单位向量执行此操作，将它们加在一起，瞧，您就有了梯度的估计值。

请注意，如果您尝试使用一些近点和一些远点，其中一些不是线性独立的，那么这种方法将不起作用，您需要做一些更复杂的事情。

于 2011-07-01T00:09:29.963 回答
0

我不完全清楚为什么计算曲线比随机采样点便宜，但这让我想起了http://en.wikipedia.org/wiki/Gradient_descent。您可以将您的问题视为尝试优化当前位置和新点之间的高程差异。它可能比尝试随机点更快，并且很容易推广到多个维度

由于该函数可能是非单调递增的，因此您可能希望将其定义为与边界的关系（在起点的 x 个单位内）。

于 2011-06-30T23:38:03.487 回答