一种有效的丰满树算法

本文提出了一种新的有效的丰满树数据结构及其插入、删除、查询、中序周游等的基本算法。这种数据结构不用指针场,而用顺序地址标法来保持树中结点的联系,从而使空间复杂度大为减少,而且其算法也得以简化。在插入、删除的结点个数相对于文件规模不算太大的情况下,该算法的时间复杂度也是比较好的。     

子问题平衡对合并排序时间复杂性的影响

利用分治法(divide and conquer)来设计算法时,人们出于平衡的考虑,总是把问题分成相等的子问题递归地分治下去。在很多具体问题上可证明子问题平衡对时问复杂性的常系数可以有改进。本文从合并排序方面讨论证明子问题平衡可使时间复杂性最小。     

排课程序时间片选择的安全决策调度算法

排课表程序中选择合适时间的问题,其本质上是寻找教室、教师和学生班级的公共有空集合,1975年Itai及Shamir证明了课程表问题也是一个NP-完全类问題。从而结束了该问题上很多学者之间的论争。可把排课表问题分成两个层次进行,首先选择合适时间,然后再根据这个时间进行教室调度。而教室调度在各类学校是大不相同的,本文着重讨论了根据安全决策准则来选择合适时间片。其出发点是在为每一门课程选择时间时,要考虑对后续课影响最小,如一位教师一学期讲两门课(相应有两个班级),选第一门课时间时,尽可能选第二门课这个班级在上别的课的时间,这样在选第二门课的时间时,其选择自由度不受第一门课的影响。如一个班级同时接受两位教师讲两门课,其考虑的出发点也同样。这样来选择时间,以后造成冲突的可能性大大减少。本文给出了安全决策调度算法的定量描述,为加快安全决策调度过程,在原始输入课元组时,把相同的教师及相同的班级的课元组放在一起,只要往下扫描几门课。根据这几门课便可进行决策,再以后的课全是无关联的。本文也给出了算法框图。经在IBM-PC机上运行,证明选择合适时间片是完全可行的。     

解空间搜索中的B*树算法

本文给出了在人工智能求解中的一种算法——B*树算法。文章比较了B*树算法与A*树算法、BB算法的不同处和特点,较详细地叙述了在两种决策策略下B*树返回修正值的产生过程,并用算法语言对B*树算法作了具体描述。