共查询到20条相似文献,搜索用时 62 毫秒
1.
幸冬梅 《计算机工程与科学》2008,30(12):97-101
支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为Inn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。 相似文献
2.
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。 相似文献
3.
指派问题是在生产和生活中经常出现的问题。本文建立了指派问题的数学模型,对现有的解决指派问题的蚁群算法进行了分析,并设计了一种改进的解决指派问题的蚁群算法,有效地提高了蚁群算法解决指派问题的准确性和效率,并通过实验结果验证了应用蚁群算法解决指派问题的可行性和先进性。 相似文献
4.
复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。 相似文献
5.
JIANG Dong- yang 《数字社区&智能家居》2008,(5)
对中文问答系统中的问题理解技术进行了研究。问题理解是问答系统的基础,问题理解的核心内容是问题分类。本文对基于规则和统计方法的问题分类体系做了介绍,提出了基于事件框架的问题语义描述模型,给出了疑问意向的形式化定义。同时借助知网,对问题空间的大小进行评测。 相似文献
6.
反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。 相似文献
7.
本文对局内问题算法给出了几个评估标准,对装箱问题设计了绝对性能比至多为2的局内问题算法,并用局内问题算法的近似度考察了 K 车服务问题。 相似文献
8.
9.
詹茂森 《数字社区&智能家居》2010,6(22):6270-6271
排课问题是一个有约束、多目标的组合优化问题,同时也是一个NP-hard问题。因此,该文选用将遗传算法引入排课问题中,首先对排课问题进行了描述,在此基础上提出了一种基于遗传算法的排课算法,并对其进行了仿真实验,最后较快的找到了问题的最优解或次优解。 相似文献
10.
11.
此文介绍了数据中心的一般性问题和特殊性问题的实质,在一般情况中涵盖了特殊性问题,而在特殊情况下又完善了一般性问题,对于这些问题的剖析,可以清晰地揭示问题的基本情况、前期对关键情况的揭示和问题的解决,是各类数据中心建成后能够长期、安全和可靠运行的必要条件。 相似文献
12.
13.
给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。 相似文献
14.
参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题:一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。 相似文献
15.
牟联常 《计算机辅助设计与制造》2008,(2):112-113
该文总结了雷达产品中铝合金铸件在机加工中存在的典型问题:毛坯划线问题、热处理后精加工基准选择问题和基准变形问题。作者在分析了以上问题存在原因的基础上,结合相关企业的经验,给出了解决这些问题的工艺方法。 相似文献
16.
17.
陈静奎 《电子制作.电脑维护与应用》2014,(9)
电力企业的线损问题,造成了电能的严重浪费。线损问题不利于建设资源节约型社会,也不利于电力企业自身的发展。本文对农村配电网问题进行了分析,首先介绍了线损的概念及理论计算方法,然后详细分析了线损管理中存在的问题,最后对这些问题提出了相应的对策。 相似文献
18.
密码体制的量子算法分析 总被引:1,自引:0,他引:1
很多快速量子算法都可以归结为隐子群问题的讨论,本文回顾了隐子群问题量子算法的基本思想,分析了群上量子算法的优越性。分析了可以归结为隐子群问题的公钥密码体制,描述了求解椭圆曲线上离散对数问题的量子算法,讨论了隐子群问题量子算法的局限性。 相似文献
19.
选址—路径问题是物流系统中的一个组合优化问题,启发式方法一般采用两阶段法将其分解为选址分派和车辆路径问题来顺序求解,但这两个阶段间的信息无法有效传递,因而往往不能得到集成问题的优化解。设计了具有能力约束的三级物流网络选址—路径问题模型,采用遗传算法整体求解该问题,避免了顺序求解带来的问题;设计了采用整数编码的三级染色体编码结构,采用禁忌搜索算法对交叉和变异操作作了改进,提高了算法的搜索效率,能够更适合集成问题的求解;最后通过算例分析,验证了本算法求解小规模选址路径问题的有效性。 相似文献
20.
软件整个生命周期中的软件问题管理是各种软件质量保证活动的核心,文中介绍了一个基于问题生命周期的软件问题管理平台———SPMP。文章深入讨论了软件问题的生命周期,指出软件问题的状态控制与变更追踪构成了软件问题管理的基础。然后介绍了该平台的体系结构、关键技术和应用实例,最后给出结论。 相似文献