比方说，假设有5个城市，则潜在旅游路线的总数量为5!=120。但是对于有7个城市的情况来说，这个计算结果会立增到5040，10个城市已经达到则是3628800，100的结果更是惊人地高达9.332622e 157，而这数量远远超过了宇宙中原子的数量。在现实生活中TSP的运用实例涉及到的是成千上万的城市数量运算，为了能在合理的时间(可能是几个小时)内解决问题，通常需要运用那些高度复杂的搜索算法和启发式算法，而这些算法是通过几十年下来的大量文献所开发形成的。
不幸的是，在实际应用中出现的许多COPs具有独特的细微差别和条件约束，它们阻止我们用最先进的解决方案来解决诸如TSP之类的已知问题，并且要求我们开发针对该问题的方法和启发式。这个过程可谓长路漫漫障碍重重，可能需要相关领域专家来检测特定问题组合，搜索空间中的某些结构。这些年来，由于深度学习在许多领域都取得了巨大的成功，让机器自主学习如何解决问题似乎有望在未来实现。
将算法的设计过程自动化，使其能够自发解决难以应对的COPs——这样不仅能节约大量财力和时间，也许还能生成比人工设计更加可行的解决方案（就像我们目前在AlphaGo等成果中所能看到的一样，它已经打败了人类过去通过数千年所取得的经验成就）。运用图例学习早在2016年，一篇名为《基于图表学习组合优化算法》的论文就对这个问题进行了早期尝试。
在这篇文章中，作者训练了一种叫structure2vec的图神经网络，针对几个有难度的COPs制定贪婪的构造解决方案，并获得了非常好的近似比值(生成成本与最优成本之比)。它的基本思路是这样子的：用图谱来表示待解决的问题，然后让图神经网络依据图谱建立解决方案。在解决方案构建过程的每次迭代中，神经网络会观察当前的图表，并选择一个节点添加到解决方案中，然后根据该选择更新图表，接着重复这个过程，直到得到一个完整的解决方案。
论文作者们使用DQN算法来训练神经网络，并证明了习得模型在运用到比所受训练更复杂的问题实例时的泛化能力。这种模型甚至可以很好地泛化到1200个节点的实例中（同时在大约100节点的实例进行训练），同时还能在12秒内生成比商业求解程序用时一小时所求得的更佳解决方案。但是这个方法有一个很大的缺陷，就是他们会使用一个“辅助”方程来帮助图神经网络寻找更好解法。
这个辅助方程是人为设计用于解决特定问题的，而这恰恰是我们想要避免的。这种基于图例的展现方式非常容易理解，因为许多组合优化问题可以自然而然地以这种方式呈现出来，就如下面这个TSP图例所展示的一样：图中的每个节点代表每个城市，节点边缘包含了城际间的距离，如果不考虑边缘属性，类似的图形也能够构建起来（如果我们出于某种原因不考虑距离因素在内的话）。
近年来，基于图形的神经网络模型（无关乎是否具备架构知识）以令人难以置信的速度流行开来。尤其令人瞩目的是自然语言处理领域，它所使用的Transformer架构模型已经成为业内众多任务处理的最先进技术。有许多优秀的文章详细地解释了Transformer 架构，所以本文不再深入剖析，而是做一个简述。Transformer架构是由谷歌研究人员在一篇题为“Attention Is All You Need”的论文中所介绍的。
在这篇著名的论文中，Transformer架构被用于处理NLP中所面对的序列难题。不同之处在于，我们可以向递归神经网络，如长短记忆网络（LSTM），直观输入一系列的输入向量，而Transformer架构中只能以一系列对象的形式输入，且必须采用特殊的方式来让它看见“序列”的排列顺序。这个Transformer是由一个多头自注意力子层和一个完全连接的子层所组成的。
它与图谱的关系在注意力层变得明显起来，而这个注意力层实际上是输入“节点”间的一种信息传递机制。每一个节点都会观察其他节点，同时定向那些对于它们自己看起来更“有意义”的节点。这与在图谱注意力机制（Graph Attention Network）中运行的过程非常相似。实际上，如果使用一个掩码来阻止单个节点向不相邻的节点传递信息，我们将会得到一个等价的过程。
学习如何在没有人类知识的情况下解决问题在论文《注意！学习解决路由问题》中，作者们尝试解决了几个涉及图解路由代理的组合优化难题，包括我们现在熟悉的旅行商问题。将输入数据视为一个图，并将其投入一个经过调整的Transformer构架并在构架中嵌入了图的节点，然后依次选择添加到路由的节点直到完成构建一个完整的路由为止。
将输入数据视为图形是一个比向其提供节点序列更为“正确”的方法，因为只要它们的坐标不变，就能够消除对所输入城市顺序的依赖性。这意味着，不同于上述的节点序列法，无论我们如何改变输入城市的排列，给定图神经网络的输出值都将保持不变。在论文所提及的构架中，图谱是由Transformer 编码器嵌入的，它在为所有的节点生成嵌入层的同时也为全图生成单个嵌入向量。
为了生成解决方案，每次给予一个特殊的上下文向量时都会给出一个单独的解码器网络，这个网络由图嵌入、最后一个和第一个城市以及未访问城市的嵌入组成，并会输出一个未访问城市的概率分布，然后采样生成下一个将要访问的城市。这个解码器会按顺序生成要访问的城市直到整个行程结束，然后根据旅程的长度给予反馈。文中使用了一种名为REINFORCE的强化学习算法来训练模型，这是一种基于策略梯度的算法。
其版本所使用的伪代码如下图所示：文中使用一个滚轮网络来确切评估实例的难度，并定期使用策略网络的参数来更新这个滚轮网络。这种方法在解决几个难题上取得了不错的成效，性能上超越了前文所提到的其他方法。尽管如此，作者们仍在拥有至多100个节点的小型例子上训练和评估模型。虽然这些结果很有希望，但这些例子与现实生活中其他情况相比，犹如小巫见大巫。
扩展到大型问题最近，一篇题为《通过深度强化学习在大型图上学习启发式算法》的论文中向解决现实世界那般规模大小的问题迈出了重要一步。在文中，作者训练了一个图卷积网络来解决诸如最小顶点覆盖(MVC)和最大覆盖问题(MCP)这样的大型实例问题。 针对这些问题，他们采用一种流行的贪心算法来训练神经网络进行嵌入图并预测每一阶段需要选择的下一个节点，在此之后使用DQN算法对其进行进一步的训练。
他们在含有数百万个节点的图上测评了其方法，并取得了比当前标准算法更优异快速的结果。虽然他们确实通过使用动手搭建的启发式来帮助训练模型，但在未来，这种方式可能会消除这种约束，并从白板状态学会解决巨大难题。总之，在无边的搜索领域中，寻找架构是强化学习的一个重要且实用的研究方向。许多批评强化学习的人声称，到目前为止，这项技术仅被用于解决游戏和简单的操作问题，想要将其应用到解决现实问题中还很有很长的路要走。
