论文标题
学习A*
Learning heuristics for A*
论文作者
论文摘要
图中的路径查找是计算机科学中研究最多的问题之一。在这种情况下，搜索算法通常会通过启发式方法扩展，以更有效地搜索目标节点。在这项工作中，我们结合了神经算法推理的最新进展，以学习图形上的路径问题的有效启发式功能。在培训时，我们利用多任务学习来共同学习Dijkstra的算法，并为A*搜索算法提供一致的启发式功能。在推论时，我们将学习的启发式方法插入A*算法中。结果表明，与Dijkstra相比，在学到的启发式值之上运行A*可以大大加快目标节点的搜索，同时仍然找到最小的成本路径。
Path finding in graphs is one of the most studied classes of problems in computer science. In this context, search algorithms are often extended with heuristics for a more efficient search of target nodes. In this work we combine recent advancements in Neural Algorithmic Reasoning to learn efficient heuristic functions for path finding problems on graphs. At training time, we exploit multi-task learning to learn jointly the Dijkstra's algorithm and a consistent heuristic function for the A* search algorithm. At inference time, we plug our learnt heuristics into the A* algorithm. Results show that running A* over the learnt heuristics value can greatly speed up target node searching compared to Dijkstra, while still finding minimal-cost paths.
