用生成流网络学习图中最短路径，理论保证路径最优。
Learning Shortest Paths with Generative Flow Networks
- 设计非环状生成流网络，通过流量正则化训练实现最短路径搜索。
- 在排列环境和魔方求解中表现良好，解长与顶尖方法相当。
- 测试时搜索预算更小，适合需高效推理的路径规划场景。
本文提出一种基于生成流网络（GFlowNets）的新型学习框架，用于在图中寻找最短路径。我们分析了非环状环境下GFlowNets的理论性质，证明若总流量最小化，正向与反向策略将仅沿起始状态与终止状态间的最短路径遍历图结构。基于此结果，我们展示任意图中的路径规划问题可通过训练带流量正则化的非环状GFlowNet解决。实验验证了该方法在排列环境及魔方求解中的性能：在后者上，其解长与专为魔方设计的先进机器学习方法相当，同时测试阶段所需搜索预算更小。
原文摘要 · Abstract (English)
In this paper, we present a novel learning framework for finding shortest paths in graphs utilizing Generative Flow Networks (GFlowNets). First, we examine theoretical properties of GFlowNets in non-acyclic environments in relation to shortest paths. We prove that, if the total flow is minimized, forward and backward policies traverse the environment graph exclusively along shortest paths between the initial and terminal states. Building on this result, we show that the pathfinding problem in an arbitrary graph can be solved by training a non-acyclic GFlowNet with flow regularization. We experimentally demonstrate the performance of our method in pathfinding in permutation environments and in solving Rubik's Cubes. For the latter problem, our approach shows competitive results with state-of-the-art machine learning approaches designed specifically for this task in terms of the solution length, while requiring smaller search budget at test-time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。