PDF《(19)的解决 *》

并且, 等价的( 指同构或对偶的) 偏序完成 排序所需要的比较次数也相同[4] . 定义

2 可接受的划分 设( U, r) 是一个偏序, D∈U, d∈D.若满足下列条件, 则称( A, B) 是D上关 于d的可接受的划分: ( 1) A∪B=D- {d} 且A∩B=!;

( 2) 若( a, d) ∈r 且a≠d, 则a∈A;

( 3) 若( d, b) ∈r 且b≠d, 则b∈B;

( 4) 对任意的 a∈A 和b∈B, 有(b, a) &

r. Peczarski 的论文中给出了如下定理. 定理

1 设r是U上的一个偏序: ( 1) 若A, B'

U, A∩B=!, 且对任意的 a∈A 和b∈B, 有( a, b) &

r, 则e( r|A∪B) =e( r|A) ・ e( r|B) ・ C |A| |A|+|B| ( 2) ( 2) 若D'

U 且d∈D, 则e( r|D) = A, B )e( r|A) ・ e( r|B) ( 3) 其中式( 3) 是对 D 上关于 d 的所有可接受的划分 求和. 定理

1 是Peczarski 给出的,他用实验证明了该 算法是计算线性扩展数最快的方法[4, 5] .此外, 对于 |U|≤5 的偏序, Peczarski 还给出了一种时间代价 为O( n) 阶的快速算法. 为叙述方便, 文中使用有向图来表示偏序.公式 ( 2) 把图划分为连通子图, 通过计算各子图的线性扩 展数来计算偏序的线性扩展数.公式( 3) 针对连通图 情况, 选择一个节点 d, 把偏序划分为多个关于 d 的 可接受划分.通过计算这些小规模偏序的线性扩展 数来计算偏序的线性扩展数. 对于计算线性扩展计数的方法,文中的改进工 作主要体现在缓存机制的引入.分析公式( 3) , 可以 发现 A、 B 都可能不是连通子图,而它们的连通子图 在计算的过程中, 需要重复计算式( 3) .若这些连通 子图的节点数不大于 5,使用 Peczarski 给出的快速 算法计算;

若节点数大于 5, 就调用式( 3) 计算.为了 提高计算效率, 作者引入缓存机制, 保存已经计算出 的节点数不小于

5 的子图的线性扩展数.当再遇到 这些子图时, 就可以避免重复计算. 以图

1 所示偏序为例, 其中|U|=14.这里省略有 向图边上的箭头, 用左右关系表示大小关系, 使用公 式( 3) 计算线性扩展数.取d=u5, 则A、 B 的所有取值 中, 节点数大于

5 的子图共

4 个, 记为 D1={u0, u1, u2, u3, u4, u10, u11}, D2 ={u0, u1, u2, u4, u10, u11}, D3 ={u0, u2, u3, u4, u10, u11}, D4={u0, u2, u4, u10, u11}, 且都被计算

2 次.n 成维一 等: 最少比较排序问题中 S (15) 和S(19) 的解决

307 Journal of Computer Science and Frontiers 计算机科学与探索 2007, 1( 3) 越大,这种子图的线性扩展数被重复计算的次数越 多.如果在第一次计算后保存了结果, 则以后可以查 询得到 e( r|Di) . 在计算 e( r|Di) 的过程中, r 始终不变, 只需要保 存Di 和它对应的 e( r|Di) . 在实际实现中, 引入位图机 制来标示元素 uk 是否在 Di 中.当n较小时, 可以使 用线性表表示缓存结构;

n 较大时,为了减小查找长 度, 可以把缓存组织成二叉排序树或平衡二叉树.实 验证明,这样的改进极大地提高了计算线性扩展计 数的效率. 3.2 Wells 算法 Wells 算法核心部分的描述如下: R0: ={r0}, where r0={( u0, u0) , ( u1, u1) , …, ( un-1, un-1) } R1 : = R2 : = … : = RCn : = Φ if Wells( 0, Cn) =false then Sn : = Fn else Sn : = -

1 //不能得出结论 BOOL Wells( c1, c2)//输入 RC1 , c1, c2, 计算 Rc1 +1 , Rc1 +2 …Rc2 for c : = c1+1 to c2 step

1 do for each r∈Rc-1 do for each ( j, k)where j2 Cn - c-

1 , 则有 e( r2) >

2 Cn - c-

1 . 证明 根据偏序的传递性, r1 的线性扩展必然是 r2 的线性扩展.定理得证. 因此, 如果先比较 uj 和uk, 那么 ui 和uq 就没有 必要再进行比较, 为此引入一个节点的势的定义. 定义