（计算机应用技术专业论文）最少比较排序问题研究.pdf

摘要 摘要 最少比较排序问题就是要研究足以将n 个元素排序所需要的最少比较次数 s ( n ) ，这是排序理论的一个基础性问题。s t e i n h a u s 在他的m a t h e 腿t i c a l s n a p s h o t s 一书中提出最少比较排序问题，d k n u t h 在他的t h ea r to fc o m p u t e r p r o g r a 啪i n g 第三卷中专门用一节讨论这个问题，他在习题中给了计算s ( 1 4 ) 个4 9 分的高分。 虽然比较次数不是衡量排序方法有效性的唯一方式，但是，仔细地研究比较 次数会给我们带来大量的洞察排序过程本性的有用知识。自从1 9 6 5 年m a r k w e l l s 用穷举法证明s ( 1 2 ) = 3 0 以来，很少见到关于最少比较排序问题的文章。 鼬l u t h 在他的巨著 h l 2 0 0 2a l l d2 0 0 4 ，m p e c z a r s k ii 蛐r o d u c e dl l i sm e t h o do f c a l c u l a t i n gs ( 1 3 ) ，s ( 1 4 ) ，s ( 2 2 ) ， a i l dt h er e s u l ts ( 1 3 ) = 3 4 ，s ( 1 4 ) = 3 8 ，s ( 2 2 ) = 7 1 i nh i sp 印既 i nt l l i sp 印w ep r o p o s e dan 哪a l g o r i t h m w mb a s e d m p e c z a r s k j s m e t h o d 锄dr e - c a l u l a t e ds ( 1 3 ) ，s ( 1 4 ) ，s ( 2 2 ) o u rr e s u hp r o v e dt h ev a l i d i t yo f m p e c z a r s l 【i sm e t h o d 锄dt h ea l g o r i t h me m c i e n c yg o t 野e a t l yi m p r o v e di n 黜 聊讧 t h c nw ec a l u l a t et h cs ( 1 5 ) ，s ( 1 9 ) u s i n gp 盯a l l e l i z e dm w e l l s 锄dm p e c 功r s i 【i s a 1 9 0 r i t h m 锄dr e w 呱a n dg a ts ( 1 5 声4 2 ，s ( 1 9 产5 8 t h ea l g o r i t h mo f c o u m i n gl i n e a re x t s i o n si st l l eb a s ea l g o d t h mo fc o m p u t i n g s ( n ) 锄di nw j l l s s “g o f t t h m “t a k e s7 0p e r o 眦o ft o t a l m p u t i n gt i m e s w b i m p r o v e dt h ea l g o r i t h mo fc o u m i n gl i n e 盯e x t s i o 邶i nt h i sp 印e r 锄dc a l c u i a t e dt h a t s ( 1 9 产5 8 t h e 既p e r i m e ms h o wt h 砒o i | rn e wa l g o t h mc a ng r e a t l yi m p r o v et h e e m c i e l l c yo f c o u m i n g1 i n e 甜e 毗e n s i o l e y 肿r 血：s o m 嗥m j 硝m u m - c o m p 枥s o ns o r t i n c o u n l i n gl j n e a r 联t e n s j o n s 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 【武班一 a 一6 年r 月? o 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 “ 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位做作者签名c 武下、 矗一6 年f 月彳d 日 第一章概述 第一章概述 2 0 世纪6 0 年代的计算机厂家估计，当把他们的所有顾客都考虑在内时，在 他们的计算机上，将有超过2 5 的运行时间花在排序上。事实上，有许多计算 机装置，其中的排序，就用去计算时间的一半以上。因此我们说，排序有许多 重要的应用，值得作为一个重要问题认真研究 实际上，目前已经发明了许多不同的排序算法，主要分为选择排序、插入排 序、交换排序、合并排序、分布排序等几类。k 伽t h 在他的计算机程序设计艺 术一书中，仅内部排序一章就介绍了至少2 5 种排序算法，这只是迄今为止已 经发明的排序算法的一小部分。可惜，人们还不知道“最好”的排序方法，目 前许多最好的方法都是针对特定的机器，根据特定的目的，对特定对象进行排 序得到的。衡量算法好坏的指标主要有正确性、时间代价、空间代价、最优性 等，衡量排序算法也不例外。 。 虽然比较次数不是衡量排序方法有效性的唯一方式，但是，仔细地研究比较 次数，会给我们带来大量的洞察排序工程本性的有用知识，也会帮助我们增进 在其他情况下解决可能碰到的更为普遍的问题的能力。 第一节最少比较排序问题 1 】 给定n 项记录：u l ，u 2 ，i l n ，其中一个域被称为关键字伥e y ) ，关键字值 k l ，k 2 ，k n 属于同一个全序集。排序就是要重排n 项记录为u l l ，u | 2 ，u 。 其中a l ，a 2 ，a n 为l ，n 的一个排列，使关键字满足： l 【l l k a 2 k 我们用一个扩展二叉树结构表示三个数的比较排序过程，如图1 1 。 树中内部节点包含两个下标i j ，表示u i 和u ，的一次比较，左子树表示l 【i b 时所需采取的动作，右子树表示i 【i k i 时所需采取的动作。树的外部节点包含下 标的一个排列a i ，a 2 ，a 3 ，表示已经得到全序k i k | 2 虹。实际的算法中通常 需要移动数据，我们只对比较感兴趣，因此完全忽略数据移动。图1 2 中3 ：1 的 比较是多余的，因为k 1 也，娩l 【3 ，所以没有必要进行k l 和l 【3 的比较，没 有一个排列对应于节点3 ：l 的左子树。 第一章概述 下文中，为简化叙述，我们不使用关键字k i ，对两个元素进行比较直接记为 u i 屿，而不是k 畸。 第0 层 第1 层 第2 层 第3 层 图1 1 对3 个元素排序的一个比较树 图1 2 多余比较的例子 我们假定没有做多余的比较，则每一个扩展二叉树的外部节点都对应一个排 列。输入关键字的所有排列都是可能的，而且每个排列都定义从根到外部节点 的唯一路径。由此推知，在一个对n 个元素进行比较而没有多余比较的比较树 中，恰有n ! 个外部节点。 令s ( n ) 为足以将n 个元素排序的最少比较次数，则比较树的所有内部节点都 在小于s ( n ) 的层次内，则显然在树中至多有2 8 吣个外部节点，因此就有； 聆! 2 s ( ”) 由于s ( n ) 是整数，我们变换这个公式以得到最少比较次数的下界： s ( 胛) 1 1 9 胛! i = c ( 刀) 在我们常用的排序方法中，需要最少比较的三个算法是二叉插入、树选择和 直接两路合并。二叉插入的最大比较次数是： b ( ，1 ) = 芝n g 七 = 刀r l g 刀 一2 1 + 1 七= i 设n = 2 。1 + 2 q + 2 4 ，其中e 1 e 2 醴，t o ，则两路合并插入的最大比较 次数是： 2 第一章概述 f ( 月) = 1 - 2 “+ ( 如+ 七一1 ) 2 靠 七一1 树选择算法或者有和二叉插入相同的最大比较次数，或者有和两路合并相同的 最大比较次数。 第二节合并插入排序 h b d e m u t h 发现了对5 个元素进行7 次比较就能排序的方法。他首先比较 k l ：k 2 ，k 3 ：k ，然后把每对的较大者拿来比较，得到的偏序可以表示为图1 3 。 这是一个有向图，我们用节点的左右关系表示大小关系，而省略了有向图边上 的箭头 。 这时经过两次比较可以把e 插入 如，d ) 当中的适当位置，再 经过两次比较可以把c 插入小于 d 的序列中。 l | f o r d 和s j o l l | l n 对这个方 法进行了推广，得到了合并插入 方法描述如下： a d e 图1 35 个元素进行3 次比较得到的偏序 l 、对n ，2 个不相交的元素对，进行逐个比较。若n 是奇数，则剩余1 个元 素；， 2 、用合并插入的方法把每对元素中较大的元素进行排序( 递归的过程) ； 3 、把每对元素中较小者插入已经完成排序的序列中。假设用图1 4 的方法 描述步骤2 得到的偏序，较小的元素从左到右命名为b l ，b 2 ，b b 唰，则插入的 顺序为：b 3 ，b 2 ，b 5 ，k b l l ，b l o ，b 6 ，。 b l a 1a 2a 3科a 5a 6a 7a 8 a 9 a 1 0 1 图1 42 1 个元素合并插入排序步骤2 得到的偏序 例如考虑2 1 个元素的排序问题，开始先比较1 0 对关键字，k l ：k 2 。 3 第一章概述 k 3 ：l 【4 ，k 1 9 ：k 2 0 ，然后对每对元素中较大者用合并插入方法排序，得到偏序如图 1 4 。 我们分别用f ( n ) 、b ( n ) 、l ( n ) 表示合并插入、二叉插入和两路合并的最大比 较次数，得到表1 1 ，下文中为书写方便，s ( n ) 、c ( n ) 、f ( n ) 有时写为s n 、c n 、 f n 。 nc ( n ) f ( n ) b ( n ) l ( n )nc ( n ) f m ) b ( n ) l ( n )nc ( n ) f ( n ) 2l l l ll o2 22 22 52 71 85 35 4 3333 。 3 l l 2 6 2 62 9 3 01 95 75 8 455551 2 2 9 3 03 33 32 06 26 2 577891 33 33 43 73 82 l6 66 6 6 l o 1 01 1l l 1 43 73 8 4 l 4 l2 27 07 l 71 31 31 41 41 54 l4 24 54 52 37 57 6 81 61 61 71 71 64 54 64 94 92 48 08 l 91 91 92 12 51 74 95 05 4 6 52 5 8 4 8 6 表1 1 几种排序方法的最大比较次数比较 由表中我们可以看出，n 7 0 ，从而证明了 合并插入法对n = 1 2 和n = 2 2 都是最优的，s ( 1 2 产3 0 ，s ( 2 2 ) _ 7 1 。 根据排序的效率，我们可以估计计算s ( n ) 的过程中每次比较生成的新偏序的 数量，但是排序的效率对计算s ( n ) 并没有直接的帮助，只能作为参考，从一个方 面反应排序的情况。例如，m p e c z a r s k i 已经证明s ( 1 4 户3 8 ，就是说1 4 个元素在 3 7 次比较中达不到o 6 3 的排序效率，而s ( 2 1 ) ；0 6 9 说明2 1 个元素在经过6 6 次 比较以后，仍然能达到o 6 9 的排序效率 5 第二章排序与线性扩展计数 第二章排序与线性扩展计数 线性扩展计数是计算s ( n ) 的算法中最重要的算法之一，在p e c z a r s k i 的算法 中，计算线性扩展数的时间占用了程序总运行时间的7 0 以上。g b 如h 呐e u 和p w 砸“e r 证明了线性扩展计数是n p - 完全问题【2 】，m p e z c a r s i 【i 给出了一个线 性扩展计数方法【3 l ，是目前最好的数学方法。我们仍然使用这个方法，但对它 的实现进行了改进，取得了很好的效果。 第一节基本概念 设u = ( u 0 ，u l ，1 是待排序的元素集。对u 进行排序可以看作生成一个 偏序 u ，r 队列，由于u 是固定的，所以用r 来表示 u ，r ) 。这个队列从完全无序 的偏序r o = ( ( u ，u ) ：ueu ) 开始，以全序 u 4 i ，u a 2 ，u 。) 结束。队列中的每个偏序， 总是由它前面的一个偏序经过一次比较来生成。设经过c 1 次比较我们得到偏 序r ，第c 次比较我们将比较屿和l l i c ，不失一般性，设旭，u k ) 叠r 且( u k 屿) 仨r ，如 果比较的结果是i l | k ，则第c 次比较得到偏序什 u j ，u k ) ，我们用r 呐u k 表示。 定义l ：设r 是u 上的偏序，l 是u 上的全序，r 1 ，称l 为r 的一个线性 扩展。 每个偏序至少有一个线性扩展，令e ( r ) 表示r 的线性扩展数，u 上完全无序 的偏序f o 有n ! 个线性扩展，全序只有个线性扩展。对任意的偏序r ，经过 c 次比较能得至一个全序，则称r 可以经过c 次比较完成排序。下面的定理1 是信息论下限的一个一般化形式。 定理1 ：若偏序r 能经过c 次比较完成排序，则r ) 2 c 。 对偏序r 来说，f = “v ) ：“u ) r ) 称为r 的对偶偏序。 定义2 ：设r 1 和r 2 是集合u 上的偏序，r l 和r 2 或r l 和r 2 是同构的偏序，则 称r l 和r 2 是等价的偏序。 则有如下定理； 定理2 ：等价的偏序完成排序需要相同的比较次数。 设似r ) 是偏序，集合a u ，下面的叙述中，我们记偏序( 气r n a a ) 为r i a 。 6 第二章排序与线性扩展计数 着u u ，我们用r u 表示比u 大的元素的集合，r u 表示比u 小的元素的集合， 即r u = v ：( u ，v ) u 八u v ) ，r u = v ：“，u ) u 八u v ) 。 第二节线性扩展计数算法 线性扩展计数被证明是套m 完全问题，这表明线性扩展的计数并不比生成线 性扩展容易。因此，我们不能期望设计一个多项式时间阶的线性扩展计数方法。 这里给出一个到现在为止最好的线性扩展计数算法。 定义3 ：设( u r ) 是一个偏序，d u ，d d ，则称( a ，b ) 是d 上关于d 的可接受 的划分，若满足下列条件： 1 、a u b = d i d ) 且a n b = o ； 2 、若( a ，d ) r 且a d ，贝0 a a ； 3 、若( d 。b ) r 且b d ，贝4 b b ； 4 、对任意的a a 和b b ，有( b ，a ) 隹r 定理3 ：设( u ，r ) 是一个偏序， l 、若a b u ，a n b = 巾，且对任意的a a 和b b ，有“b ) 仨r ，则 p ( ，1 4 ub ) = p ( ，i 彳) e ( ，l b ) c 嚣例 ( 1 ) 2 、若d 量u 且d d ，则； p ( ，j d ) = e ( ，i 爿) p ( ，j 动 4 j 这里的求和是对d 上所有关于d 的可接受划分求和。 该算法的中心思想是将问题划分为更小的问题加以解决。考虑表示偏序的 图，( i ) 式是针对非连通图的，很好理解。( 2 ) 式是针对连通图的。我们找到一个 d ，使r l d 中与d 相关的元素数最大，也就是d 上所有关于d 的可接受划分数 最小，则计算e ( r ) 最快。 例如图2 1 表示集合u = i i o ，u l ，u 1 3 上的一个偏序r ，我们选d = 1 1 5 ，则： e ( ，) = e ( r i 甜o ，甜l ，甜2 ，“3 ，甜4 ，甜l o ，甜1 l ) e ( ，1 甜6 ，甜7 ，甜8 ，”9 ，甜1 2 ，“1 3 ) ) + e ( ，i “o ，甜2 ，“3 ，“4 ，甜l o ，甜l l ) e ( r i “i ，甜6 ，“7 ，8 ，材9 ，甜1 2 ，甜1 3 ) + 口( ，1 甜o ，越i ，”2 ，甜4 ，甜l o ，“) ) p ( ，i 甜3 ，甜6 ，甜7 ，甜8 ，甜9 ，甜1 2 ，甜1 3 ) ) 7 第二章排序与线性扩展计数 + e ( r l “o ，“2 ，“4 ，“l o ，“l l ) 口( r i “l ，“3 ，甜6 ，甜7 ，掰8 ，甜9 ，“1 2 ，甜1 3 ) ) + p ( r l 甜o ，“l ，“2 ，“3 ，甜4 ，“8 ，甜l o ，甜1 1 ) ) 幸p ( ，j 甜6 ，“7 ，甜9 ，甜1 2 ，“1 3 ) ) + e ( r i 甜o ，甜2 ，缸3 ，甜4 ，甜8 ，“l o ，甜1 1 ) ) g ( ，i “1 ，甜6 ，“7 ，“9 ，甜1 2 ，“1 3 ) ) + e ( ，i “o ，就l ，甜2 ，甜4 ，甜8 ，砧1 0 ，甜1 1 ) ) b ( ，i 鸭，材6 ，甜7 ，9 ，甜1 2 ，l f l 3 ) ) + p ( ，i ，甜2 ，甜4 ，“8 ，甜1 0 ，甜1 1 ) ) 8 ( ，i “l ，“3 ，“6 ，甜7 ，“9 ，甜1 2 ，甜1 3 ) ) = 2 4 1 2 + 1 2 8 4 2 + 1 2 6 7 2 + 1 9 2 1 2 + 8 4 7 2 2 + 7 2 5 0 4 = 6 1 0 5 6 u 4u l u 8 u 6 图2 1u 上的个偏序 定理3 给出的线性扩展计数算法是一个递归的过程。若i d 产1 ，则砸l d ) = l 。 若| d | = 2 ，设u e d ，若r mur 【u 】n d = 中，则e ( r p 片，否则砸l d ) = 1 。对于若 3 i d i 5 的偏序，m p e c z a f s k j 定义了一个保存r i d ) 的数组e 口，并设计了一 个简单的哈希函数m e t a ，查表可以得到e ( r l d ) 。 若l d l = 3 ，对所有u d ，计算t h e t a = l ，【“】i ，e 】= ( 6 ，3 ，2 ，1 ，则 e ( r l d ) = e 【t h e t a 】 若j d i = 4 ，对所有u d ，计算t h e t a _ 研i ，【“】n d i 】，其中钆】- o ，1 ，4 ，l o ) ， 数组e 【】= 2 4 ，1 2 ，6 ，6 8 ，4 ，3 ，o 4 ，2 ，6 ，3 ，2 ，o ，2 0 ，l ，则e ( r i d ) = e 【t h e t a 】。图2 3 给出了 所有f u j = 4 的偏序，由图可以看出，当t h e t a = 2 或5 时有哈希冲突，还需要判 断 若i d i - 5 ，若至少有一个d d ，满足l r d l - lr d i ：o ，则定义d l - d d ， e ( r io ) = 5 e ( r l d l ) ，否则对所有u d ，计算七l 爿，【“】n d l ，j 2 刊，【“】n d l ， f j 搪船= 口陋l 】防2 】，则e ( r j d ) 2 e 【t h e t a 】。其中6 和e 【】定义如下： 8 第二章排序与线性扩展计数 l =0 l 234 针o ，i 】= ol3 1 0 纠1 ，i 】；o 685 p 【2 ，i 】= l 8l 吼3 ，i 】= 3 5 针4 ，i 1 = 1 0 i =3 46 91 0 1 l 1 2 1 3 1 4 1 51 71 8 。e i 】= 1 61 8 1 4 1 22 491 l 4 8 71 26 i =2 0 2 22 42 5 2 72 82 93 l3 23 84 14 2 e i = 82 6 83 5 4l4 62 3 图2 3 给出了所有i u l = 5 且不存在满足i “d l - lr d i = o 的d 的偏序。 若i d p 5 ，则按照定理3 ( 2 ) 式用递归的方法求c ( r 1 d ) 。 二么一 _ 二_ n l c 协；o1 l i e 忸= l t l l c 协= 2t h i 池= 2m e 忸- 3 e ( r ) ；6e ( r ) _ 3c ( r ) - 2c ( r ) - 2 c ( r ) = l 图2 2d 上所有偏序，i d p l 3 ：= 么二h_ _ _ _ 卜_ t b 或a = o c ( f ) = 2 4 t l l c t a = l c ( r ) = 1 2 t b c 诅= 2 啪= 6 也c t a = 2 c ( r ) = 8 t b e t a = 4 c ( r ) = 8 t l l 咖= 5 e ( r ) = 4 巳习x 伽亭t a = 3 也咖= l on l e t a - 5 也e t a = 6 恤t a = l lt h 咖= 8 啪c ( r ) = 6e ( r ) = 5e ( r ) - 3e ( r ) = 3啪= 4 让 m 咖= 9 啪= 2 t h 咖= 1 4 啪宅 n 珥t a = 1 2 e ( f ) = 2 也e t a = 1 5 e ( r ) = l 图2 3d 上所有偏序，i d i = 4 9 第二章排序与线性扩展计数 芝鼍翟 也咖= 31 b e 诅= 4 e ( r ) = 1 6 e ( f ) = 1 8 t h e t a ；6t h e 慷= 9 e ( r ) ；1 4o ( r ) = 1 2 专 啪喇r ) = 9 啪= l l xz _ o ) ，应用定理3 ( 1 ) v ：= m i i l e l e m e 删妇t ) a 1 _ s u b s e t ( v j 吒v )，a l 是定理3 ( 1 ) 中的集合a v - s e t ：2 v j e t - a 1 b ：= l a l i t _ t 口 c ：= c b i f ( b 5 的d ，假设s e l e c t v o 选 择的节点为v ，n 1 = l r 【v 1 i 且1 1 2 = 旷【v 】i ，则计算e ( r ) 的过程中，总共需要保存的d 的个 数为k l 2 n 1 4 + i 【2 + 2 正4 o ) ，应用定理3 ( 1 ) 式 v ：= m i l l e l e m e m ( v - s e t ) a l ：= s u b s e t ( v 贼，v ) 1 3 第二章排序与线性扩展计数 vs e t ：= vs e t & 。a l b ：= n u m o n ( a 1 ) t ：= t c ： c ：= c b i f ( b 3 ) c o n t i 娜e i f ( b 6 ) t ：一t + t l l e t a 1 ) ) ：c o m i 肌e ；) t 1 ：= b u f n s e a r c h ( a 1 ) ，在缓存中查找 i f ( t 1 ) t ：= t + t 1 ；g m o l a b e l l d ：= s e l e c t v ( a 1 )，应用定理3 ( 2 ) t l ：= o w h i l e ( g e t n e x t s u b s e t ( a 1 ，d ，a 2 ，b 2 ) ) t 2 ：= 砸i a 2 ) 递归的过程 t 3 ：= e ( r l b 2 ) t 1 ：= t 1 + t 2 + t 3 ) b i l f n h l s e i t ( a 1 ，t 1 ) ，存入缓存 l a b e l l ： t ：= t t 1 ： ) r e t i l m t 1 4 第三章图同构算法 第三章图同构算法 图同构算法是计算s ( n ) 的另一个重要算法，p e c z a r s k i 在计算s ( 1 3 ) 的过程 中，该算法占用了大约2 0 的c p u 时间。根据定理2 ，等价的偏序的线性扩展 数相等，表现在表示偏序的有向图上。表示同构偏序的有向图相同，表示对偶 偏序的有向图的边方向相反。为了避免重复计算，我们每次由r 进行一次比较 生成r 1 和r 2 时，都要与已有的偏序进行比较，如果已经有与它们等价的偏序， 我们就不必再处理r l 和r 2 了 u l l m 肌算法是一个比较好的图同构算法【4 1 ，它的时间代价大约是o ( n 3 ) 。该 算法的中心思想是从一个节点出发，把图展开，找到节点之间的一一对应关系， 如果能找到这样的关系，则两个图同构。u 1 1 m a n 本人给出的算法是要在一个无 向图中找到与另一个无向图同构的子图，由于我们比较的是两个有向图，且节 点数相等，所以需要对u 1 1 m a n 算法稍做修改。 算法首先生成表示图9 1 和9 2 节点对应关系的矩阵m ，若节点i ，j 的前驱和 后继数都对应相等，则瓤i j = l ，否则m i 儿j = o 。然后从9 1 的节点 p e r m - l e n = 0 开始，取9 2 中一个与p e r m - 1 e n 的前驱和后继数都相等的节点j ， 保留他们的对应关系，删除p e r 虬l e n 与其它节点的对应关系，并修改矩阵m 为 m l ，修改m 的过程在文献【4 】中称为r e f i n e o ，它的主要任务是在删除了p e r 毗1 e n 与其他节点的对应关系后，修改p e r m _ 1 e n 的各邻居与另一图中节点的对应关 系，并修改矩阵m 1 。若修改后m l 的某行全为o ，说明9 1 有一个节点在9 2 中找 不到对应的节点，则取m 中p e r m - l e n 的另一个对应的节点继续测试。如果测试 了m 中p e r m - 1 e n 对应的所有节点，都会使m 的某一行全为o ，则返回测试 p e r m - 1 e n 一1 的另一个对应的节点若p e r m - l e n = n 一1 ，则在9 1 和9 2 的节点之 间建立了一一对应关系，两个图同构。 修改后的算法描述如下： 算法3 ( 9 1 u l l 腿n ( 9 2 ) ) ： i f ( 9 1 ni - 9 2 。n ) r e t u r nf a l s e m ：= o每b i t 表示一个元素，构成n 牛n 的0 矩阵 f o r ( i ：= 0 ：i n ：i + + ) ( 生成初始矩阵 f o r ( j ：= o ：j n ：j + + ) 1 5 第三章图同构算法 i f ( 帆m o f l ( 9 1 p r e v i ) = n o f l ( 9 2 p r e v j ) ( n u m o f l ( 9 1 n e x t i ) = n o f l ( 9 2 n e x t j ) ) m i ：= 1 j 】 l ， p e 瑚l l e n ：= 0 ： i f ( m a t c h ( g l ，9 2 ，m ，p e r m j e n ) ) r e t u r i lt r u e r e t u r nf a l s e b 0 0 lm a t c h ( g l ，9 2 ，m ，p e r m _ 1 e n ) f o u n d ：= f a l s e n o d e s ：= m p e r m _ l e n 与节点p e r m _ 1 e n 度相同的节点集 w h i l e ( ! f o u n d n o d e s ) 、 n o d e 2 ：= m i n e l e n t ( n o d e s ) 试图将n o d e 2 与p e r m - 1 e n 对应 n o d e s ：= n o d e s ( 1 n o d e ) m 1 ：= m f o r ( i ：= p e r m _ 1 e n + l ；+ i n ：i + + ) ( m 1 i ：= l i ( 1 n o d e 2 ) v _ s e t ：= m i 】 “ 呐i l e ( v s e t ) v ：= 舭n e l e m e n t ( v - s e t ) k ：= p e r n l l e n ： i f ( ( 9 1 p r e v i ( 1 ( k ) x 0 r 1 ( 9 1 n e x t i ( 1 k ) x o r ( 9 1 p r e v k ( 1 i ) x 0 r ( 9 1 n e 置t k ( 1 i ) x o r m l i ：= m 1 i ( 1 j ) v - s e t ：5l s e t 。( 1 v ) r e f i n e ( ) 9 2 p r e v 【i ( 1 n o d e 2 ) 9 2 n e x t i ( 1 n o d e 2 ) 9 2 p r e v n o d e 2 ( 1 v ) 9 2 n e x t n o d e 2 ( 1 e ) ， 则r 1 经过c n - c 1 次比较完成排序的概率要比f 2 小，因此他的算法中优先测试 线性扩展数较大的一个偏序。 我们称m ，w j l l s 用来生成r c 的算法为w e l l s 算法。算法中若r c 包含一个 与偏序r 等价的偏序，函数s e a r c h 皿c r ) 返回t m e ，否则返回f a l s e 。， 算法5 m k l l s 算法) ： r o ：= r 0 ) ，w h 盯er d = ( 1 | 0 ，i | 0 ) ，( u i ，u 1 ) ，( u m l ，u n 1 ) r l ：= i b ：= ：= r 珈：= 中 i f w e l l s ( o ，c n ) = f a l s et h e ns n - f n e l s n ：= 1，不能得出结论 b 0 0 lw e l l “c l ，c 2 ) ，输入r c l ，c 1 ，c 2 ，计算1 + l ，i + 2 r c 2 矗) r c - c 1 + l t o c 2s t e p ld o f o r c hr k l d o f o r e a c h ( j ，k ) w h e r e j q 【舭d ( u j ，u k ) 硭r 弧d ( u i 【u j ) 仨r d o r 1 ：= r + 沁，u k ) r 2 ：= r + 叻 ， 1 8 第四章w h l s 算法及改进 i f s e a r c h ，r 1 ) = f a l s e 锄ds e 盯c h a r c ，r 2 产f a l s et h e n i f e ( r 1 ) = 2 a n de ) = r 2 ) t h r c ：= l 沁u r 1 ) e l i k ：= r c u r 2 ) i f r o = mt h e n r e t i l m f a l s e 一 栅m n u e ：一 算法从只包含一个完全无序的偏序r 0 的集合硒开始，在第c 步中，对r 。1 中每一个偏序f 的中的每一个没有关系的元素对“，u 游行一次比较，得到新的 偏序r 1 和r 2 ，若r 1 ( 或r 2 ) 的线性扩展数大于2 嘶，则r 1 ( 或r 2 ) 不能经过c n c 次比较完成排序( 【4 】定理1 ) ，那么，对r 来说，在第c 步比较屿和u k 是不合适 的。若r l 和f 2 的线性扩展数都不大于2 c ”，则它们有可能经过c n - c 次比较完 成排序，那么f 有可能经过c n _ c + 1 次比较完成排序，把r 1 和r 2 中线性扩展数 较大的一个加入r c ，继续测试。如果r l 或r 2 在r c 中有一个等价的偏序，则 它们没有必要加入r “【4 】定理2 ) ，这样可以有效的减少r c 中偏序的数量。 若r c = o ，则说明r c 1 中的偏序都不能经过c n c + 1 次比较完成排序，同 理，r c 2 ，r c 3 ，r ，眦中的偏序都不能经过c n - i 次比较完成排序。由此 可以断定s ( n ) c n 。用该算法计算s ( 1 2 ) 时，r 2 4 _ 中。由于f ( n 产3 0 ，由此得出 s ( 1 2 ) = 3 0 由于每次比较以后，我们只向r c 中加入了一个新的偏序r l 或f 2 ，另一个 能否在c n c - 1 次比较后完成排序还不知道，若r 凸巾，我们不能断定s ( n ) = c n ，需要其他的计算才能得出结论用w e l l s 算法计算s ( 1 3 ) 、s ( 1 4 ) 时遇到了这 种情况。 第二节更高效的w e l i s 算法实现 w e l l s 算法中要对偏序中所有没有大小关系的元素对进行比较。虽然我们也 使用w e l l s 算法，但使用一些技巧后，算法的效率得到极大提高。 1 9 第四章w b l l s 算法及改进 4 2 1 调整比较的顺序 设r r c 是u 上的偏序， u j u ， ，u k ) 叠“u j ) 岳r ，我们比较了屿 和u k ，得到r l 呵+ q u k ，e ( r 1 ) 2 c ”1 ，对于任意的l j p 一【u j 】和l l q r 【u k 】，设印州u q ， 则e ( r 0 2 h 州。这是显而易见的，根据偏序的传递性，r l 的线性扩展必然是 的线性扩展- 出h 7幽 u l u 3u 6 u 1 0 u 1 2 图4 1 计算s ( 1 3 ) 时r 1 3 上的一个偏序 j kc l1 j kc1 j kc1 j kc oo3 21 41842 83 774 26 93 lo4 o1 5l902 93 974 37 84 2o62 1 6 ll o l3 0 4 624 4 79o 3o 751 7l1 123 l4l o44 57l ol 4 o 951 8l1 223 241 174 671 12 5ol o41 92 3 53 341 274 771 22 6o1 l72 02 4 33 45 654 88 9 4 7o1 272 l2 6l3 557 24 98l o5 81222 22 723 65 925 081 12 9 l3 72 32 923 751 035 l81 22 l o l4 52 42l o13 8 5uo 5 29l ol l ll5 22 52l l43 951 2o5 391 12 1 2l6 32 621 244 067 35 491 22 1 3l7 o2 73 424 l6 875 5l l 1 2o 表4 1 图4 1 偏序对应的无关元素对 第四章w j l l s 算法及改进 m p e c z a s k i 提出了这一点，但没有善加利用，他只是在遇到这样的( u 。u k ) 时， 将( u p ，l l q ) 标记为不必比较。我们可以特意取寻找这样的( u j ，u k ) ，先比较它们，以 便把更多的元素对标记为不必比较。 我们定义偏序r 中元素u 的势为ir 【u 】i - l 一【u 】l ，则依概率，势相等或接近 的元素进行比较，得到的两个新偏序的线性扩展数相差较小，都接近于e ( r ) 2 ， 因此我们优先比较这些元素对。这样，我们一旦发现一个e ( r 。) 2 l ，则可能 把更多的元素对标记为不必比较。 图4 ，l 是计算s ( 1 3 ) 时，r 1 4 中的一个偏序r ，母= 4 8 5 7 1 2 。下次如果先比较 u 5 和u l o ，得到r 1 钟+ u ，u l o ，r 2 = r h l o u 5 ，r 2 ) = 3 3 5 5 9 2 2 靠1 5 = 2 埔，因此不保 存r 1 和r 2 ，利用上面的方法，可以把元素对( u 3 ，u 8 ) 、( i | 6 ，u 8 ) 、( u 5 舶) 比较为不必 比较。为此，我们构造一个数组，保存j 、k 和u j l j l c 的势差如表4 1 。若我们不 加处理，直接按照数组中的顺序进行比较，则总共要计算个3 5 偏序的线性扩展 数，若我们扫描数组8 次，分别比较咖7 的元素对，则总共需要计算