如何使用机器学习来预测 A 星级搜索的启发式

Question

我的问题是如何使用机器学习为 A 星搜索预测更好的启发式算法。具体来说，

1. 我们是否应该训练一个可以采用任意节点并输出更好的启发式函数（比曼哈顿/欧氏距离更接近估计）的模型，这可以在以后更好地指导搜索？因为在 A 星中，我们按节点的 g+h 对节点进行排序。我们应该关注从任意状态到目标状态的未来成本吗？还是启发式函数？

2. 在训练中，我们可以选择哪些特征作为x的特征？

我很困惑。我可能没有正确理解启发式的概念。

Answer 1

使用机器学习为 A* 搜索预测更好的启发式算法是一个活跃的研究领域，您可以采用多种方法。

1. 训练一个可以采用任意节点并输出更好的启发式函数的模型。这个启发式函数应该提供比曼哈顿或欧几里得距离更准确的估计从当前节点达到目标的成本。可以使用节点数据集及其相应的启发式估计来训练模型。

就您可以选择作为模型输入 (x) 的特征而言，您可以考虑使用有关节点状态的信息，例如节点的位置、到目标的距离、路径中的障碍物以及任何其他相关信息。您还可以考虑使用有关先前访问的节点的信息以及为到达当前节点所采取的操作。

重要的是要记住，启发式函数的质量对 A* 算法的性能至关重要。因此，训练的重点应该放在改进启发式函数本身而不是从任意状态到目标状态的未来成本上。目标是训练一个模型，该模型可以更准确地估计从给定节点达到目标的实际成本。

总的来说，将机器学习用于 A* 搜索启发式的方法是一个活跃的研究领域，并且有许多可能的探索方向。在选择特定方法之前，清楚地了解问题和可用数据非常重要。