一类弱支配集问题的近似算法

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为Inn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。     

蚁群算法解决指派问题的研究和应用

指派问题是在生产和生活中经常出现的问题。本文建立了指派问题的数学模型,对现有的解决指派问题的蚁群算法进行了分析,并设计了一种改进的解决指派问题的蚁群算法,有效地提高了蚁群算法解决指派问题的准确性和效率,并通过实验结果验证了应用蚁群算法解决指派问题的可行性和先进性。     

MSP问题NP完全性研究

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。     

支配问题的研究进展

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。     

中文问答系统中问题理解的研究

对中文问答系统中的问题理解技术进行了研究。问题理解是问答系统的基础,问题理解的核心内容是问题分类。本文对基于规则和统计方法的问题分类体系做了介绍,提出了基于事件框架的问题语义描述模型,给出了疑问意向的形式化定义。同时借助知网,对问题空间的大小进行评测。     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

局内问题算法的近似度

本文对局内问题算法给出了几个评估标准,对装箱问题设计了绝对性能比至多为2的局内问题算法,并用局内问题算法的近似度考察了 K 车服务问题。     

回溯算法的形式模型

讨论了回溯算法的形式模型,提出了刻画回溯的一些数学概念,以隐式搜索教育界背景提出了状态空间概念,给出了分别以邻接方阵和邻接表形式表示的有向图所对应的状态空间,从而说明显式搜索是隐式搜索的特例,通过展开空间概念揭示了问题求解的不同要求所对应的不同数据结构,提出了通用回溯算法,并以N皇后问题、稳定婚姻问题,点着色问题、子集和数问题,跳马问题,最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯 算法的应用,该文结果有助于扩大回溯算法的使用范围,提高回溯算法实现的正确性和效率。     

基于遗传算法的排课问题研究

排课问题是一个有约束、多目标的组合优化问题,同时也是一个NP-hard问题。因此,该文选用将遗传算法引入排课问题中,首先对排课问题进行了描述,在此基础上提出了一种基于遗传算法的排课算法,并对其进行了仿真实验,最后较快的找到了问题的最优解或次优解。     

排课表问题的闭环DNA计算模型的算法

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。     

最优运输管理中的分布参数控制问题

分析了汽车运输公司的最优经营管理问题,应用分布参数控制理论和方法建立了运输问题最优控制的数学模型,并用算子半群理论和方法给出了最优控制问题的解,最后给出了最优控制问题的经济学解释.     

数据中心同类问题之剖析

此文介绍了数据中心的一般性问题和特殊性问题的实质,在一般情况中涵盖了特殊性问题,而在特殊情况下又完善了一般性问题,对于这些问题的剖析,可以清晰地揭示问题的基本情况、前期对关键情况的揭示和问题的解决,是各类数据中心建成后能够长期、安全和可靠运行的必要条件。     

顶点覆盖变体问题的确定参数可解算法研究

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题：一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。     

矩形的三角形划分问题研究

给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。     

雷达铝合金铸件机加工典型问题探讨

该文总结了雷达产品中铝合金铸件在机加工中存在的典型问题：毛坯划线问题、热处理后精加工基准选择问题和基准变形问题。作者在分析了以上问题存在原因的基础上,结合相关企业的经验,给出了解决这些问题的工艺方法。     

Java中文问题

针对Java中出现的中文问题,从Servlet中文问题、资源文件的中文问题、JDBC中文问题等三个方面进行了问题的提出,并给出了解决方案。     

集成三级物流系统的网络规划问题研究*

选址—路径问题是物流系统中的一个组合优化问题,启发式方法一般采用两阶段法将其分解为选址分派和车辆路径问题来顺序求解,但这两个阶段间的信息无法有效传递,因而往往不能得到集成问题的优化解。设计了具有能力约束的三级物流网络选址—路径问题模型,采用遗传算法整体求解该问题,避免了顺序求解带来的问题;设计了采用整数编码的三级染色体编码结构,采用禁忌搜索算法对交叉和变异操作作了改进,提高了算法的搜索效率,能够更适合集成问题的求解;最后通过算例分析,验证了本算法求解小规模选址路径问题的有效性。     

农电线损管理中存在的问题及优化对策分析

电力企业的线损问题,造成了电能的严重浪费。线损问题不利于建设资源节约型社会,也不利于电力企业自身的发展。本文对农村配电网问题进行了分析,首先介绍了线损的概念及理论计算方法,然后详细分析了线损管理中存在的问题,最后对这些问题提出了相应的对策。     

密码体制的量子算法分析

很多快速量子算法都可以归结为隐子群问题的讨论,本文回顾了隐子群问题量子算法的基本思想,分析了群上量子算法的优越性。分析了可以归结为隐子群问题的公钥密码体制,描述了求解椭圆曲线上离散对数问题的量子算法,讨论了隐子群问题量子算法的局限性。     

用Excel制作试卷必须解决的几个问题

在利用Excel-VBA制作试卷时总会遇到一些无法绕开的问题,如考生信息统一性问题、试卷及标准答案的安全问题、计时问题、随机抽题问题、试卷密码问题、答案不惟一问题等。只要其中有一个问题不能合理解决,程序就不能正常使用。为此,对这些问题逐一进行了分析和探讨,并成功找出了解决途径,使利用Exce-VBA制作的试卷成功投入教学,收到了良好的教学效果。