Limiting theorems for the nodes in binary search trees

We consider three random variables X_n, Y_n and Z_n, which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X_n, Y_n and Z_n are all asymptotically normal as n→∞by applying the contraction method.

一种故障树预处理和最小割集的嵌套求解方法

故障树分析(Fault Tree Analyze,FTA)是一种系统安全性分析方法。求解故障树最小割集(Minimum Cut Set,MCS)是FTA的重要环节,其方法主要包括基于布尔代数的算法和基于二元决策图(Binary Decision Diagram,BDD)的算法,在使用普通计算机分析大规模故障树时,现有方法存在工作内存不足和计算时间过久的问题。为了解决上述问题,针对国内某百万千瓦级大型压水堆风险模型,提出了一种基于布尔代数的故障树预处理和最小割集嵌套求解算法(Pretreat and Nested Minimum Cut-Set Algorithm,PNMCS)。该算法由三个模块组成:故障树化简、故障树剪枝、最小割集嵌套计算。在国内某大型压水堆风险模型和几种实际应用风险模型上的应用表明,本算法在求得正确结果的同时,有效解决了工作内存不足和计算时间过久的问题。

基于LBP和CCS-AdaBoost的多视角人脸检测

为了解决多视角人脸检测中多视角导致的人脸结构不同的问题和人脸与非人脸之间的误分类风险不同的问题,检测特征使用局部二值模式(LBP)及统计直方图,人脸非人脸分类器使用可控风险敏感AdaBoost(CCS-Ada-Boost).LBP及统计直方图能够描述多视角的人脸结构;CCS-AdaBoost能够在降低总体的误分类风险的同时最小化分类错误率.实验中,LBP特征的性能在正面人脸检测上比Haar-like特征更好.CCS-AdaBoost分类器在一定条件下也比普通AdaBoost分类器有更好的性能,并且弥补了风险敏感AdaBoost分类器(CS-AdaBoost)对靠近分类边界的样本分类不好的缺陷.最终的多视角人脸检测器在CMU-Profile测试集上获得了满意的结果.该算法实现了鲁棒的多视角人脸检测方法,在相同虚警率下获得比其他人脸检测方法更好的结果,能够有效地解决多视角人脸检测中的2个问题.

基于BDD的多阶段任务系统可靠性

针对多阶任务系统中考虑共因失效后,系统的阶段依赖性和共因失效而增加了系统可靠性分析的复杂度,采用分析显式和隐式方法存在不足的问题,提出了一种基于二元决策图考虑共因失效的故障树可靠性分析方法.该方法首先忽略共因失效情况下的故障树并将其转化为多阶段任务系绕的二元决策图(PMS-BDD),求出系统的不可靠度表达式;然后,通过隐式方法将该表达式转化成包含共因失效信息的不可靠度或可靠度表达式,并依据求得的表达式进行相应的可靠性分析.研究结果表明:该算法与显示式算法的结果相同.该研究结论为多阶任务系统可靠性分析提供一种更加简便方法.

给定恢复目标的扩展黑启动方案路径优选

扩展黑启动可以通过同时启动多台机组为网架重构阶段的系统恢复提供更多的功率支持,加快系统恢复进程,但由于扩展黑启动方案在网络拓扑中表现出来的复杂性,其恢复路径的搜索确定难于常规黑启动方案。文中在充分考虑工程实际的基础上,提出一种给定恢复目标的扩展黑启动恢复路径搜索方法。同时,提出一种改进的基于主客观集成的属性权重求解方法,将其应用于扩展黑启动恢复路径方案评价体系中指标权重的确定。通过基于局部最小树思路的初步筛选和基于灰关联投影法的二次优选,最终确定扩展黑启动方案最优恢复路径。新英格兰10机39节点系统和河北南网系统算例验证了所述方法的有效性。

基于改进的动态故障树的惯导系统安全性分析

惯导系统的安全性是影响整个飞行器安全的重要因素。在利用动态故障树对惯导系统进行安全性分析时,针对马尔科夫链的组合爆炸和无法分析事件服从非指数分布系统的问题,引入了Monte-Carlo方法。提出了一种基于改进的最小割集的动态故障树分析方法,该方法通过改进最小割集的生成方法,确定相应的分析流程,综合了二元决策图、马尔科夫链和Monte-Carlo方法的优点。最后将该方法应用到惯性平台的倒台事故分析中,结果表明该方法避免了马尔科夫链的缺点,并可以进行定性和定量分析。

战术导弹故障树自动建立方法研究

根据战术导弹故障模式和故障机理间的逻辑关系,采用判定表表示故障知识,采用宽度优先搜索算法形成故障树文件,采用下行法完成故障树图形的无交互绘制,首次实现了战术导弹故障树的自动建立,为准确、快速、高效的进行故障诊断提供有力的分析工具。

基于不平衡数据的公司破产预测研究

整合创新数据预处理技术与集成算法利用不平衡数据探讨了公司破产预测问题。首先,运用冗余信息处理方法、不同抽样方法等对不平衡数据进行预处理。其次,以5.0分类器(Classifier 5.0,C5.0)决策树和单隐层前馈神经网络作为基分类器,分别与三类重抽样数据预处理技术结合,择出最优抽样法。再次,结合自助汇聚法提升分类效果,并运用十折交叉验证的受试者操作特征曲线的下方面积进行评价,对比了两基分类器的集成模型。最后,运用加利福尼亚大学尔湾分校数据库中一万多家波兰制造业公司的实际数据进行实验验证。实验结果表明:欠抽样或人工少数类过采样法与神经网络结合的集成模型分类效果最优,为企业实施破产预测提供积极支撑。

一种改进的新二分查找算法的研究与实现

基于传统的二分查找算法,给出了有序表中任意两元素之间距离的最优表示方法,改进了low和high的取值,得到一种基于距离的新二分查找算法。该算法与传统的二分查找算法相比,判定树高度得到有效降低;随着有序表元素的增加,平均查找长度ASL显著减少,查找速度明显提升。

基于有序二元决策图的动态故障树定性分析方法

关于基于有序二元决策图的定性分析方法,首先引入时序逻辑,将动态门转换成时序逻辑表达式,然后将动态故障树转换成相应的有序二元决策图结构。动态故障树转换方法面临底部事件排序、冗余结构等问题,影响了定性分析的效果,为此,提出了基于成分组合法的逆向转换法,该方法具有直接、高效等特点。实例验证表明该方法能够减少转化后有序二元决策图的节点数量和冗余结构,提高动态故障树定性分析的效率和效果。

基于优化决策树算法的变电站故障诊断系统研究

为有效提升变电站运行期间故障自动化诊断效率和准确率,采用阈值近邻迭代法对样本数量进行优化,同时引入平衡系数对测试属性选择进行优化,然后再采用优化二分离散算法对连续属性离散性进行优化,构建基于优化决策树算法的变电站故障诊断系统。通过优化决策树、ID3以及C4.5三种算法的应用效果对比分析,得出基于优化决策树算法分类准确性更高、决策树构建速度更快、决策树规模更小这一结论,能够显著提升监控系统在变电站运行期间的应用效果,对于变电站长期运行稳定与安全具有重要意义。

求解声波散射问题的边界元快速多极算法的一种新型树结构

目的为创建一种新的树结构,进一步提高求解效率。方法针对有界星型散射区域,应用极坐标的思想,提出一种新型的弧形单元树结构,该树结构将二维散射问题的快速多极算法的树结构由传统的四叉树结构转化为二叉树结构,进而大大提高了求解效率。结果通过对数值例子的计算及求解效率的分析,可以看出在应用快速多极算法求解声波散射问题时,应用该二叉树结构相比原始四叉树结构时的求解效率高很多,而且精确度也较高。结论提出的新型树结构是高效且精确的。

二元决策图和故障树相融合的无线传感器网络可靠性分析

为了提高无线传感器分析网络可靠性,提出一种基于二元决策图和故障树相融合的无线传感器网络可靠分析方法;首先根据无线传感器网络拓扑结构建立了故障树模型,然后将无线传感器网络故障树转化为二元决策图结构,最后采用仿真实验分析了不同节点冗余度、不同跳数条件下无线传感器网络的可靠性;仿真结果表明,文章方法的分析结果可以帮助无线传感器网络性能的优化,可以提高无线传感器网络的可靠性。

基于“二叉决策树”模型的嵌入式软件调试

在嵌入式软件开发过程中,软件不可避免地会出现各种错误,因此调试是软件生命周期中一个非常重要的环节。针对嵌入式软件开发的流程和特点,对其调试部分进行较为深入具体的研究和探索,提出基于调试器的"二叉决策树"调试模型。该模型描述了嵌入式软件调试的一般过程、调试对象和常用方法。实践表明"二叉决策树"调试模型具有较好的实用性和扩展性。

基于二分查找判定树的蔗糖结晶颗粒分类器设计

在仔细研究煮糖过程蔗糖结晶环节的基础上,对结晶颗粒图像经过处理后所提取的特征值进行分析,针对其中的颗粒面积和形状指数特征值,提出了基于二分查找判定树的结晶颗粒分类器的设计和分类算法,并根据其分类数据对煮糖结晶阶段进行控制,经实验证明该分类方法简单实用且效率高,对于煮糖过程自动控制的实现有着重要意义。

基于模块化分解的故障树分析方法

传统故障树分析算法存在诊断成本高和耗时长的问题,为此,在研究故障树结构中的特殊规律的基础上,采用深度优先最左遍历算法对故障树进行模块化分解,减小故障树分析的规模。结合if-then-else运算符,将最左底层模块子树转化为相应的二元决策图结构。运用深度优先最左遍历算法得到该二元决策图结构中的割集和最小割集,用相同故障概率的基本事件替代最左底层模块子树得到新故障树。采用自底向上、从左至右的递归综合分析思想,获得系统元件故障发生的概率,实现对故障树的分析。对故障实例的分析诊断结果表明,该方法可有效提高诊断速度,减少诊断成本。

二分查找判定树的构造方法研究及应用

通过对二分查找的算法进行分析,并结合二分查找判定树的特点,提出一种快速画出二分查找的判定树的方法。该方法较传统方法更加直观,学生更容易理解掌握,而且比传统方法速度更快、效率更高,通过实例验证了提出方法的有效性。

融合启发式搜索的改进极快决策树算法在多规格货物智能混合装载中的应用

针对多规格货物装载效率较低问题,提出一种融合启发式搜索的改进极快决策树智能装箱算法,该算法首先计算并择优选取样本信息熵,然后构建生成货物装箱决策树模型,基于启发式搜索方法对货物装载后的剩余空间进行合并再利用。通过保证决策树每个节点装入货物体积最大,对待装货物进行快速决策。最后,基于七组异构性逐渐增强的货物数据对算法进行仿真实验。结果表明:本算法在保证较高集装箱利用率的情况下实现了快速装箱。

基于BDD考虑共因失效的接触网系统可靠性分析

为分析共因失效对高速铁路接触网系统的影响,将二元决策图(Binary Decision Diagram,BDD)与共因失效理论引入到接触网系统可靠性分析中。利用逻辑相邻优先组合法(Logic Neighbor Priority Connect,LNPC)将高速铁路接触网系统的故障树模型转化为BDD模型并求取其可靠度表达式,利用隐式方法对考虑了共因失效的接触网系统可靠度进行计算,利用MATLAB绘制考虑共因失效和不考虑共因失效情况下接触网系统可靠度变化曲线。研究结果表明:提出的分析方法适用于接触网系统的可靠性分析,为接触网系统的可靠性分析提供了一定的理论依据。

基于EFDT-HS随机森林算法的货物装载研究

为保证多规格货物在集装箱中的高效装载,提出了一种启发式随机森林算法,该算法首先利用Bagging方法生成T个训练集,对每个训练集,要求在特征集中随机选取K个特征组成新的特征集,将新特征集中的最优特征作为分割特征,利用分割特征计算并择优选取样本信息熵,然后构建生成货物装箱决策树模型,最后基于启发式搜索方法对货物装载后的剩余空间进行合并再利用.通过BR1~BR10共十组异构性逐渐增强的货物数据对算法进行仿真实验,将实验结果与其他研究算法进行比较,该算法在BR10算例中利用率达到90%,仅比其他算法低1%,但计算时间却由138062 s降低到76 s.由此可见,该算法对于多规格强异构货物的求解具有一定的可行性和有效性.