arXiv:2407.17413v3 公告类型: replace-cross 摘要: 我们提出了一种新的算法，该算法结合了现有的基于凸规划的方法和启发式信息，以找到凸集合图（SPP-GCS）上最短路径问题的最优性和接近最优路径。我们的方法受到 $A^*$ 的启发，从一个指定的顶点子集开始，以一种类似于最佳优先的方式进行操作，并迭代地扩展它，直到进一步的增长既不可能也不会有好处。传统上，获得优化问题的解的界通常涉及求解一个松弛问题，将松弛的解修改为可行的解，然后比较这两种解来确定界限。然而，对于 SPP-GCS，我们展示了逆向处理这个过程在欧几里得旅行成本的情况下可以更加有利。换句话说，我们最初使用 $A^*$ 来为 SPP-GCS 找到一个可行的解，然后将这个解限制在 $A^*$ 探索的顶点上求解一个凸松弛问题以获得一个松弛的解，最后比较这些解来确定界限。我们展示了数值结果，以突出我们的算法在求解的凸程序规模和计算时间方面相对于现有方法的优势。