显示标签为“算法”的博文。显示所有博文
显示标签为“算法”的博文。显示所有博文

2014年2月1日星期六

使用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来给金庸小说中的武器打分。

2012年1月26日星期四

经典和量子的"冒牌排序"

计算机科学中有一个近乎玩笑的排序算法称为"冒牌排序" (bogosort), 又叫作"猴子排序" (Monkey Sort). 这个算法被称为"典型的糟糕算法". 实现它的步骤是:
第一步: 检查数组是否有序;
如果有序返回结果;
如果乱序:
第二步: 随机排列该数组, 返回第一步.
"冒牌排序"等价于把一堆扑克随机洗牌, 然后检视是否有序. 如果无序, 则继续重复下去. 可想而知, 这个算法的效率是极其低下的. 它的平均时间复杂度为$O(n \cdot n!)$. 相对比之下, 常用的快速排序平均只需要 $O(n \cdot \log n)$ 次操作.

有个调侃量子计算机的笑话, 说利用冒牌排序可以在 $O(n)$ 次操作中完成排序. 原理如下:
第一步: 利用量子计算机将数组随机排列. 根据量子力学的多世界诠释, 每一种可能的排列都会出现在某一个宇宙中.
第二步: 检查每一个宇宙中的数组是否有序. 在每个宇宙中, 这需要 $n-1$ 次操作.
第三步: 摧毁仍然乱序的宇宙. 唯一的幸存者只看到过 $n-1$ 次操作.
算法第三步的实现交给读者作为练习.

当然实际上这个算法的第三步是不可能实现的 (假定多世界诠释是对的, 并且这个数组是量子数组). 因为首先每次测量将会使观察者选择某一个具体的世界, 量子数组亦将选择某一种排列方式. 观察者当然不可能再跳出这个宇宙 (即使摧毁这个宇宙, 因为观察者是宇宙的一部分), 更不用说摧毁其他宇宙.