duoluoluo

旅行商问题（TSP）给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。 这是一个 NP 完全问题，当数据规模比较大的时候，目前几乎不可能找到精确解。 所以本篇文章使用基于 Attention 的模型，同时用一个简单但是有效的 greedy rollout baseline 强化学习方式来训练模型。 当然这个模型不止可以用来处理 TSP 问题，但是文章主要是以 TSP 为例进行说明。 模型架构一个问题实例 $s$ 定义为一个有 $n$ 个点的完全图，$x_i$ 表示节点特征，在 TSP 问题中，它是一个 $2$ 维向量，表示在平面上的一个点。TSP 问题的解定义为 $\pi=(\pi_1,\dots,\pi_n)$，是节点的一个排列。 定义基于实例 $s$ 找到解 $\pi$ 的随机策略为： p_{\theta}(\pi|s)=\prod_{t=1}^{n}{p_{\theta}(\pi_t|s,\pi_{1:t-1})}然后基于 Encoder-Decoder 框架，找到解 $\pi$。 Encoder 输入 $x_i$（batchsize, grap ...

概要引入一种新的神经结构，我们将其称为 Pointer Net，用于学习输出序列的条件概率，其中输出序列的元素是对应于输入序列位置的离散标记。 现有的模型（如 sequence-to-sequence 和 Neural Turing Machines）都无法做到这一点，因为它们输入长度是固定的。 在这篇论文中，用 Ptr-Nets 求解了三个组合优化问题的近似解（凸包问题、Delaunay 三角形剖分问题和旅行商问题）。 1 介绍对比了 Sequence-to-Sequence 和 Ptr-Net，Ptr-Net 不是像 Sequence-to-Sequence 那样将一个序列转换成另外一个序列，而是产生一系列指向输入序列元素的指针。 2 模型2.1 Sequence-to-Sequence 模型训练对 $(\mathcal{P},\mathcal{C}^\mathcal{P})$，计算概率 $p(\mathcal{C}^\mathcal{P}|\mathcal{P};\theta)$，$\theta$ 是 RNN 模型的参数，通过概率链式法则可以得到如下计算公式： p(\mathca ...