c - 有效地找到二维空间中位置的两倍最优成本

Question

我有一个 100 x 100 维的二维网格。网格中的每个点 (x,y) 都有一个相关的成本，并且它在整个空间中都是单调非递减的。相关费用事先不可知。

我无法找到所有地点的费用。所以我要做的是，找到最顶层位置的成本 (100,100)。将其称为成本 C。然后在此二维网格上识别等成本等高线，以获得一组精心选择的成本值。设 C 为成本位置 (100,100)。轮廓的成本经过精心选择，最后一个轮廓(轮廓 k)的成本为 C(网格中的最大成本)，轮廓 k-1 的成本为 C/2，轮廓 k-2 将与几何系列中的成本一样，成本为 C/4。 Iso 成本等高线以黑色曲线显示。它们是通过首先在左/上边缘定位种子然后沿着它的邻域探索来识别的。

现在对于轮廓上的任何位置 (x,y)，最近轮廓的成本将为位置 (x,y) 的成本提供一个近似值。也就是说，我们得到的成本值小于位置 (x,y) 的实际成本的两倍。轮廓上的每个位置 (x,y) 都覆盖其第三象限中的区域。例如，位置 M 被等值线覆盖，成本为 C/8。 因此，对于任何给定位置 (x,y)，我可以通过查看谁是其上方最近的轮廓及其成本来说明成本是多少。这给出了最接近的成本，但不是位置 (x,y) 的确切成本，这对我的情况来说已经足够了。但这需要我a) 找到 C、C/2、C/4 到 Cmin 的完整等值线。b) 存储上述所有等高线位置，即每个等高线 100 个位置。

如何在要探索和存储的空间中拥有非常少的点数，并且仍然实现两倍最优成本的特性？

注意:需要减少成本计算的地点数量。目前我正在计算所有等成本轮廓位置。 100乘100的分辨率是为了说明问题。实际分辨率要高得多。

Answer 1

您需要测试的最坏情况下的位置数有一个下限，与通过定位等成本等值线获得的上限相距不远。

假设您知道除 * 处的每个值:

.  2  .
1  *  2
.  1  .

此值可以是 1 或 2。(如果可以接受这种歧义，则可以将 2 替换为 2.001。)因此，您需要对其进行采样。您无法从其他站点的成本中确定值(value)。

设 k = log_2(cost(n,n)/cost(1,1))。您可以构造一个成本函数，这样在几乎 nk 个站点(大约 k(n-k/2))，如果不对该站点进行采样，您就无法确定 2 倍内的成本。我将说明一个示例，其中 k=3。

      8 8 8 8 8 8
    4 * 8 8 8 8 8
  2 * 4 * 8 8 8 8
1 * 2 * 4 * 8 8 8
1 1 * 2 * 4 * 8 8
1 1 1 * 2 * 4 * 8
1 1 1 1 * 2 * 4
1 1 1 1 1 * 2 
1 1 1 1 1 1

因此，对于 n>>k，您需要测试的站点数量是 theta(nk)。如果你有一个成本函数的概率模型，并且 k 比 n 小，你可能平均做得更好。