arXiv:2606.04860cs.LGcs.AI2026-06

用新方法训练神经启发式函数,确保解谜搜索路径最优且大幅减少计算量。

Learning Empirically Admissible Neural Heuristics for Combinatorial Search

  • 用带不对称损失的可允许贝尔曼算子训练神经网络,抑制高估。
  • 在验证集上添加安全偏移量,确保无任何高估违规。
  • 在魔方等难题上减少超80%搜索节点,适合需保证最优解的场景。

求解如魔方、滑块谜题和Lights Out等组合谜题的最优解路径仍是人工智能的经典挑战。启发式搜索算法(如A*)仅在使用不夸大真实剩余代价的可允许启发式函数时能保证路径最优性。深度强化学习方法(如DeepCubeA)通过深度神经网络近似代价到目标的启发式函数,但标准均方误差(MSE)训练常导致高估,违反可允许性并损害解的最优性。本文提出一种可推广的框架,用于学习经验证校准的可允许神经启发式函数。我们使用低估型可允许贝尔曼算子与非对称损失函数训练价值网络,以惩罚高估;为应对残余神经函数逼近误差,提出基于验证打乱状态计算的后处理校准安全偏移量。实验表明,经校准的神经启发式函数在评估协议下未出现任何可允许性违规,实际保持路径最优性,同时在2×2魔方上减少83.0%的搜索节点扩展,在3×3 Lights Out网格上减少19.9%,在8-滑块谜题上减少1.9%,显著优于标准解析基线。

原文摘要 · Abstract (English)

Finding optimal solution paths for combinatorial puzzles like the Rubik's Cube, sliding tile puzzles, and Lights Out remains a classical challenge in artificial intelligence. Heuristic search algorithms, such as A* , guarantee path optimality only when using an admissible heuristic-one that never overestimates the true remaining cost-to-go. Deep reinforcement learning (RL) methods like DeepCubeA train deep neural networks to approximate cost-to-go heuristics. However, standard mean-squared error (MSE) training regularly yields overestimations, violating admissibility and compromising solution optimality. In this paper, we introduce a generalizable framework for learning validation-calibrated admissible neural heuristics. We train a value network using an underestimating Admissible Bellman Operator combined with an Asymmetric Loss function to penalize overestimation. To account for residual neural function approximation errors, we propose a post-hoc calibration safety offset computed over validation scrambles. We demonstrate that our calibrated neural heuristics achieve no observed admissibility violations under the evaluation protocol and preserve path optimality in practice while reducing search node expansions by up to 83.0% on a 2 by 2 Rubik's Cube, 19.9% on a 3 by 3 Lights Out grid, and 1.9% on an 8-Puzzle compared to standard analytical baselines.

启发式搜索神经网络可允许性组合优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。