百度正用谷歌AlphaGo,解决一个比围棋更难的问题

2019-03-06 16:00 稿源:量子位公众号  0条评论

人工智能,AI

图片来源图虫:已授站长之家使用

本文来自于微信公众号量子位(ID:QbitAI),作者:晓查,站长之家经授权转载。

9102 年,人类依然不断回想起围棋技艺被AlphaGo所碾压的恐怖。

却也有不以为然的声音:只会下棋的AI,再厉害也还是个运动员啊!

百度说:你们错了,它还是一位数学家。

百度硅谷AI实验室的同学们,就在用这个出自谷歌DeepMind的围棋算法,解决一个比围棋复杂得多的数学问题。

为了重新训练这个算法,百度用了 300 张1080Ti和2080Ti显卡。

他们解决的问题,叫做“图着色问题”,又叫着色问题,属于前些天让中国奥数队全军覆没的图论。它是最著名的NP-完全问题之一。

简单来说,就是用尽可能少的颜色,给一张图的顶点上色,保证相邻顶点的颜色不重复。

10 个顶点的简单版是这样的:

image.png

而复杂版……只要顶点足够多,分分钟让人类数学家无从下手,如果有 512 个顶点,这个问题的复杂度会比围棋高出几百个数量级。

在这个数学问题上,运动员AlphaGo表现优秀,最高能将一张图所用的颜色减少10%。

从四色定理谈起

就算你对“图论”、“着色问题”这些词有点陌生,应该也听说过“四色定理”。这是第一个由计算辅助证明的数学定理。

四色定理告诉我们,只需 4 种颜色我们就可以让地图上所有相邻国家的颜色互不相同。

这其实就是一个平面上的着色问题,国家可以简化为顶点,国与国之间的相邻关系可以简化为连接顶点之间的线。对于平面图而言,颜色数k最小等于几?

历史上数学家已经手工证明了五色定理(k=5),但是因为运算量太大,在将颜色数量进一步减少到四种(k=4)时却迟迟无法解决,最终在 70 年代靠计算机才完成证明。

一般来说,我们可以用贪心算法解决这个问题,其基本思路是:先尝试用一种颜色给尽可能多的点上色,当上一步完成后,再用第二种尽可能多地给其他点上色,然后再加入第三种、第四种等等,直到把整张图填满。

或者是用深度优先搜索算法,先一步步给图像着色,若遇到相邻点颜色相同就回溯,再换一种着色方法,直到问题解决为止。

比围棋世界更复杂

如果图的顶点数比较少,以上两种方法还可行,但随着顶点数的增加,以上两种算法的局限性就暴露了出来。

△ 用贪心算法着色和最优解的对比

贪心算法会陷入局部最优解,而深度优先搜索算法的运算量会越来越大,以至于完全不可行。

图着色问题的复杂度随着顶点数增加而急剧增长。当顶点数达到 512 时,其可能得状态数就达到达到了10^790,远超围棋的10^460,当然更是比全宇宙的粒子数10^ 80 多得多。

即使中等大小图的状态数也远超围棋,如果顶点数量达到 1000 万,复杂度会大得惊人,相当于在 1 后面有 4583 万个0。

另外着色问题还有另一个复杂维度,围棋算法可以反复在同一张相同棋盘上进行测试,而图即使顶点相同,因为连接各点的边不相同,结构也不完全相同。

声明:本文转载自第三方媒体,如需转载,请联系版权方授权转载。协助申请

相关文章

相关热点

查看更多