我想极大地优化我的算法之一,我会尽量用最好的方式来解释它。
主题
在t = 0时,我们处于二维欧几里得系统中。在这个系统中有两个对象:O1和O2。
O1和O2分别位于点PA和PC处。
O1以恒定且已知的速度沿点PB的方向移动。物体到达 PB 时将停止。
O2可以在任何方向以与 O1不同或不同的恒定且已知的速度移动。在时间 0,O2没有方向,我们需要为它找到一个方向。
已知参数:
- O1:位置、方向、速度
- O2:位置、速度
这是系统的小图。
我们想找到点PI和时间ti:Position of O1 at the time ti = Position of O2 at the time ti = PI
。然后我们将物体 O2 移动到点 PI 以获得O2 的方向。
When the direction of O2 (the point PI) is chosen and both objects O1 and O2 are on the move, the objects will never stop or wait for each other.
在这种情况下,结果将是这样的(PI 在这张图片上标注为 D)。
算法
你可以在这个jsfiddle找到用 JS 编写的工作算法,这也是理解问题的好方法。
这时候我使用了一个简单的算法,它可以工作,但是可以进行很多操作,我会得到最好的交叉点时间,然后得到交叉点的位置。
为了得到这个时间,我会检查一下 O1 的位置,并检查 O2 是否可能在这个时候去这个位置。如果 O2 不能及时到达物体,我们将增加 150% 的时间,但是如果 O2 可以在当时穿过 O1-B 线,我们将减少 50% 的时间。
最终,经过多次近似,我们将找到两个物体相遇的最佳时间。
伪代码
function getOptimalIntersectionTime time
if distance between O1 and O2 at the time `time` < 1
return time
else if O2 could not reach the object O1 at the time `time`
return getOptimalIntersectionTime time * 1.5
else
return getOptimalIntersectionTime time * 0.5
我为什么担心?
我的算法有效,但在某些情况下(例如 jsFiddle 中的“反向案例”),需要大量的微积分才能找到最佳点。
在这个 jsFiddle 中,我们对位置(-1000 到 1000)和速度(1-200)使用了很小的值,但是这个算法在使用更大的数字时会明显变慢。
我知道过早的优化是一个坏主意,但是我在项目的最后(包括数据库插入/选择和数据分析,包括这个算法被调用了很多次)并且这个算法占据了 80%在某些情况下项目系统资源,因此改进可以真正提高系统的稳定性和响应能力。