algorithm - 接近检测点

Question

我有一大组 3D 的三阶多项式。

矩阵形式

Pn = [1,t,t ² ,t ⁴ ]*[An]

[Pn]分别[An]是1xN和4xN矩阵

每个函数都有一个权重 Wn。n, m, T对于某些人，我想t0找到第一个这样的t地方t>t0

(Wn*Wm) * |Pn-Pm| ^-2 > T

除了 O(n ² ) “尝试一切”方法之外，我什至不确定从哪里开始，就此而言，即使对于已知的 n 和 m，我也不知道如何回答这个问题。

有任何想法吗

编辑：

• 设置大小约为 10-1000
• 权重是分布的〜对数（很少大，很多小）
• 这个测试将在一个多体模拟器的内部循环中，所以它会运行很多
• 在改变一条路径后，在找到新答案方面表现良好（摊销）的版本是一件好事。

Answer 1

不知道这是否可以通过分析方法解决，有很多方法可以搜索空间并尝试找到任何符合该标准的 t。

遗传算法、模拟退火和其他优化算法浮现在脑海中。

Answer 2

确定播种锅：

• 使用某种形式的“close pair finder”算法在 t0 和其他时间用这些对在堆中播种。
• 拉出找到的最近的一对
• 如果足够接近并且比目前最好的更快，保持
• 找出它们是否更近或更远
• 将当前对和下一个对之间的差异拆分到“更近”的一侧，然后添加堆。

想法？

Answer 3

N有多大？是否有可能进行详尽的搜索？

我会在numpy或scipy讨论板上提问，并复习你的 Python 技能。我敢打赌，您可能会将其变成一个最小化问题，并使用 fmin 或BFGS或其他一些有界准牛顿算法来找到一个合理的最小值。也许最小化 t 和 T 之间的差异。除非你的矩阵中有什么奇怪的东西，否则你的搜索空间看起来至少是连续的。

由于您在标题中提到了最接近的方法，请在 numpy 板上查看此帖子。