量子近似优化算法在精确覆盖问题中的应用

1

作者 郭玲玲 李志强 段孟环 《计算机应用》 CSCD 北大核心 2024年第3期849-854,共6页

精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法... 精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法对量子逻辑门中的参数进行优化。首先,通过精确覆盖问题的数学模型建立经典伊辛模型;其次,利用量子理论中的旋转变量对经典伊辛模型进行量子化,再用泡利旋转算子代替旋转变量,得到量子伊辛模型和问题哈密顿量,提高QAOA寻找最优的速度;最后,以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积,得到问题哈密顿量期望的表达式,并由此设计生成量子线路。另外,通过经典处理器对两个酉变换中的参数进行优化,调整问题哈密顿量的期望值,从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验,实验结果表明,所提方案能够在多项式时间内以95.6%的概率获得问题的解,验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。 展开更多

关键词 量子近似优化算法 量子线路 哈密顿量 酉变换 精确覆盖

下载PDF 职称材料

精确覆盖问题的O(1．414^n)链数DNA计算机算法 被引量：3

2

作者 李肯立 刘杰 +1 位作者 杨磊 刘文斌 《计算机研究与发展》 EI CSCD 北大核心 2008年第10期1782-1788,共7页

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DN... DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果. 展开更多

关键词 DNA计算机 NP完全问题 精确覆盖问题 分治法 DNA超级计算

下载PDF 职称材料

基于精确覆盖的应用算法研究 被引量：1

3

作者 姜华林 《电脑知识与技术》 2018年第12Z期61-62,共2页

"百变方块"是一款深受大众喜爱的益智游戏,而求解"百变方块"是精确覆盖的一种典型应用案例。为求解"百变方块"解集,该文深入研究了"百变方块"的数据结构并设计了一种非回溯的有效算法,并用C#... "百变方块"是一款深受大众喜爱的益智游戏,而求解"百变方块"是精确覆盖的一种典型应用案例。为求解"百变方块"解集,该文深入研究了"百变方块"的数据结构并设计了一种非回溯的有效算法,并用C#语言实现了该算法。 展开更多

关键词 百变方块 精确覆盖 回溯算法 非回溯算法

下载PDF 职称材料

精确覆盖问题的加权分治算法 被引量：1

4

作者 胡沁 宁爱兵 +1 位作者 苟海雯 张惠珍 《运筹与管理》 CSSCI CSCD 北大核心 2020年第4期179-186,共8页

精确覆盖问题是组合优化中经典的NP-Hard问题之一,其在诸多领域具有广泛的应用价值。本文首先研究了精确覆盖问题的数学性质,并根据数学性质提出相应的分支降阶规则以缩小问题的规模;接着设计了一个基于分支降阶的回溯算法求解该问题;... 精确覆盖问题是组合优化中经典的NP-Hard问题之一,其在诸多领域具有广泛的应用价值。本文首先研究了精确覆盖问题的数学性质,并根据数学性质提出相应的分支降阶规则以缩小问题的规模;接着设计了一个基于分支降阶的回溯算法求解该问题;然后运用常规技术分析得出该精确算法的时间复杂度为O(1.4656k);最后运用加权分治技术对该算法的时间复杂度进行分析,将该算法的时间复杂度降为O(1.3842k)。文章最后通过一个示例进一步阐述该算法的原理,并与其他精确算法进行了对比分析,研究结果表明该算法是可行的,也是有效的。 展开更多

关键词 精确覆盖问题 分支降阶 加权分治 时间复杂度

下载PDF 职称材料

基于FTTx的下一代通信网精确覆盖系统的设计与实现 被引量：4

5

作者 林宇 《移动通信》 2014年第10期19-23,共5页

在"宽带中国"上升为国家战略的大背景下,有效支撑移动宽带和固定宽带业务的发展是当前及今后一段时期通信网络转型的一项重大举措,也是室内深度覆盖建设转型的契机。通过探讨基于FTTx的下一代通信网精确覆盖系统的设计、系统... 在"宽带中国"上升为国家战略的大背景下,有效支撑移动宽带和固定宽带业务的发展是当前及今后一段时期通信网络转型的一项重大举措,也是室内深度覆盖建设转型的契机。通过探讨基于FTTx的下一代通信网精确覆盖系统的设计、系统基本原理、硬件电路原理及系统硬件实现等方面,为各运营商在无线网室内精确覆盖方案的制定提供一定的参考。 展开更多

关键词 FTTX 室内分布 精确覆盖 深度覆盖 下一代通信网 LTE

下载PDF 职称材料

基于精确覆盖率趋势的动态优化方案研究

6

作者 姜涛 王斌 《通讯世界》 2017年第9期35-37,共3页

精确覆盖率问题随着网络的建设变得越来越复杂,如何有效发现影响网络精确覆盖率指标的问题成为了重中之重,面对精确覆盖率指标的优化,我们有很多疑问:如何提升这个指标,是我们需要思考的问题,精确覆盖率优化是长期的,动态的,因此有必要... 精确覆盖率问题随着网络的建设变得越来越复杂,如何有效发现影响网络精确覆盖率指标的问题成为了重中之重,面对精确覆盖率指标的优化,我们有很多疑问:如何提升这个指标,是我们需要思考的问题,精确覆盖率优化是长期的,动态的,因此有必要研究一套行之有效的优化方案。 展开更多

关键词 精确覆盖率 网络结构 趋势 优化方案 LTE网络

下载PDF 职称材料

CDMA无线网精确化覆盖思路分析 被引量：2

7

作者 蒋晓虞 胡军 +1 位作者 张磊 孔繁俊 《移动通信》 2011年第12期26-30,共5页

文章针对精确化覆盖提出了分析流程,通过测试数据、后台分析数据来确定网络弱覆盖区,针对不同类型的覆盖问题提出解决思路;对几类典型的精确化覆盖场景,给出了低成本、高效的覆盖思路。

关键词 CDMA精确化覆盖 弱覆盖区 Ec/Io 薄覆盖

下载PDF 职称材料

覆盖问题解决技巧的深入探讨

8

作者 纪政 宋海岸 《软件导刊》 2010年第9期58-60,共3页

覆盖问题是一种常见的问题,由于其状态复杂,数据规模大,直接的搜索往往效率过低,复杂度难以承受。从解决覆盖问题的一般方法出发,深入探讨了动态规划、数学归纳法,以及Dancing links算法的转化在覆盖问题中的应用,充分弥补了现今大多数... 覆盖问题是一种常见的问题,由于其状态复杂,数据规模大,直接的搜索往往效率过低,复杂度难以承受。从解决覆盖问题的一般方法出发,深入探讨了动态规划、数学归纳法,以及Dancing links算法的转化在覆盖问题中的应用,充分弥补了现今大多数书籍和文献中解决覆盖问题时忽视算法设计技巧的缺点。 展开更多

关键词 精确覆盖 DANCING LINKS 数独

下载PDF 职称材料

一种基于虚拟力补偿的三维空间自主部署算法 被引量：2

9

作者 谭励 王云会 +2 位作者 杨明华 胡计鹏 杨朝玉 《仪器仪表学报》 EI CAS CSCD 北大核心 2015年第11期2570-2578,共9页

针对三维空间中无线传感网络的覆盖目标复杂多样,容易出现部署"空洞",难以实现均匀部署的问题,提出了一种基于虚拟力补偿的三维空间自主部署算法。首先建立了节点模型和覆盖目标模型。其次将传统的虚拟力算法从二维扩展到三... 针对三维空间中无线传感网络的覆盖目标复杂多样,容易出现部署"空洞",难以实现均匀部署的问题,提出了一种基于虚拟力补偿的三维空间自主部署算法。首先建立了节点模型和覆盖目标模型。其次将传统的虚拟力算法从二维扩展到三维空间,提出了覆盖目标虚拟力补偿的概念,使网络中的节点能够根据覆盖目标的特点,完成均匀的覆盖。仿真实验表明该算法覆盖率能达到95%以上,同时均匀度有10%的提升。最后通过四旋翼实验平台对算法的有效性进行了验证。 展开更多

关键词 三维部署 虚拟力算法 目标建模 精确覆盖

下载PDF 职称材料

LTE小基站建设策略探讨 被引量：19

10

作者 苏雄生 《电信快报（网络与通信）》 2014年第10期13-16,共4页

在LTE时代,小基站在网络部署中正发挥着越来越大的作用,LTE小基站解决了新建站址匮乏的难题,弥补了LTE高频段损耗大、覆盖较差的劣势,除了能完善网络中的覆盖盲区,在提供大带宽数据业务等方面也发挥着更重要的作用。文章介绍目前网络中... 在LTE时代,小基站在网络部署中正发挥着越来越大的作用,LTE小基站解决了新建站址匮乏的难题,弥补了LTE高频段损耗大、覆盖较差的劣势,除了能完善网络中的覆盖盲区,在提供大带宽数据业务等方面也发挥着更重要的作用。文章介绍目前网络中常用的小基站类型,结合案例分析提出小基站的建设策略,并提出解决基站小区间干扰协调的措施和手段。 展开更多

关键词 小基站 覆盖补盲 精确覆盖 干扰协调

下载PDF 职称材料

基于虚拟力的三维部署技术研究 被引量：8

11

作者 李享 李轩涯 《科学技术与工程》 北大核心 2013年第9期2412-2420,2425,共10页

为了能够实现在复杂多变的环境中执行对未知目标体的探测任务,提出了一种基于虚拟力的在三维空间中的对复杂目标进行精确覆盖的部署算法。首先将虚拟力算法从二维空间拓展到三维空间,创新地提出了自适应中心引力和目标斥力网的概念,使... 为了能够实现在复杂多变的环境中执行对未知目标体的探测任务,提出了一种基于虚拟力的在三维空间中的对复杂目标进行精确覆盖的部署算法。首先将虚拟力算法从二维空间拓展到三维空间,创新地提出了自适应中心引力和目标斥力网的概念,使传感器节点能够根据探测目标形态的不同,自主进行调整部署形态,自适应地覆盖未知目标进行有针对性的探测任务。在仿真试验中,实现了对不同形态的复杂目标进行精确覆盖,并且与传统的虚拟力算法相比,覆盖率和均衡度都有较大提升。因此算法能在针对复杂的未知目标进行探测时,以较小的代价高效地完成探测任务,提出了一个从区域覆盖部署到目标精确覆盖部署的新型的研究方向。 展开更多

关键词 虚拟力 三维部署 复杂目标 精确覆盖

下载PDF 职称材料

关于John Beebee的一个问题

12

作者 朱群生 《南京师大学报（自然科学版）》 CAS CSCD 2001年第2期20-22,共3页

回答了JohnBeebee关于不相交同余覆盖的一个问题 .

关键词 不同余精确覆盖 等差数列 同余

下载PDF 职称材料

Dancing Links X在智能导检中的应用研究

13

作者 付冰 胡云 周作建 《计算机时代》 2022年第3期61-64,69,共5页

为了缩短健康体检排队等待时间、预测待检项目整体顺序,以X算法、精确覆盖、广义覆盖、Dancing Links作为理论基础,提出了应用Dancing Links X解决体检时间广义覆盖问题的方法。通过构建以服务时间成本、排队等待时间成本的总成本最小... 为了缩短健康体检排队等待时间、预测待检项目整体顺序,以X算法、精确覆盖、广义覆盖、Dancing Links作为理论基础,提出了应用Dancing Links X解决体检时间广义覆盖问题的方法。通过构建以服务时间成本、排队等待时间成本的总成本最小化为目标的Dancing Links X三重约束来搜索可行性解,并摘选最小值。以此模型完成的规划体检顺序,实现了对体检路线的预测,表明基于Dancing Links X三重约束的智能导检路径优化模型可以对待检项目顺序及时间节点预测,为导检的智能化研究提供新思路。 展开更多

关键词 智能导检 Dancing Links X算法 广义覆盖 精确覆盖

下载PDF 职称材料

用舞蹈链求解数独的算法解析及优化

14

作者 肖波 《福建电脑》 2021年第8期157-160,共4页

舞蹈链是一种用特殊的数据结构来实现的X算法,主要用来解决精确覆盖问题,并在求解问题上表现出非常优越的性能。用舞蹈链求解数独,是将数独问题按特定的规则转化为精确覆盖问题后再进行求解。通过对问题转化和求解过程的原理解析,使读... 舞蹈链是一种用特殊的数据结构来实现的X算法,主要用来解决精确覆盖问题,并在求解问题上表现出非常优越的性能。用舞蹈链求解数独,是将数独问题按特定的规则转化为精确覆盖问题后再进行求解。通过对问题转化和求解过程的原理解析,使读者加深对舞蹈链算法的理解。结合数独的特性和人工求解策略对算法进行优化,可以更好地提高算法的效率。 展开更多

关键词 数独 舞蹈链 精确覆盖 矩阵

下载PDF 职称材料

内蒙古联通LTE分场景建设应用研究

15

作者 乌文全 《信息通信》 2017年第11期195-198,共4页

与3G组网相同的宏蜂窝覆盖仍然是LTE建网的基础,但是宏蜂窝不能够解决所有问题,特别是相对独立的区域,即我们所说的"场景",包括综合园区、大型住宅、大学校园、体育场馆、工业园区等,为此,文章对分场景的组网思路、组网关键... 与3G组网相同的宏蜂窝覆盖仍然是LTE建网的基础,但是宏蜂窝不能够解决所有问题,特别是相对独立的区域,即我们所说的"场景",包括综合园区、大型住宅、大学校园、体育场馆、工业园区等,为此,文章对分场景的组网思路、组网关键点、组网方案进行进一步探讨和总结,为实现"基于场景的差异化精确组网"提供方向。 展开更多

关键词 分场景建设 异构网 宏微协同 精确覆盖

下载PDF 职称材料