arXiv:2504.21131v1 宣告类型: 新颖 摘要: 虽然在启发式搜索中研究的大多数启发式方法仅依赖于状态，但有些方法在搜索过程中积累信息，因此还依赖于搜索历史。现有的一些方法在$\mathrm{A}^*$-类似算法中使用此类动态启发式方法，并引用$\mathrm{A}^*$的经典结果来证明其最优性。然而，这样做忽略了使用可变启发式进行搜索的复杂性。在本文中，我们将动态启发式方法的概念形式化，并在通用算法框架中使用它们。我们研究了一种特定实例化的形式，该形式模拟了使用动态启发式的$\mathrm{A}^*$，并展示了通用最优性结果。最后，我们展示了现有的经典规划方法可以被视为此实例化的特殊情况，从而使我们能够直接应用我们的最优性结果。