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

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为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皇后问题、稳定婚姻问题,点着色问题、子集和数问题,跳马问题,最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯 算法的应用,该文结果有助于扩大回溯算法的使用范围,提高回溯算法实现的正确性和效率。     

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

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

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

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