A-star搜索与整数规划的联系，扩展A-star

Question

关于A-star搜索和欧几里得最短路径问题的更一般整数规划公式之间的联系，有没有人有很好的参考？

特别是，我感兴趣的是如何修改A-star以应对额外的(可能是路径相关的)约束，如果使用通用的LP/IP求解器来解决像这样的约束最短路径问题是有意义的，或者如果需要更专业的东西来实现A-star获得的相同类型的性能以及良好的启发式方法。

我不害怕数学，但我找到的大多数关于更复杂的最短路径问题的参考文献都不是非常明确地说明它们与启发式引导算法A*的关系(可能是因为'A*‘很难在google上搜索到...)

Answer 1

您可能希望研究约束优化，特别是软圆弧一致性，以及约束满足，特别是圆弧一致性，或其他类型的一致性，如i-consistency。下面是一些关于约束优化的参考：

1. Thomas Schiex。软约束处理。http://www.inra.fr/mia/T/schiex/Export/Ecole.pdf

2分，瑞娜。约束处理，第一版。摩根·考夫曼，旧金山，加利福尼亚州94104-3205,2003年。

3 Kask，K.和Dechter，R. Mini-Bucket启发式，用于改进搜索。在进程中。UAI-1999 (旧金山，加利福尼亚州，1999)，Morgan Kaufmann，第314-323页。

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

我不确定这是否对你有帮助。这就是我是如何得到这个想法的：

约束优化是SAT对最优化和两个以上变量的推广。一组软约束，即部分成本函数和一组离散变量定义了您的问题。通常使用分支定界算法来遍历此问题所暗示的搜索树。软弧一致性指的是一组启发式算法，它们使用局部软约束来计算到搜索树中目标节点的近似距离。这些启发式算法在分支定界搜索中使用，与在A*搜索中使用的启发式算法非常相似。

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

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

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