algorithm - A*算法开表选择

Question

我知道在 A* 算法中，当采取下一步时，应该从 openlist 或 frontier 中选择具有下一个最低预测成本的步骤，但是当有多个最低步骤都具有相同的预测成本时，是否有任何偏好应该选择哪一个？

我认为后进先出效果更好，但我不确定在有多个匹配成本时是否有更好的方法来选择下一步。

Answer 1

我想你在找bounded relaxation (AKA A*-epsilon) .

想法是生成f(v) = g(v) + (1+eps)h(v)。 eps 的值非常小，它不会改变算法的最优性，同时在搜索中更倾向于“深度”而不是“广度”，并且通常会提高搜索速度。

同样，您可以通过提供非常接近零但为负的 eps 值来支持广度 - 但我不熟悉这里支持广度的任何用法。