反馈集与子集反馈集问题的计算复杂性研究进展

反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.

基于最佳特征子集的自适应非视距身份识别系统

身份识别一直是安防领域的研究重点,其在非视距场景下的研究存在较大意义。针对识别的舒适度和隐私性问题,提出基于最佳特征子集的自适应非视距身份识别系统。通过有效结合多种预处理手段获取Wi-Fi信号的低维有用数据;提出鲁棒性人员检测方法截取有效片段;设计有监督特征提取方法,使用“前向搜索”获取最佳特征子集;改进传统Adaboost算法实现群体变化下的自适应识别。实验评估表明,当系统中志愿者为2~12人时,与相关系统和传统分类算法相比,均具有较好的性能。

基于子集模拟的铁路路基重力式挡土墙系统可靠度分析

文中以某典型的铁路路堤挡土墙为例,介绍了铁路路基重力式挡土墙的确定性分析模型和结果.基于子集模拟方法的不确定性分析流程,分析了随机参数与系统安全系数的相关性.通过直接蒙特卡洛模拟与理论计算方法,对比验证了子集模拟方法的结果.结果表明:子集模拟方法在大幅降低计算消耗的同时,保证了计算精度.

基于子集模拟法的施工进度计划可靠性评估

建筑工程施工进度管理是项目管理的核心,施工进度计划的可靠性对工程建设起着决定性作用。为及时准确评估建筑工程施工进度计划的可靠性,结合随机概率理论,将可靠度分析引入关键路径法中,基于子集模拟法提出了一种动态的施工进度计划可靠性评估方法。实际工程案例分析表明,该方法概念简单易懂、实时性强、计算效率高,能够实时地为项目管理者提供决策依据,有效避免工程进度逾期风险,提升了项目管理的效率和质量。

基于麻雀搜索算法的ARAIM故障子集优化算法

针对多假设解分离(MHSS)测试受卫星数目增加、潜在故障概率提高的影响,使得需要监测的子集数量增长而带来计算负担增加的问题,提出一种基于麻雀搜索算法(SSA)的高级接收机自主完好性监测(ARAIM)故障子集优化算法。结合SSA将可见卫星分配为发现者、跟随者和侦查预警者,通过剔除能量较低的个体降低计算冗余。在搜索过程中,引入自适应步长提升迭代速度,提高算法的执行效率。在双星座情况下,对完好性支持信息(ISM)参数进行3种假设,验证了所提算法的可用性,并与传统算法进行了对比分析。结果表明:通过所提算法得到的子集数量较传统算法减少了75%~90%,相同条件下,仿真用时降低了68%~88%,ARAIM可用性变化不超过2%。

规则与概率相结合的不一致数据子集修复方法

不一致数据子集修复问题是数据清洗领域的重要研究问题,现有方法大多是基于完整性约束规则的,采用最小删除元组数量原则进行子集修复.然而,这种方法没有考虑删除元组的质量,导致修复准确性较低.为此,提出规则与概率相结合的子集修复方法,建模不一致元组概率使得正确元组的平均概率大于错误元组的平均概率,求解删除元组概率和最小的子集修复方案.此外,为了减小不一致元组概率计算的时间开销,提出一种高效的错误检测方法,减小不一致元组规模.真实数据和合成数据上的实验结果验证所提方法的准确性优于现有最好方法.

关于凸模糊子集的研究

给出了强凸模糊子集和严格凸模糊子集的定义.研究了强凸模糊子集与凸模糊子集的关系,及严格凸模糊子集与凸模糊子集的关系.将Yang的一些结论推广到凸模糊子集上.

面向公共服务的中文编码字符集实用子集的构建方法研究

针对我国公共服务场景对中文编码字符集实用子集的需求,基于汉字和汉字编码字符集的历史和现状分析,提出构建实用子集的构想并探讨了可能的实现方法,分析了自底向上的构建方法和自顶向下的构建方法,并对涉及生僻字的公共服务场景的汉字使用提出了若干建议。

基于ALK模型与子集模拟的主动学习可靠性分析方法

针对主动学习Kriging(Active Learning Kriging,ALK)模型在评估小失效概率时遇到的候选样本过多、计算耗时的问题,提出了一种结合ALK模型与子集模拟(Subset Simulation,SS)的双阶段代理模型方法——ALK⁃SS2。首先在第1阶段基于构建的极限状态函数代理模型,采用较少数量的SS最后一层样本作为候选样本完成极限状态面的粗略近似,然后在第2阶段选择更大样本量的SS最后一层样本来细化第1阶段的极限状态函数代理模型,以获得更高的精度。此外,考虑到传统ALK模型的收敛准则太过于保守,在ALK⁃SS2评估的失效概率基础上,提出了一种更高效的基于失效概率误差的收敛标准,进一步提高了该方法的效率。通过4个算例的测试以及同类方法的对比,证明其具有较高的计算精度和计算效率,适用于处理小失效概率问题和耗时的隐式功能函数问题。

关于子集的几个定理

以二项式(1+x)n的展开式为基础,用求导数及令x为某些特殊值的方法,例如,令x=1,-1,i,…等等,得到很多新的组合恒等式,亦即是n元集的子集数的恒等式。

基于长短期记忆及自适应Kriging子集模拟优化的风电功率预测方法

风电功率的准确预测是目前践行各类监管和运营战略,发展智能电网和先进控制系统等重要技术的前提。提出一种基于长短期记忆及自适应Kriging子集模拟优化的风电功率预测方法。在风电场数据特征提取的基础上,以长短期记忆预测均方根误差为目标,超参数为设计变量,通过基于期望改善的深度耦合自适应Kriging子集模拟优化,进行超参数的高效优化设计,输出最优预测功率。最后,通过案例验证所提方法的预测性能。

基于子集模拟和通用生成函数的结构可靠性分析

传统的结构可靠性分析方法在处理多维非正态分布、小失效概率以及功能函数高度非线性问题时,很难以较低成本获得满意的精度。为了克服现有方法的不足,将子集模拟法(SS)与通用生成函数(UGF)相结合,提出结构可靠性分析的UGF-SS法。根据子集模拟思想,利用通用生成函数获得中间失效概率,从而获得结构失效概率。对随机变量进行低密度离散,获得结构通用生成函数,划分中间事件,计算失效概率。在之后的模拟中针对中间事件进行非均匀自适应细分,获得每层中间失效概率。最后一层模拟利用拉丁超立方抽样扩充中间事件样本,计算失效概率。模拟结束后,各中间失效概率相乘得到结构失效概率。通过算例分析验证了所提方法的合理性和可行性,所提方法在保留子集模拟法高效率的同时,发挥了通用生成函数对任意随机变量和功能函数的普适性,保证了结果的精度。

李涤生《荀子集释》平议

《荀子集释》虽然是一本出版于1979年的书,但却时常活跃在研究者的征引之列,其学术价值显然经受住了时间的淘洗,获得了荀子研究者的认可。鸟瞰后世注释《荀子》之作,此书当在《荀子》注释史上占有一席之地。从格局、体例、方法三大层面进行衡定,该书有相当大的学术价值和启迪意义。其一,在研究格局上,广采众家,由博返约。其二,在撰著体例上,题解精妙,案语多当。其三,在研究方法上,训诂为主,兼及义理。这三大层面所彰显出的特色决定了此书是一部融训诂、思辨于一身,兼普及、研究于一体的有着鲜明特色的《荀子》注释类著作。可以逆料的是,当代《荀子》注释类著述与相关研究亦当沿此三大层面进行,才能获得突破性进展。

基于子集模拟与风险参数耦合的粉煤气化管道可靠性分析

对粉煤气化管道进行可靠性分析,研究服役管道各参数对失效的影响规律,可以有效降低坍塌、断裂等事故的发生频率。针对煤气管道可能出现断裂和塑性坍塌问题,采用子集模拟技术对粉煤气化管道的可靠性进行评估,分析了管道小概率失效的关键因素,对管道内压、缺陷深度和材料韧性进行显著性分析,并探讨不同应变硬化模型对评估结果的影响,探讨了各关键参数变化对系统产生的耦合效应,综合评估煤气管道在塑性坍塌状态和断裂状态下的系统失效概率。结果表明,管道失效概率随着腐蚀深度、裂纹深度和长度以及管道内压增加而增大,管道的系统可靠性随之降低;在相同条件下,应变硬化指数对管道的可靠性分析结果有显著影响;断裂和塑性坍塌的风险程度与管道壁厚成正比关系。

基于正交子集的叠前噪音压制技术

三维地震数据中一条检波线和与之垂直的炮线的所有地震道组成了三维地震数据的一个正交子集。一个正交子集就是一个三维单次覆盖数据体。在正交子集中,各种规则干扰,如面波、声波、折射以及由地面不均匀体产生的散射,在三维空间上,形成以震源或散射点为顶点的锥形体,线性噪音为从圆锥顶点辐射出的直线,具有恒定的视速度。三维F-Kx-Ky锥形滤波器的频率响应特征呈圆锥形,与线性噪音在正交子集道集上的分布形状吻合,三维F-Kx-Ky锥形滤波可以很好压制线性噪音和次生干扰。在正交子集里,共中心点距离缩减为炮点距和检波点距的一半,将三维叠后随机噪音压制技术应用到正交子集上,可有效缓解基于传统道集的叠前噪音压制因空间采样不足而引起的假频问题。实际资料的应用表明,正交子集压制噪音,比传统的炮检域有更好的去噪效果。

状态机的稳定状态与稳定子集

主要研究了状态机的(可)稳定状态,稳定子集与可稳定状态子集关于状态机同态、覆盖及状态机的积的性质,并讨论了只有一个输入的状态机的(可)稳定状态,稳定子集与可稳定状态子集.

扇束图像重建中OSEM算法及子集划分的研究

将一种快速迭代图像重建方法OSEM用于仿真Phantom模型的扇束投影数据的重建中,验证其重建参数的有效取值范围,分析比较不同子集选取对扇束OSEM重建的图像质量以及收敛速度的影响。方法: 本研究采用事先计算特定几何扇束扫描的概率矩阵和最大间距划分投影子集的方法,选取图像大小为128*128。通过对模拟的Phantom扇束投影数据的重建,结果: OSEM重建效果好于传统滤波反投影(FBP)重建的结果,尤其是在有噪声情况下,在一定范围内重建质量与迭代次数和子集划分个数成正比,而计算时间仅仅与迭代次数正比。结论: 恰当地选取子集个数,扇束OSEM重建可用较少迭代次数和较短的计算时间获取好的重建图像。

一种地理空间网络子集快速探测方法

针对大数据下地理空间网络子集探测效率较低的问题,文章通过引入“弧段到点”和“点到弧段”两个索引表,提出了一种地理空间网络子集快速探测方法。该方法创新性地通过两个索引表直接实现了弧段和端点的查找定位,避免了传统子集探测方法中因查找搜索计算冗余度过高导致的效率低下问题,显著提升了地理空间网络子集探测的计算效率。通过MATLAB软件模拟生成了包含不同数量随机点的狄洛尼三角网,利用该方法和传统方法分别进行了子集探测。结果表明,两种方法均可实现子集的成功探测,但是该方法显著改善了子集探测效率。

基于剪枝策略的回溯算法优化——以子集和问题为例

回溯法的本质是穷举,其复杂度较高,但通过剪枝策略,可以显著增强算法的性能。本文以子集和问题为例,分别实现了无剪枝、约束条件剪枝、先验知识剪枝、约束条件剪枝加先验知识剪枝共四种算法策略,并通过实验进行性能对比,验证了各种剪枝策略在不同情境下的效果,并总结了剪枝策略对算法性能的实质性改进。研究结果表明,合理应用剪枝策略能够显著提升回溯算法在复杂组合优化问题中的解决效率和实用性,为相关领域的算法设计与应用提供了重要参考与指导。

序列子集联合代数重建技术

图像重建迭代算法的主要缺点是计算量大,重建速度慢。为减少计算时间,Hudson等提出了有序子集算法,由于该算法在每次迭代时使用固定的子集个数,重建图像的质量主要依赖于迭代步中的子集数。本文提出序列子集联合代数重建技术,在每次迭代后减少使用的子集个数,这样在加速图像收敛的同时恢复重建图像的各种频率元素。实验结果表明序列子集联合代数重建技术可在少数次迭代后提供较高质量的重建图像,且对噪声数据不敏感。