我们比较了五种方法：从空图开始禁忌搜索；增量禁忌搜索，其中使用课程来使用每个尺寸找到的高分图表作为更大尺寸的起点（在附录 F 中解释）； AlphaZero 从空图开始；增量 AlphaZero，其中使用课程（附录 D 中解释）；和瓦格纳的交叉熵方法[44]，第一个机器学习方法寻找数学猜想的反例（见附录G）。对于 AlphaZero，我们还对网络表示的选择进行了消融（参见附录 E）。由于 $f(n)=\theta (n\sqrt{(n)}$（参见（1））我们已将分数归一化为$n\sqrt{n}$在图中。

•    与最先进的下限进行比较。如图1所示，增量禁忌搜索当 $n\in 64,..,134\cup 138,...,160\cup 176，...，186\cup 188，...，190$（具体示例见附录A）.在表 2 中，我们有列出了通过增量禁忌搜索 n = 1, 2, … 实现的下限…,200.AlphaZero 与课程还改进了许多尺寸的最先进的下限，并且完全符合与 54 到 100 之间所有大小的增量禁忌搜索相同，n = 56, 57, 64, 66, 77 除外，96，增量禁忌搜索领先一步。我们观察到瓦格纳的交叉熵方法[44]的性能比禁忌搜索和AlphaZero都要差。详情请参阅附录 G。
  使用课程的好处。如果没有课程，代理必须构建给定的图表size 从空图开始，而在课程中，智能体从先前找到的较小尺寸的图开始，翻转一些边以获得所需尺寸的图。图2（左）说明了对于尺寸 54 至 100，使用课程进行禁忌搜索的好处，其中随着节点数量的增加而显着增加。图 2（右）显示了类似的图AlphaZero：不带课程的 AlphaZero 与带课程的 AlphaZero 的大小差不多30但之后恶化。我们认为原因是剧集长度较长和困难勘探和信用分配。我们的结论是，使用课程是一个重要的组成部分将强化学习应用于这个问题，并且可能适用于任何优化问题一个子结构属性和一个巨大的状态空间。
  
  图 1：归一化分数，由边数给出 $\frac{numberofedges}{n\sqrt{n}}$，根据大小 n 绘制。 AlphaZero 与课程（未绘制）与 41 个尺寸的增量禁忌搜索获得相同的分数54到100。Erdos推测红色和蓝色曲线都收敛到青色水平线为˝$n\to \infty$。最先进的下界来自[1,17,30,18]，理论上限来自[18]。
  
  图 2：左：使用课程的增量禁忌搜索，表现越来越好比禁忌搜索更大的问题规模。右：添加课程可以提高绩效AlphaZero 显着，尤其是在较大尺寸上。