华中科技大学学报(自然科学版) 2017年 第45卷 总目次

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

大规模稀疏图的极大团枚举算法

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

基于多核环境的并行性双向枚举连接

基于多核处理器, 结合自底向上和自顶向下两种算法, 提出一种图遍历驱动的双向优化算法, 该算法充分利用两种遍历算法的优点, 并发挥多核环境的优势, 实现了最优查询计划的高性能并行构建, 解决了并行双向枚举连接问题. 实验结果表明, 该算法的性能优于已有算法, 可明显提高数据库查询速度.     

基于多核环境的并行性双向枚举连接

基于多核处理器,结合自底向上和自顶向下两种算法,提出一种图遍历驱动的双向优化算法,该算法充分利用两种遍历算法的优点,并发挥多核环境的优势,实现了最优查询计划的高性能并行构建,解决了并行双向枚举连接问题.实验结果表明,该算法的性能优于已有算法,可明显提高数据库查询速度.     

计算网络SKT可靠性的一个算法

提出一个计算从网络源点到某些特定结点（ＳＫＴ）可靠性算法,这个算法本质上是通过系统地枚举网络的一类特殊子网络而计算其ＳＫＴ可靠性或生成可靠性表达式,由于所需枚举的子网络数量小于相应的Ｓａｔｙａｎａｒａｙａｎａ算法需枚举的子网络数量,因此新算法性能优于Ｓａｔｙａｎａｒａｙａｎａ算法,最后通过一个具体例子说明了这个结论。     

半结构化文档数据流的快速频繁模式挖掘

为了提高半结构化文档数据流的挖掘效率,对原有挖掘算法StreamT进行了改进,提出了一种半结构化文档数据流的快速频繁模式挖掘算法--FStreamT.该算法针对利用集合存储候选频繁模式效率较低的缺点,采用枚举树存储候选频繁模式,可以有效地提高对候选频繁模式集合进行查找和更新的效率,同时利用频繁模式的单调性和枚举树的特点减小了维护负边界的搜索空间,从而提高了整个算法的效率.理论分析和实验结果表明,算法FStreamT与算法StreamT相比具有较高的效率,是有效可行的.     

枚举组合算法的研究与应用

关联规则挖掘领域中的Apriori算法，其基本思想是组合枚举，然而要枚举出所有组合是一个困难的问题。本文从程序设计的角度对组合枚举算法进行了研究，给出了定义、定理和证明，设计了组合算法并在C#．NET中进行了实验，探讨了组合枚举算法的应用与不足。     

基于自动区域故障模式与后果分析法的配电网可靠性评估

提出了一种基于配电块的简化网络可靠性FMEA算法.根据不同开关的功能,以自动开关装置为边界形成自动区域,将配电网络简化为只含开关、配电块及负荷的等效网络,每个自动区域仅含一个自动开关和若干个手动开关,由自动区域特性可知与该区域直接相连的所有支路的负荷点有相同的故障率,对于和自动区域直接相连的负荷而言,区域内元件故障对负荷点造成的故障停运时间相同.基于配电块的故障模式后果分析法,提出了形式化的简化配电网络可靠性评估算法.该算法只需一次枚举大大减少了重复枚举的数量,通过RBTS算例分析,证明了该方法的有效性.     

Cm命题演算的定理机器证明系统

C_m系统是制约逻辑的命题演算系统,但是其推导定理的过程可否由图灵(计算机)算法完成尚未得到明确的结论.研究证明了C_m的公式集是递归可枚举集,并且给出了一个递归枚举算法,该算法能够对任一给定的实际可证的C_m式在有限的步骤内判定它属于C_m可证公式集.并给出了C_m命题演算系统的一个定理机器证明系统.因此证明了C_m系统至少是半可判定的.     

结合优先指派规则的车间作业问题的枚举算法

车间作业调度问题是一个典型的NP完全问题,这种问题的精确求解算法的计算时间会随着问题实例规模的增大而呈指数增加.针对车间作业调度问题的难解性,给出了一个求解该问题的快速枚举算法.该算法是按照枚举算法的一般步骤来进行设计的,在设计过程中对于算法所涉及到的初始解问题、分枝问题以及剪枝策略等问题给出了旨在减少算法计算时间的解决方案.该算法找到了所测试的9个标准算例中4个算例的精确最优解.     

基于GASA算法的成品燃油战时公路配送路径优化

为了实现配送的路径优化,结合战时极其重要的物资--成品燃油,提出了多属性道路网络下成品燃油战时配送的路径优化问题.综合考虑战时配送VRP(vehicle routing problem)的多个评价目标,基于重要性的多目标分层优化思想,分析建立了问题的完全分层优化模型.将进化算法和传统优化技术相结合,构造了模型的两层求解算法,第一层采用遗传算法和模拟退火算法混合的GASA(genetic simulated annealing algorithms)算法,第二层采用枚举法.实验表明,所构造的算法较标准遗传算法更有效.     

Mining Frequent Closed Itemsets in Large High Dimensional Data

Large high-dimensional data have posed great challenges to existing algorithms for frequent itemsets mining. To solve the problem, a hybrid method, consisting of a novel row enumeration algorithm and a column enumeration algorithm, is proposed. The intention of the hybrid method is to decompose the mining task into two subtasks and then choose appropriate algorithms to solve them respectively. The novel algorithm, i.e., Intertransaction is based on the characteristic that there are few common items between or among long transactions. In addition, an optimization technique is adopted to improve the performance of the intersection of bit-vectors. Experiments on synthetic data show that our method achieves high performance in large high-dimensional data.     

一类基于优先级的隐枚举两层决策方法

针对一类含０－１变量的两层决策问题，探讨了用隐枚举方法求解过程中的变量搜索次序问题。在定义了变量搜索优先级之后，提出了一种基于变量搜索优先级的方法，理论分析与计算示例表明，所提出的方法能够最快地求到问题的全局最优解。     

单原子状态自洽法的算法

针对传统的算法存在解的精度不高和计算时间长等问题,通过对单原子状态自洽法的算法进行分析,利用数值运算功能极强的MATLAB(MATrix LABoratory)为工具,以金属Cu为例,对确定晶体电子结构的计算方法单原子状态自洽法编程求解。研究结果表明:此法编程时间短,利用该编程求解,解的精度更高,计算效率提高了近100倍,便于引入其他性质,增强标定电子结构的准确性。     

基于抽样方法的不确定极限学习机

实际应用中的大量数据具有不确定属性,而传统的挖掘算法无法直接应用在不确定数据集上.针对不确定数据的分类问题,提出一种基于抽样方法的不确定极限学习机.该算法通过抽样的方法,对不确定数据集中样本的抽样实例进行学习和分类,得到该不确定样本的所属类别的概率,从而实现了传统极限学习机分类算法对不确定数据的分类,并极大降低了不确定对象实例的枚举代价.实验结果表明,该算法在不确定数据的分类问题中具有较好的有效性和高效性.     

A method of combining SE-tree to compute all minimal hitting sets

In model-based diagnosis, the candidate diagnostic results are generally characterized by all minimal hitting sets for the collection of all conflict sets. In this paper, a new method is proposed to judge a hitting set by the number of conflict sets corresponding to components, and the computing procedure is formalized by combining revised SE-tree (set enumeration tree) with closed nodes to generate all minimal hitting sets. Results show that because closed nodes are added into SE-tree, the search efficiency is highly improved. Furthermore, the proposed method is easy to be understood and implemented. Compared with other effective algorithms with completeness in some experimental tests, the diagnosis efficiency of our proposed method is higher, particularly for single- and double-fault diagnosis.     

整数线性规划的一种混合算法

本文是将分支定界法与改进的割平面法、隐枚举法相结合,提出一种解决整数线性规划的混合型方法。用这种方法解决整数规划问题,能节省较多的计算量。     

一种人机交互语音切分系统

对于大规模的语音语料,语音切分方法主要有传统的人工切分和机器自动化切分2种方式.人工切分大规模语音语料的切分质量易控制,但效率低、成本高;机器自动化切分效率高,但后期查找切分错误时任务极其繁重.因而提出一种人机交互语音切分系统,切分人员可选择自动切分算法,设置切分参数,修改有问题的自动切分结果,同时可自动生成用于HTK训练的标注文件.以课题组采集的1 000个普米语语音文件为研究对象,以普米语孤立词为切分基元,机器自动化切分存在难以避免的切分错误,后期检查时工作量巨大;然而使用本文提出的人机交互语言切分系统进行切分,切分人员在无需高认知度的情况下也可做到近100%的切分正确率.     

不同数据结构下回溯法效率的比较

一般而言,因溯法比枚举法的效率高出几个数量级,因此,其效率问题对于输入规模较大的问题而言至关重要.以一个典型的回溯问题为例,通过对比,说明回溯法在不同数据结构下,其时间效率的差异,验证对于可表示成稀疏矩阵的数据集,在使用四向链表结构时,可以大大提高时间效率.这对于那些适合回溯法解决的问题是非常有意义的.