问题标签 [approximation]

一个简单的解析函数 f(s,Г) 怎么能近似逆不完全伽马函数Г(s,x)？这意味着写 x = f(s,Г) = 12*log(123.45*Г) + Г + 123.4^s 之类的东西。

（我至少需要想法或参考资料。）

赏金

这个问题提出了几个问题。赏金将用于从整体上解决它们的答案。

这是我一直在玩的一个问题。

注意我对不基于欧几里得空间的解决方案特别感兴趣。

有一组 Actor 形成了一个大小为 K 的人群。d(ActorA,ActorB)对于任何两个 Actor 来说，距离很容易计算（解决方案应该适用于“距离”的各种定义），我们可以使用任何给定 Actor 找到 N 个最近邻居的集合许多已建立的算法中的任何一种。

这个邻居集在第一时刻是正确的，但是Actor 总是在移动，我想为每个 Actor 维护 N 个最近邻居的进化列表。我感兴趣的是比完美解决方案更有效的近似解决方案。

1. 引入错误后，解决方案应该收敛到正确性。
2. 如果错误变得太大，有时执行完全重新计算是可以接受的，但检测这些错误应该很便宜。

到目前为止，我一直在使用朋友的朋友算法：

当人群移动缓慢且 N 适当大时，这表现得相当好。它在小错误后收敛，满足第一个标准，但

• 我没有检测大错误的好方法，
• 我没有对错误的大小和频率进行定量描述，
• 它在实践中收敛，但我不能证明它总是会的。

你能帮助解决这些问题吗？

另外，您是否知道任何表现良好的替代方法

• 当人群快速移动时，
• 当一些演员快速移动时，
• 当 N 很小时，
• 当人群在某些地方稀疏而在其他地方密集时，
• 还是使用特定的空间索引算法？

我目前正在做的扩展是在邻居快速移动的情况下将朋友的朋友推广到朋友的朋友的朋友。我怀疑这不能很好地扩展，并且如果不对误差进行量化，就很难得出正确的参数。

我欢迎所有建议！这是一个有趣的小问题:-)

迄今为止值得注意的建议

Fexvez：随机采样额外邻居，采样大小取决于 Agent 的速度。从它即将进入的区域取样可能也会有所帮助。

当代理speed*delta_time超过与最远已知邻居的距离时，对邻居重新采样。

维护Delaunay 三角剖分，它是最近邻图的超集。只考虑一个最近的邻居。

David Mount 的ANN 库 似乎无法处理移动物体。

我从来不明白为什么浮点数据类型被认为是近似值，而十进制数据类型被认为是精确的。我正在寻找一个好的解释，谢谢。

我正在使用一些流行的 python 包作为基础，为图形和网络开发一个开源近似算法库。主要目标是包含针对图和网络上的 NP 完全问题的最新近似算法。这样做的原因是 1）我还没有看到一个很好的（现代）整合包来涵盖这个和 2）这将是一个很好的教学工具，用于学习 NP-Hard 优化问题的近似算法。

在构建这个库时，我使用单元测试来进行完整性检查（就像任何合适的开发人员一样）。我对我的单元测试有些谨慎，因为就其本质而言，近似算法可能不会返回正确的解决方案。目前我正在手动解决一些小实例，然后确保返回的结果与之匹配，但这是不可取的，在实现意义上也不可扩展。

对近似算法进行单元测试的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报（那个时候测试很幸运，不能保证所有实例都低于界限）。

python中是否有模块可以用遗传算法逼近给定函数（a）来接收函数（b），该函数会产生相同或相似的输出和相同的输入？为什么要近似？函数（a）的工作原理是未知的。所以基本上算法应该做的是最小化函数（a）和变异函数（b）产生的样本值的偏差。有任何想法吗？

例子：

我已经在一个项目中达到了这样的地步：开始为向量和其他三角函数构建一些支持类比继续使用临时函数更有意义。我希望有很多 C++ 库为此，但我不想牺牲我习惯的速度和功能。

具体来说，我希望能够使用整数角度，并且我希望保持这样的近似值所提供的超快速度：

因此，在我不必要地自己动手之前，是否有任何用于 c++ 的非常快速的定点库，其中包含模板类（例如向量），我可以在其中指定使用的整数的宽度，并且具有快速近似值，例如我应该看的上面那个?

有许多算法可以找到直线施泰纳最小树 (RSMT) 的近似值。其中有：

• 一套找到最小生成树的算法
• RST-T（直线单主干施泰纳树）
• BGA（批量贪心算法）
• BI1S（批量迭代 1-Steiner 树）
• FLUTE（基于快速查找表的 RSMT 构造和线长估计技术）

结果表明，RSMT 的长度可以达到直线生成最小树的 3/2 倍。我没有在文献范围内找到其他算法。它们存在吗？

FLUTE 似乎是所有算法中最有效的算法，但我不知道它是最坏的情况和上限。找到了吗？

是否有任何算法的界限小于 3/2？

here is what I want to do (preferably with Matlab):

Basically I have several traces of cars driving on an intersection. Each one is noisy, so I want to take the mean over all measurements to get a better approximation of the real route. In other words, I am looking for a way to approximate the Curve, which has the smallest distence to all of the meassured traces (in a least-square sense).

At the first glance, this is quite similar what can be achieved with spap2 of the CurveFitting Toolbox (good example in section Least-Squares Approximation here). But this algorithm has some major drawback: It assumes a function (with exactly one y(x) for every x), but what I want is a curve in 2d (which may have several y(x) for one x). This leads to problems when cars turn right or left with more then 90 degrees. Futhermore it takes the vertical offsets and not the perpendicular offsets (according to the definition on wolfram).

Has anybody an idea how to solve this problem? I thought of using a B-Spline and change the number of knots and the degree until I reached a certain fitting quality, but I can't find a way to solve this problem analytically or with the functions provided by the CurveFitting Toolbox. Is there a way to solve this without numerical optimization?

所以我决定做一个超几何分布计算器（概率和统计的东西）。问题是输出总是介于 0 和 1 之间。因此 Python 根据输出值向下舍入到 0 或向上舍入到 1。

这是我的代码

我试过导入十进制模块，但我不确定我是否正确使用它，或者这是否就是它的用途。任何帮助都是极好的！

编辑：例如，当我设置 N = 15、n = 6、r = 5 和 k = 3 时，它会将答案四舍五入为 0。我希望它打印正确的答案：.2397802398。谢谢！

我正在尝试使用动态编程计算函数 F(x,y)。功能上：

F(X,Y) = a1 F(X-1,Y)+ a2 F(X-2,Y) ... + ak F(Xk,Y) + b1 F(X,Y-1)+ b2 F (X,Y-2) ... + bk F(X,Yk)

其中 k 是一个小数（k=10）。

问题是，X=1,000,000，Y=1,000,000。因此，为 x=1..1000000 和 y=1..1000000 之间的每个值计算 F(x,y) 是不可行的。是否有一个近似版本的 DP，我可以避免为大量输入计算 F(x,y)，并且仍然可以准确估计 F(X,Y)。

一个类似的例子是两个非常长且相似的字符串（例如相似的 DNA 序列）的字符串匹配算法（Levenshtein 距离）。在这种情况下，只有对角线分数很重要，远离对角线的条目对最终距离没有贡献。我们如何避免计算非对角线条目？

PS：忽略边界情况（即当 x < k 和 y < k 时）。