接近点检测

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 >

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

任何想法

编辑：

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

Answer 1

由于不知道这是否可以通过分析手段解决，因此有许多方法来搜索空间并尝试找到任何满足该标准的 t。

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

Answer 2

可以播种底池：

• 使用某种形式的“紧密对查找器”算法在 t0 和其他时间用这些对播种堆。
• 拉出找到的最接近的一对
• 如果足够接近并且比迄今为止最好的更快，则
• ，继续查找它们是否更接近或更远，
• 将当前对与“较近”一侧的下一对之间的差异分开，并将其添加到堆中。

想法？

Answer 3

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

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

由于您在标题中提到了最近的方法查看此帖子< /a> 在 numpy 板上。