search - A-star 搜索和整数规划之间的连接，扩展 A-star

Question

对于欧几里得最短路径问题，是否有人对 A 星搜索和更一般的整数规划公式之间的联系有很好的引用？

特别是我感兴趣的是如何修改 A-star 以应对额外的(可能是依赖于路径的)约束，如果使用通用 LP/IP 求解器来解决像这样的受限最短路径问题是有意义的，或者如果什么需要更专业才能达到 A-star 获得的相同性能以及良好的启发式。

不怕数学，但我为更复杂的最短路径问题找到的大多数引用资料都没有很明确地说明它们与 A* 等启发式引导算法的关系(也许是因为“A*”很难用谷歌搜索。 ..)

Answer 1

您可能想要研究约束优化，特别是软弧一致性和约束满足，特别是弧一致性，或其他类型的一致性，例如 i-一致性。以下是有关约束优化的一些引用资料:

[1] 托马斯·希克斯。软约束处理。 http://www.inra.fr/mia/T/schiex/Export/Ecole.pdf

[2] 德希特，丽娜。约束处理，第 1 版。摩根考夫曼，旧金山，CA 94104-3205，2003。

[3] Kask, K. 和 Dechter, R. Mini-Bucket Heuristics for Improvement Search。在过程中。 UAI-1999(加利福尼亚州旧金山，1999 年)，Morgan Kaufmann，第 314-323 页。

[3] 可能特别有趣，因为它处理将 A* 与您似乎感兴趣的类型的启发式相结合。

我不确定这是否对您有帮助。我是这样认为它可能的:

约束优化是 SAT 对具有两个以上值的优化和变量的概括。一组软约束(即部分成本函数)和一组离散变量定义了您的问题。通常使用分支定界算法来遍历该问题所暗示的搜索树。软弧一致性是指一组启发式算法，使用局部软约束来计算从您当前位置到该搜索树中目标节点的近似距离。这些启发式在分支定界搜索中使用，就像在 A* 搜索中使用启发式一样。

分支定界与树上的 A* 的关系与深度优先搜索与广度优先搜索的关系非常相似。因此，除了在这种情况下使用了类似 DFS 的算法(分支定界)并且它是树而不是图，它看起来像(软)弧一致性或其他类型的一致性就是你要找的。

不幸的是，虽然您原则上可以使用 A* 来代替分支定界，但目前尚不清楚(据我所知)通常如何将 A* 与软弧一致性结合起来。从树到图可能会使事情进一步复杂化，但我不知道。

所以，没有最终答案，只是一些可以作为入门的东西，也许:)。