|
|||||
|
|
| 对随机排列落表剖分算法的一个改进 | |
| 引用本文： | 丁克诠,王志立.对随机排列落表剖分算法的一个改进[J].大连理工大学学报,1987(4). |
| 作者姓名： | 丁克诠 王志立 |
| 作者单位： | 大连工学院应用数学研究所 (丁克诠)，大连工学院应用数学研究所(王志立) |
| 摘 要： | 列车编组作业中要求将一个任意排列的车列依到站的先后次序重新排列,数学上将其抽象为随机排列的顺序剖分。落表算法是已有的最优算法。本文给出的算法得到与落表算法相同的结果,而对一类随机排列,其时间复杂度低于落表算法。1 落表算法的一些性质 以S(m,n)表示含有几个不同数字,且相邻数字不相同,长为m的所有排列的集合。当m=n时,落表算法的时间复杂度为O(n2)阶。 定理 给定 S(n,n) 随机等可能地取自S(n,n).随机变量X表示求P ()所需要的比较次数,则EX=O(n2),VarX=O(n3). 证明 取 为顺序排列,并且记P(X=k)=P k,当X=k时,若a=1,… |
| 关 键 词： | 分柝 随机 排列/落表算法 顺序剖分 |
| 本文献已被 CNKI 等数据库收录！ | |