arXiv：cs.AI· Nikita Morozov, Ian Maksimov, Daniil Tiapkin, Sergey Samsonov·· 5 小时前
用生成流网络（GFlowNets）学习最短路径
Learning Shortest Paths with Generative Flow Networks
AI 导读
研究者提出一种基于生成流网络（GFlowNets）的最短路径学习框架，证明当总流量最小时，前向与后向策略只沿初始与终止状态间的最短路径遍历环境图，并通过流正则化训练近似求解。该方法在排列环境寻路与多种尺寸魔方求解中，解的长度与专为该任务设计的SOTA机器学习方法相当，且测试时所需搜索预算更小。
正文
Abstract: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 reduce shortest-path finding in an arbitrary unweighted graph to finding a non-acyclic GFlowNet with minimal total flow, and approximate it in practice by training with flow regularization. We experimentally demonstrate the performance of our method in pathfinding in permutation environments and in solving Rubik's Cubes of various sizes. For the latter problems, 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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2603.01786 [cs.LG] |
| (or arXiv:2603.01786v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2603.01786 arXiv-issued DOI via DataCite |
Submission history
From: Nikita Morozov [view email]
[v1]
Mon, 2 Mar 2026 12:12:13 UTC (307 KB)
[v2]
Tue, 13 Oct 2026 12:47:07 UTC (334 KB)
来源：arXiv：cs.AI · arxiv.org