基于位移向量的n维空间点到原点最少向量数路径求解

给定n维空间中的位移向量列表 (v_1, v_2, \dots) 以及点A，我们可以用这些向量构建从A到原点的路径。每条路径对应一组整数系数 (c^i)，满足等式：

(OA = \sum c^i v_i)

我们需要找到若干（比如10条）N值最小的路径，其中 (N = \sum |c^i|)，也就是使用向量的总步数最少的路径（例如红色路径更优，因为它的步数更少）。目前能想到的只有暴力枚举n个向量的所有组合、分解OA求系数再按N排序的方法，想找更高效的解决方案。

• 整数线性规划（ILP）求解：把问题建模为ILP，目标函数设为最小化 (N = \sum |c^i|)，约束条件为 (\sum c^i v_i = OA) 且 (c^i \in \mathbb{Z})。主流ILP求解器（如Gurobi、CPLEX）支持输出前k个最优解，能直接避开暴力枚举，快速拿到所需的10条最优/次优路径。
• 反向广度优先搜索（BFS）：把问题反转，从原点出发搜索到点A（等价于原问题从A到原点）。每一步选择添加或减去某个向量，记录每个位置对应的最小N值。一旦搜索到A就记录系数组合，继续搜索直到收集够10条路径。这种方法天然优先探索步数少的路径，不会做无用功。
• 格基约化+组合扩展：先用LLL等格基约化算法对原始向量集处理，得到更短、更正交的基向量。用约化后的基求解系数，能更快得到小N的解，再通过基向量的整数线性组合生成其他次优解，大幅缩小搜索范围。
• 分支定界法：先放松约束允许实数系数，算出N的下界。再逐步分支枚举整数系数，剪掉那些N超过当前最优解的分支，快速缩小搜索空间，高效找出前k个最小N的路径。

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