使用PageRank对金庸武侠的功夫进行排名

金庸武侠人物功夫排名是互联网上的年经帖。这种排名首先是在同一本小说的武侠世界进行，然后又扩展到整个金庸武侠世界。各种版本排名依据不一，又带有很强的主观性，因而得出的结论往往引发极大的争议。

在理想状况下，所有侠客切磋过且能得到一个偏序关系。这时候得出的排名最没有争议。举例来说，在《笑傲江湖》里，左冷禅败给岳不群、令狐冲，岳不群败给令狐冲，令狐冲败给东方不败。如果仅考虑这四个人，其排名自然为：东方不败、令狐冲、岳不群、左冷禅。可是在一般武侠世界里，首先并不是所有人物之间都打斗过；其次比武时胜负也不一定能够构成一个偏序链。比如《笑傲江湖》几个主要高手之间切磋的结果大致为：

如何排列这些人物之间的功夫就成了问题。

关于这个问题，我们可以用PageRank等向心值算法来解决。其想法如下，一个人的功夫，可以由其他人的评价来进行估计。这个评价可以是比武，也可以是间接评价，比如任我行曾对风扬清有过很高的评价。如果甲败给乙，那么甲必然对乙的功夫有较好的评价。在甲乙打平的情况下，可以认为双方对彼此的功夫有好的评价。当然，从功夫好的人得到的好评要比从功夫差的人得到的好评要好。所以一个人$i$的功夫（用$p_i$来表示）: \[
p_i = \alpha \cdot \sum_j A_{ji} f_j p_j + \beta_i, \quad \sum_i p_i = 1.
\] 这里，$\alpha$ 和 $\beta_i$ 是两个基于先验经验确定的值，$f_j$ 是一个关于评价者的函数，$A_{ji}$是该图的邻接矩阵或『评价矩阵』。根据这些『评价』种类的不同，我们可以赋予不同的权重。一般的胜负定为1，令狐、任、向三人围攻定为3，佩服、欣赏亦定为1，左冷禅击败任我行以后受伤严重，不能再战斗，可为0.9。在最简单的PageRank里，$f_i = 1/\max(1, d^{\text{out}}_i)$，换句话说，一个人被打败的次数越多，他对别人的评价贡献越小。在改进模型中$f_i$也可以换成其他合适的函数。

我们将这个想法应用于上面提到的《笑傲江湖》的排行问题。令$\alpha=0.85$, $\beta = (1-\alpha)/N$, 这里N为顶点个数。得到的风评分使用『权重』和不使用『权重』两种情况为：

第一种情况得到排名为：东方不败、任我行、令狐冲、方证、风清扬、左冷禅、岳不群、冲虚、向问天。 讨论：左冷禅的功夫高于岳不群是因为左冷禅曾战胜高手任我行。任我行排名比令狐冲高是因为他跟多个高手过过招。

第二种情况得到的排名为：任我行、令狐冲、东方不败、方证、风清扬、冲虚、左冷禅、岳不群、向问天。讨论：任我行、令狐冲排名比东方不败靠前是因为他们参与的决斗比较多，而在这里东方不败的名声主要来源于她与三大高手的决斗。假如不将此赋予较高权重的话，东方不败无法鹤立鸡群。这也显示了权重的重要性。

当然所有的参数可以根据读者的经验调节，从而得到一个合适的排名。为了得到合适的排名，也需要深度挖掘其他次要人物的贡献。由于很多出场人物并没有比较得到过评价，这时候他们先验的江湖名声就变得重要起来。进一步地，如果能找到一些连结各个金庸武侠小说的人物（比如少林寺、丐帮、武当派等），这个办法也可以用来做金庸武侠世界的综合排名。

参考：
cf. Liyun: 十八般武艺，谁主天下。写成此文后，搜到这篇文章用PR来给金庸小说中的武器打分。

物理学家加入数学盛宴

有一个古老的数学命题说,

宴会定理: 在一场不少于6个人宴会中, 一定存在三个人, 他们之间要么彼此相识, 要么彼此不相识. 

 图一用图形表示了宴会定理情形之一.

图 一: 用图表示的六人宴会. 其中使用图的顶点作为与会人士, 蓝色的边表示陌生, 红色的边表示相识. 宴会定理断言, 一定会存在一个单色(蓝色或红色)的三角形. 读者可以挑战这里的一个Java applet.

当参加宴会的人数为5时, 上述命题不再成立. 图二给出了一个反例. 宴会人数大于6, 我们只要考察其中任意6个人之间的关系, 即可知命题成立. 因此, 可以得出这样的结论: 要使宴会命题成立, 宴会的人数有一个下限. 这个下限, 在数学上被称为Ramsey数, 以纪念英年早夭的英国数学家F. P. Ramsey (1903 - 1930, 去世时年方26岁).

图 二: 一个顶点图使用双色染色但不存在单色三角形的例子. 图例同图一.

Ramsey考虑了这个问题的推广. 比如要使宴会中的一定存在四个人两两相识或陌生, 宴会人数的下限是否存在, 如果存在, 是多少? 五个人, 六个人, 乃至多人的情形将如何? 甚至, 对于相识和陌生人数不等的情形又如何? 1930年, 他最终能够证明这样的下限对任意情况都是存在的. 这样一个定理如今以他命名, 被称为Ramsey定理, 大意如下:

对于任意正整数 $s$ 和 $t$, 存在一个正整数 $n$, 使得当一场宴会的人数不少于 $n$ 时, 其中一定存在要么$s$个人相识要么 $t$ 个人不相识的情况. 

这样的整数 $n$ 统称为Ramsey数, 记作 $R( s, t )$. 宴会定理是Ramsey定理的一个特例, 即 $ s = 3, t = 3$, 而 $R( 3, 3 ) = 6$.

Ramsey证明了Ramsey数对于任意正整数 $ s $ 和 $ t $ 都存在, 却没有给出它的算法. 事实上, $R(s, t)$ 的计算是困扰数学家的难题之一. 迄今为止, $s > 3, t > 3$ 的Ramsey数人们仅仅知道9个, 其他的数人们仅知道他们的大致范围 [1]. 使用穷举方法, 对于有 $n$ 个人参加的宴会, 共有$2^{(n-1)n/2}$ 种情形. 譬如, 已知 $R(5, 5)$ 在 $43 - 49$ 之间. 为了验证 $R(5, 5) = 43$ 是否成立, 需要穷举 $2^{903}$ 种情形. 使用2 GHz的计算机 (每秒计算 $2^{10}$ 次), 仍需 $10^{261}$ 年. 对比之下, 宇宙的年龄才 $10^{11}$ 年.

为了说明Ramsey数的计算复杂度, 匈牙利著名数学家Paul Erdos(1913 - 1996)曾讲过一个故事 [2].

假设有个比我们强大很多的外星人军团在地球登陆, 要求地球人给出 R(5, 5) 的准确值否则将会摧毁地球. 那么, 我们应该立刻集合所有数学家和所有计算机来找到它. 但假如他们要求的是 R(6, 6) 的值, 我们转而应当设法消灭强大的外星人.

现在物理学家正在加入这场盛宴. 美国物理学家Frank Gaitan和Lane Clark提出, Erdos和其他数学家不必对计算Ramsey数的复杂性感到悲观. 因为未来量子计算机也许可以解决这个问题 [5]. 据APS Physics报道, 他们提出了一种可以计算Ramsey数的量子算法 [4]. 在这种算法中, 他们引入了一个 Hamilton量, 其态空间包含了所有图的构型. 同时当图的顶点的个数小于Ramsey数时, 此Hamilton量的基态能量为零. 否则基态能量不为零. 他们首先使用一个易于获得的含时Hamilton量, 然后绝热地演化到前述Hamilton量, 最后再测量此时的基态能量. 需要注意的是, 由于量子力学的特性, 量子计算给出的结果是随机性的. 只能够通过多次测量, 以较高的概率确定Ramsey数的值.

由于量子算法可以使用普通计算机上来模拟, 尽管速度会非常慢, Gaitan和Clark使用他们的算法对较小的几个Ramsey数的值进行了模拟并与数学家给出的结果相符 (表 一).

表 一: Gaitan & Clark使用他们的算法对小Ramsey数进行的模拟结果.

Gaitan和Clark的算法, 给使用量子计算机解决数学和科学中的计算难题带来了新的希望. 人们已知, 对于某些能够在经典计算机(Universal Turing Machine)上快速验证(P), 但至今未找到算法快速解决的问题(NP), 可能能在量子计算机上快速解决(BQP). 整数分解质因数的 Shor算法提供了第一个这样的例子. 进一步, 量子计算机还可能快速解决某些甚至不能在经典计算机上快速验证的问题. Gaitan和Clark的算法有可能证明量子计算机的某些远超经典计算机的计算能力. 无论如何, 物理学家加入这场数学盛宴, 将给未来科学带来难以预计的震撼.

图 三: 量子计算, 在计算复杂性中可能的位置. P 表示可以在多项式时间内解决的问题. NP表示, 可以在多项式时间内验证(证实)的问题. 类似的co-NP则是可以在多项式时间内证否的问题. NP-complete 或 NPC 是NP问题中最难的一类. PSPACE 是可以以多项式空间内, 以多项式时间解决的问题. BQP是量子计算机可以以多项式时间解决的问题. 在计算科学中, NP = P? 是个悬而未决的重大问题. 进一步, 人们问, P = PSPACE? 一般认为, NP != P. 而对量子计算来说, BQP则被认为包含P, 与NP有交集但不包含NP的全部 [3].

参考:
[1] Weisstein, Eric W. "Ramsey Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RamseyNumber.html
[2] L. Graham and Joel H. Spencer, in Scientific American (July 1990), p. 112-117
[3] http://en.wikipedia.org/wiki/Quantum_computer#Relation_to_computational_complexity_theory
[4] Synopsis: Quantum Search for Elusive Numbers
[5] Frank Gaitan and Lane Clark, Ramsey Numbers and Adiabatic Quantum Computing, PRL 108, 010501 (2012)