简介

本文解决的问题是，给定一个图优化问题 和问题的分布 的实例，我们能从 中学习到更好的启发式推广到看不见的实例吗？

算法的大体结构是一个贪心算法，即我们在选择点的时候，每次都贪心地选择当前状态下最优的一个点，加入到选择集合中。与之前传统算法相比，本文本质上是使用强化学习去训练了一个policy， 根据当前的选择以及图的状态，来选择下一个点

本文的强化学习部分采用的是传统的 Q-Learining，说是因为policy gradient 方法在采样方面比较困难，而且本文推导出来 Q 函数有数学上的意义，因此采样了Q learning。

本文解决的图论问题

本文主要尝试了以下三个问题：

本文的基本假设

  1. 一个问题的实例 是从一个分布中采样出来的，这个分布可以是一个模型，也可以是来自于现实世界的例子
  2. 本文采样特征向量来作为当前局部最优解的表征，即一个位上是1表示选择该点，是0表示不选择该点
  3. 某些问题上可能需要一个helper function来合法化上面演化算法出来的解
  4. 对于一个局部的解 通过一个函数 来衡量其优越性，其中的 算子表示组合结构
  5. 贪心策略会选择能够最大化一个评估函数 的 ，换言之即

从上面的假设和流程可以看出，本文的核心难点在于怎么找到一个计算代价不高的 和自动化的训练出评估函数

至于helper function原文设定如下：

如何表示 Q 函数

如何估算

本文使用 structure2vec 方法来估算