在给定位移向量的情况下找到两点之间的最短路径

Question

我有一个向量列表 v₁，v₂，... 和 n 维空间中的点 A。这些矢量是可用于构建从 A 点到原点的路径的位移。问题是找到一些向量前面系数和最小的路径（使用的向量“量”最少）。

在我看来，图论可以用在这里，但我从来没有研究过，所以我正在寻求建议。我的想法是创建一个树形图

（图）

从 OA 开始，继续分层，在每层添加一个向量。我相信可以通过当前总和与相加向量的点积来确定系数。该系数还可以用作连接相邻层的边的权重。然后我可能可以使用 Dijkstra 算法之类的东西来搜索该图中的最短路径。

我需要关于这是否是可行的方法以及哪种搜索算法更适合此应用程序的建议。

Answer 1

假设：

您希望以最小的方向变化总和从 OA 移动到原点

算法：

• 将S1设置为OA
• 循环1
  • 找到与 S1 到原点的角度最小的向量 V
  • 循环2
    • 将 S2 设置为 S1 + V
    • 如果 S2 == 原点
      • 将 V 添加到路径
      • 停止
    • IF S2 到原点的距离 > S1 到原点的距离 从循环 2 中中断
    • 将 V 添加到路径
    • 将S1设置为S2
  • ENDLOOP2
• ENDLOOP1