We train a small message-passing graph neural network to predict Hamiltonian
cycles on Erd\H{o}s-R\'enyi random graphs in a critical regime. It outperforms
existing hand-crafted heuristics after about 2.5 hours of training on a single
GPU. Our findings encourage an alternative approach to solving computationally
demanding (NP-hard) problems arising in practice. Instead of devising a
heuristic by hand, one can train it end-to-end using a neural network. This has
several advantages. Firstly, it is relatively quick and requires little
problem-specific knowledge. Secondly, the network can adjust to the
distribution of training samples, improving the performance on the most
relevant problem instances. The model is trained using supervised learning on
artificially created problem instances; this training procedure does not use an
existing solver to produce the supervised signal. Finally, the model
generalizes well to larger graph sizes and retains reasonable performance even
on graphs eight times the original size.

通过小型消息传递图神经网络在临界状态下预测 Erdos-Renyi 随机图上的哈密顿回路，相较于现有的手工启发式方法，训练单个 GPU 大约 2.5 小时后性能表现更好，这种训练方法相较于手工设计的启发式算法具有较快的训练速度和较少的问题特定知识要求，并且通过使用监督学习算法在人工构建的问题实例上进行训练，避免了使用现有求解器产生的监督信号干扰，最终模型在更大规模图形上具有良好的泛化表现。

使用图神经网络寻找哈密顿回路

Finding Hamiltonian cycles with graph neural networks

Reinforcement learning has recently been used to approach well-known NP-hard
combinatorial problems in graph theory. Among these problems, Hamiltonian cycle
problems are exceptionally difficult to analyze, even when restricted to
individual instances of structurally complex graphs. In this paper, we use
Monte Carlo Tree Search (MCTS), the search algorithm behind many
state-of-the-art reinforcement learning algorithms such as AlphaZero, to create
autonomous agents that learn to play the game of Snake, a game centered on
properties of Hamiltonian cycles on grid graphs. The game of Snake can be
formulated as a single-player discounted Markov Decision Process (MDP) where
the agent must behave optimally in a stochastic environment. Determining the
optimal policy for Snake, defined as the policy that maximizes the probability
of winning - or win rate - with higher priority and minimizes the expected
number of time steps to win with lower priority, is conjectured to be NP-hard.
Performance-wise, compared to prior work in the Snake game, our algorithm is
the first to achieve a win rate over $0.5$ (a uniform random policy achieves a
win rate $< 2.57 \times 10^{-15}$), demonstrating the versatility of AlphaZero
in approaching NP-hard environments.

本文利用蒙特卡罗树搜索（Monte Carlo Tree Search，MCTS）算法创造了自主智能体，学习玩 Snake 游戏，该游戏可被公式化为单人折扣马尔可夫决策过程，问题困难度大，但与先前工作相比，该算法是首个实现胜率超过 $0.5$ 的算法，可应用于解决复杂的 NP 困难问题。