学习A*算法的可接受启发式：理论与实践

于红博

摘要: 启发式函数对于搜索算法的性能至关重要，例如A星算法，其中可接受性——即永远不会高估真实最短路径成本的特性——保证解的最优性。最近的深度学习方法通常忽视了可接受性，并且在训练数据之外提供有限的泛化保证。本文解决了这两个限制。首先，我们将启发式学习作为一个受限优化问题，并引入交叉熵可接受性（CEA），这是一种在训练过程中强制执行可接受性的损失函数。在魔方领域，这种方法产生了近可接受的启发式，比压缩模式数据库（PDB）启发式提供了更强的指导。从理论上讲，我们研究了启发式学习的样本复杂度。通过利用PDB抽象和图的结构属性，如魔方，我们缩小了A星算法泛化所需的训练样本数量的界限。用ReLU神经网络替换一般的假设类别，得到的界限主要取决于网络的宽度和深度，而不是图的大小。利用相同的网络，我们还为目标相关的启发式提供了第一个泛化保证。

更新时间: 2025-09-26 17:51:26

领域: cs.LG,cs.AI

下载: http://arxiv.org/abs/2509.22626v1