百度正用AlphaGo算法 解决一个比围棋更难的问题
百度硅谷AI实验室的同学们，就在用这个出自谷歌DeepMind的围棋算法，解决一个比围棋复杂得多的数学问题。
他们解决的问题，叫做“图着色问题”，又叫着色问题，属于前些天让中国奥数队全军覆没的图论。它是最著名的NP-完全问题之一。
简单来说，就是用尽可能少的颜色，给一张图的顶点上色，相邻顶点的颜色不重复。
而复杂版……只要顶点足够多，分分钟让人类数学家无从下手，如果有512个顶点，这个问题的复杂度会比围棋高出几百个数量级。
在这个数学问题上，运动员AlphaGo表现优秀，最高能将一张图所用的颜色减少10%。
就算你对“图论”、“着色问题”这些词有点陌生，应该也听说过“四色”。这是第一个由计算辅助证明的数学。
四色告诉我们，只需4种颜色我们就可以让地图上所有相邻国家的颜色互不相同。
这其实就是一个平面上的着色问题，国家可以简化为顶点，国与国之间的相邻关系可以简化为连接顶点之间的线。对于平面图而言，颜色数k最小等于几？
历史上数学家已经手工证明了五色（k=5），但是因为运算量太大，在将颜色数量进一步减少到四种（k=4）时却迟迟无决，最终在70年代靠计算机才完成证明。
一般来说，我们可以用算决这个问题，其基本思是：先尝试用一种颜色给尽可能多的点上色，当上一步完成后，再用第二种尽可能多地给其他点上色，然后再加入第三种、第四种等等，直到把整张图填满。
或者是用深度优先搜索算法，先一步步给图像着色，若遇到相邻点颜色相同就回溯，再换一种着色方法，直到问题解决为止。
如果图的顶点数比较少，以上两种方法还可行，但随着顶点数的增加，以上两种算法的局限性就了出来。
算陷入局部最优解，而深度优先搜索算法的运算量会越来越大，以至于完全不可行。
图着色问题的复杂度随着顶点数增加而急剧增长。当顶点数达到512时，其可能得状态数就达到达到了10^790，远超围棋的10^460，当然更是比全的粒子数10^80多得多。
即使中等大小图的状态数也远超围棋，如果顶点数量达到1000万，复杂度会大得惊人，相当于在1后面有4583万个0。
另外着色问题还有另一个复杂维度，围棋算法可以反复在同一张相同棋盘上进行测试，而图即使顶点相同，因为连接各点的边不相同，结构也不完全相同。
这些更复杂的问题对算法的训练和推理提出了极大的挑战。而AlphaGo曾在解决这类复杂问题上取得了很大的成功，研究人员也很自然的想到了用它来解决图的着色问题。
对于这类问题，我们一般采用式搜索算法（heuristic search），就是在状态空间中的搜索对每一个搜索的进行评估，得到最好的，再从这个进行搜索直到达到目标。
AlphaGo使用的蒙特卡洛树搜索（MCTS）用的就是一种式搜索算法。
△蒙特卡洛树搜索算法示意图：选择径；扩展树；由神经网络执行模拟；将最终结果反向，更新径节点。
AlphaGo下棋通过正是这种方法，计算当前棋盘上获胜概率最大的点，直到赢棋为止。
图着色问题与围棋也有类似之处，它的每一步棋就是给接下来的点填上颜色。它和围棋和象棋一样都可以用强化学习来解决问题，差别则是励。
在图着色问题中，最明显的励选择是颜色种类，使用的种类越少越好。而在围棋和象棋中，励是游戏的胜负结果。
在棋类游戏中，让算法在对弈中进化是很一件很自然的事，让表现最好的学习算法与自己对抗，这就是AlphaGo的升级版本AlphaGo Zero。
AlphaGo Zero没有学习人类棋谱，它只是懂得围棋规则，在不断的对弈中获得提高，谷歌只用了21天，就让这个0基础的升级版打败了5-0战胜柯洁的AlphaGo Master版。
当AlphaGo进化到自学版本AlphaGo Zero后，它就更适合做图着色问题了，因为着色问题是没有所谓“人类棋谱”可以学习的。
在图着色问题种，研究人员让AlphaGo Zero与其他算法比赛，看谁用的颜色种类少，这就是算法的励机制。
和AlphaGo一样，图着色算法也有策略网络（p-network）和价值网络（v-network），p是顶点涂某种颜色的概率，v是最终颜色数量少于之前最佳算法结果的概率。
1、可扩展性（Scalability）：线性O（V）或线性对数O（E+VlogV）时间复杂度，它在更大的图形（比如1000万顶点）上也能使用。
2、完整图形上下文（Full Graph Context）：不同的图有不同的着色策略，因此网络需要有图形结构的信息。
问题上下文（problem context）是根据刚刚着色的顶点，来安排接下来对哪些顶点进行着色。它在任务开始和结束的时候都是零。问题上下文中包含的顶点数是一个超参数，在实验中设置为8。
可能颜色上下文（possible color context）是以上顶点集合每种可能用到的颜色。它也是一个超参数，在实验中设置为4。
策略网络使用全局图形上下文（global graph context），它负责计算将每个颜色选择分配给当前顶点的概率。
随着填充过程的进行，颜色数量会逐渐增加。为了支持颜色数量的变化，它会首先处理每种颜色，产生一个非标准化分数，然后通过seq2seq模型对该分数进行处理，该模型还会考虑与其他颜色的依赖性。最终通过softmax操作得出归一化的填充颜色概率。
策略网络利用了具有相同颜色的节点之间的局部关系，提高了准确性，同时还降低了大图计算的时间复杂度。
价值网络负责从输入数据预测着色问题最终的结果。 问题上下文（problem context）中的顶点与着色顺序存储在对应的序列中。使用seq2seq模型处理此序列，然后将这个序列与图形上下文（graph context）组合起来，并将它们馈送到完全连接的reLU层中，最终结果输入softmax，计算出胜利、失败或平局的概率。
研究人员用FastColorNet的强化学习过程来训练图着色问题，图形大小从32个顶点到1000万个顶点不等。
在32K到16M个顶点的图上进行测试，FastColor在训练集中使用的颜色比以往的式搜索算法提高了5%-10%。 尽管在测试集有所逊色，但性能也比先前的算法高出1%-2%。
虽然提升比例看起来不高，但这种算法显示出解决此类问题的潜力。Twitter上一位网友这样评价：这篇文章以线性复杂度O（n）解决了一个NP完全问题。
量子位正在招募编辑/记者，工作地点在中关村。期待有才气、有热情的同学加入我们！相关细节，请在量子位号（QbitAI）对话界面，回复“招聘”两个字。
