问题标签 [approximation]

为了更详细地描述它，如果我有一个区域的图像地图，当单击时，将执行查询以获取有关该区域的更多信息。

我的客户希望我在将鼠标悬停在该区域图像地图上时显示大致数量的搜索结果。

我的问题是如何缓存？或者在不严重耗尽服务器内存资源的情况下获得该数字？

顺便说一句，如果这是必要的信息，我正在使用 php 和 mysql。

我试图通过使用傅里叶描述符来近似形状边界。我知道这是可以做到的，因为我在课堂上了解到它并在多个来源中阅读过它。

为了获得 (x,y) 坐标边界的傅里叶描述符，我执行以下操作： 1) 将 (x,y) 坐标转换为 x + iy 形式的复数 2) 将这组新数字输入 1D傅里叶变换 3) 输出是傅里叶描述符

为了近似边界，我简单地移除（设置为零）高频，然后应用傅里叶逆变换，然后将复数转换回 (x,y) 坐标，然后从这组新坐标重建图像。我的项目的目标是根据我设置为零的项的数量来找出我可以近似边界的程度。

我的问题是，每当我将任何频率设置为 0 时，我的输出图像都会非常小，并且会以非常奇怪的模式出现。

我在下面提供了一个示例。输入图像是一个普通的正方形。给出的第一个输出图像是使用所有傅里叶描述符正常重建的图像。请注意，整个边界不存在，因为边界像素的数量被采样为 256，并且我在输出时没有费心连接点。另请注意，输出被翻译到左下角，这是故意的。第二个输出图像是当我只使用前 128 个频率时。

输入图片 http://img19.imageshack.us/my.php?image=square0.bmp

输出图像 1：所有频率 http://img27.imageshack.us/my.php?image=square0normal.bmp

输出图像 2：频率的前半部分 http://img23.imageshack.us/my.php?image=square0out.bmp

有谁知道为什么会发生这种情况？

编辑：第一次把图像放在这里，不知道为什么它们没有出现..这里是链接：
输入图像
输出1
输出2

这里还有一个文档的链接，它有点讨论这个问题，它从第 5 页的末尾开始。

或者更确切地说，组合算法和线性算法的定义分别是什么？

说清楚是因为显然第一响应者误解了这个问题：我不是在寻找线性时间与非线性时间运行的算法的定义。线性算法在某种程度上与线性规划有关，线性规划是一种用于寻找或逼近线性优化问题的解决方案的技术。

由于 NP-hard 问题非常困难，因此整个领域都在试图找到近似解。例如，旅行商问题有几个近似解，它们在多项式时间内运行，并产生一个在最佳解的给定范围内的解。

这些近似算法中的一些称为线性算法，另一些称为组合算法；后者似乎是首选（为什么？）。这是我想了解的两个概念。

我需要找到未定义函数与阈值相交点的良好近似值。我正在步入我的空间，每当我发现两个后续步骤位于阈值的不同侧时，我都会在两者之间添加一个点：

_{（来源：宁网）}

我的第一种方法是只选择中点，但这显然是一个糟糕的解决方案：

_{（来源：宁网）}

我现在使用线性插值，它给出了一个合理的结果，但底层函数实际上永远不会是线性的。因此，只有当我的步长足够小时，这才有效：

_{（来源：宁网）}

对基本函数进行采样可能会非常昂贵，但是我想尝试添加一两个额外的样本以获得更好的近似值。是否可以在这里使用三次插值？像这样：

_{（来源：宁网）}

还是有更好的方法？

非常感谢，大卫·鲁滕

附言。我正在用 C# 编写，但这是一个与语言无关的问题。

有谁知道将光频率转换为 RGB 值的任何公式？

我正在尝试使用我自己编写的神经网络来近似 sine() 函数。我已经在一个简单的 OCR 问题上测试了我的神经网络并且它有效，但是我无法将它应用于近似正弦（）。我的问题是，在训练过程中，我的误差恰好收敛到 50%，所以我猜它是完全随机的。

我使用一个输入神经元作为输入（0 到 PI），一个输出神经元作为结果。我有一个隐藏层，我可以在其中改变神经元的数量，但我目前正在尝试大约 6-10 个。

我感觉问题是因为我使用的是 sigmoid 传递函数（这是我的应用程序中的要求），它只输出 0 和 1 之间，而 sine() 的输出在 -1 和 1 之间。尝试纠正我尝试将输出乘以 2，然后减去 1，但这并没有解决问题。我想我必须在某处进行某种转换才能使这项工作正常进行。

有任何想法吗？

我正在开发一个 Java/Groovy 程序。我有一个双变量，其中包含用户输入的数字。我真正想知道的是用户在小数点右边输入了多少个数字。就像是：

当然，你不能用 double 来做到这一点，因为它使用的是 IEEE 浮点数，而且都是近似值。

假设我无法获取用户键入的字符串，但只能访问存储值的双精度，有没有办法可以通过 BigDecimal 或类似的方法来清除该双精度以获得“真实”数量小数位？（当双重显示在屏幕上时，它是正确的，所以我认为有一种方法至少可以很好地猜测？）

我附上图片：（ _{来源：piccy.info）}

所以在这张图片中有一个函数的图表，它是在给定的点上定义的。例如在点 x=1..N 上。

另一个图，它被画成半透明曲线，这就是我想从原始图中得到的，即我想逼近原始函数，使其变得平滑。

有什么方法可以做到这一点吗？

我听说过最小二乘法，它可以用直线或抛物线函数来逼近一个函数。但我不需要用抛物线函数来近似。我可能需要用三角函数来近似它。那么有什么方法可以做到这一点吗？还有一个想法，如果我们可以为三角函数推断出最小二乘法，是否可以使用最小二乘法来解决这个问题？

还有一个问题！如果我使用离散傅里叶变换并将函数视为波的总和，那么可能噪声具有特殊的特征，我们可以通过它来定义它，然后我们可以将相应的频率设置为零，然后执行傅里叶逆变换。因此，如果您认为这是可能的，那么您可以提出什么建议来识别噪声频率？

我有一种方法，它使用随机样本来近似计算。这种方法被调用了数百万次，因此选择随机数的过程是否高效非常重要。

我不确定 java 到底有多快Random().nextInt，但我的程序似乎并没有像我希望的那样受益。

选择随机数时，我执行以下操作（在半伪代码中）：

现在，这显然有一个糟糕的最坏情况运行时间，因为理论上随机函数可以永远添加重复的数字，从而永远停留在 while 循环中。但是，这些数字是从 {0..45} 中选择的，因此在大多数情况下不太可能出现重复值。

当我使用上述方法时，它只比我的其他方法快 40%，这不是近似的，但会产生正确的结果。这运行了大约 100 万次，所以我希望这种新方法至少快 50%。

您对更快的方法有什么建议吗？或者，也许您知道一种更有效的生成一组随机数的方法。

为了澄清，这里有两种方法：

经过一些测试和分析，我发现这种方法是最有效的：

考虑一个加权图 G=(V,E,w)。我们得到一组顶点 V_i 的子集。

斯坦纳森林是一个森林，对于每个顶点子集 V_i 将这个子集中的所有顶点与一棵树连接起来。

示例：只有一个子集 V_1 = V。在这种情况下，Steiner 森林是整个图的生成树。

示例：图 P4（具有 4 个顶点的路径）和两个子集：V_1 = {v1, v4} 和 V_2 = {v2, v3}。此示例的 Steiner 树是整个图。

理论够了。很难找到这样一个重量最小的森林（NP-complete）。你知道任何更快的近似算法来找到这样一个非最优权重的森林吗？