按年被提到
20212021 · 4 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:2104.14516 · math.CO

Constructions in combinatorics via neural networks

用神经网络构造组合数学中的例子
Adam Zsolt Wagner · 2021

用深度交叉熵方法找到组合数学猜想的反例与显式构造

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2021-05-01 · 最近 2022-03-07
5不同的人
4活跃月份
5讨论串
40被引(OpenAlex)

论文展示如何使用强化学习算法,即深度交叉熵方法,为极值组合与图论中的若干公开猜想找到显式构造和反例。被推翻的猜想包括 Brualdi 与 Cao 关于避免某种模式的矩阵的积和式最大化的问题,以及若干涉及图的邻接矩阵与距离矩阵特征值的问题。

HN 为什么提它

HN 评论者把它当作「用神经网络为组合数学问题找构造 / 反例」的参考来推荐,同时有人指出作者也提到其中一些问题可以用线性规划求解器解决。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1极值组合与图论
2图的谱(邻接矩阵特征值)
3强化学习与交叉熵方法
4神经网络基础

学习路径

读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

这条路径帮你了解把组合优化当作神经网络加强化学习问题的几项前期工作,再看本文如何用很简单的交叉熵方法找到反例。

  1. 1
    Pointer Networks指针网络(Pointer Networks) · 2015

    指针网络是早期用神经网络直接输出组合结构的方法,是后续神经组合优化的基础。

    读用注意力指向输入位置作输出的机制。

  2. 2

    第一批用强化学习训练神经网络求解组合优化问题的工作。

    读策略梯度训练指针网络求解旅行商问题的流程,以及奖励设计。

  3. 3

    在图上用强化学习学习组合优化的贪心启发式,与本文处理图论问题相关。

    读把图问题表示成逐步构造解的决策过程。

  4. 4

    综述神经网络在组合优化与推理中的用法,给出本文所处的整体背景。

    读整体分类与主要方法,了解本文方法在其中的位置。

  5. 5
    Constructions in combinatorics via neural networks用神经网络构造组合数学中的例子 · 2021 · 就是这篇

    目标论文:用深度交叉熵方法在极值组合与图论里找猜想的反例与显式构造。

    读把构造当作序列决策的建模方式,交叉熵方法的训练循环,以及各猜想的结果。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用dpaleka · 2021-08

“see Constructions in Combinatorics via Neural Networks [0] by Wagner (2021).”

指出 Wagner 用神经网络构造组合数学例子的论文
How Big Data Carried Graph Theory into New Dimensions原评论 ↗
引用porcoda · 2022-03

“The author does mention problems where LP solvers can be used to solve the problems instead of the neural network approach used for the others.”

指出作者提到部分问题也可用 LP 求解器而非神经网络解决
An AI has solved several open problems in combinatorics and graph theory原评论 ↗
被提交为 story · 3 次