带相对方向约束的曲线拟合全局优化问题

问题描述 #

需要用定长线段对一条3D曲线进行最小偏差/误差的最优拟合，核心约束为：线段的方向依赖于前一段线段的方向。

2D简化场景的方向规则 #

线段N+1的可能方向仅包含以下5种：

• 线段N的方向 - 10°
• 线段N的方向 - 5°
• 线段N的方向
• 线段N的方向 + 5°
• 线段N的方向 + 10°

由此，线段N+2的方向会同时依赖于N+1和N的方向。本质上，线段间的相对方向只能取{10,5,0,-5,-10}度：

• 若线段N全局方向为0°，则线段N+1的全局方向为{10°,5°,0°,-5°,-10°}（0°+相对方向）
• 若线段N全局方向为5°，则线段N+1的全局方向为{15°,10°,5°,0°,-5°}（5°+相对方向）

相关草图说明：

• 第一张图：通过黑/红/紫线展示相对方向累积如何影响线段的全局方向
• 第二张图：展示相邻线段仅允许±10°相对方向的物理约束示例

拟合规模与现有方法的局限 #

拟合场景包含3500条线段，每段相对于前一段最多有26种方向选择，总组合数达到26^3500，完全无法枚举所有可能性。

已尝试的两种方法均无法得到全局最优结果：

• 逐段最优拟合：从线段0开始逐段计算最优选择，仅需26*3500次计算，耗时约10分钟，但只能得到局部最优，无法顾及长期全局误差
• 有限前瞻拟合：一次性拟合N+1到N+Y段，但受限于算力最多仅支持4段前瞻，依然无法覆盖长期全局优化需求

关键观察：通过增大线段N的局部拟合误差，可以显著改善线段N+500的拟合效果，进而降低系统整体误差。但修改线段N的方向后，必须重新计算线段N到3500的所有线段——所有后续线段的方向都依赖于前一段。

核心疑问 #

在这种“局部牺牲可换取全局大幅优化”的拟合场景中，应该采用什么方法实现全局优化？目前不清楚该领域的研究术语，无法开展针对性调研。

内容的提问来源于stack exchange，提问作者CrazyArm