加权集合覆盖问题的加权分治算法

加权分治技术是一种用于算法分析和设计的新方法,该技术通过对处理对象按不同重要程度而赋予不同的权值来更加精确的描述算法分支子问题规模的大小,从而降低算法的时间复杂度.分支降阶技术是广泛用于求解组合优化领域难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并用递归来求解这些子问题.加权集合覆盖问题是一个典型的NP难题,利用加权分治技术对集合覆盖问题进行研究,给出了一个精确算法,降低了算法的时间复杂度.在进行算法处理之前,将问题转换成二分图,并提出相应的降阶规则,将原问题的规模进行了缩小,在此基础上运用加权分治技术来分析其算法的复杂度.研究表明运用加权分治技术能够得到较传统算法更精确的时间复杂度.

基于面上DNA计算求解最小集合覆盖问题

利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。

基于DNA粘贴模型求解最小集合覆盖问题

运用DNA计算模式中基于粘贴运算的粘贴模型求解最小集合覆盖问题.在粘贴模型中,用存储复合体来表示子集,并利用粘贴运算的巨大并行性,可以有效地求解最小集合覆盖问题.举例说明了基于DNA粘贴模型求解最小集合覆盖问题的过程.

加权互斥最大集合覆盖问题的精确算法

加权互斥最大集合覆盖问题是一个NP难问题,为解决该问题设计一个分支搜索算法,采用测量治之方法对算法运行时间界进行分析,得到算法的时间复杂度为O^*(1.3132 m),改进该问题原有的最佳运行时间界O^*(1.325 m)。通过比较可知,基于测量治之方法分析得到的结果优于传统方法分析得到的结果,可以在不改变算法的前提下通过度量设置的改变进一步改进算法的运行时间界,度量设置方案越详细得到的结果更好。

加权最小顶点覆盖的加权分治算法

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性.

基于简单网络断层扫描的失效链路定位研究

失效链路是无线传感器网络中一种典型的网络故障现象,严重影响了无线传感器网络的运行与服务质量,必须加以发现并修复。主要研究了基于简单网络断层扫描方法定位失效链路的技术。引入二元分离模型描述链路状态,在已知链路状态先验分布条件下,失效链路定位问题描述为最大后验估计问题。通过将失效链路定位问题映射为加权最小集合覆盖问题,提出了一种基于启发策略的失效链路定位算法。仿真实验结果表明,该算法具有可行性和有效性。

无线传感器网络启发式失效链路推断算法

无线传感器网络的实际应用产生了对网络故障管理的迫切需求。严重报文丢失的失效链路影响无线传感器网络的性能,需加以发现并修复。受有限资源的约束,采用被动端到端测量的方法,利用网络断层扫描技术推断失效链路。通过将失效链路推断问题映射为最小集合覆盖问题,提出了一种基于启发策略的失效链路推断算法。仿真实验结果表明该算法具有可行性和有效性。

一种协作群智感知任务分配的贪心算法

关于群智感知的任务分配算法,目前已有若干研究.然而,现有的研究很少涉及到群智感知中需要多人协作的复杂感知任务,本文则对这一类任务进行研究.首先,展示了一个与位置相关的协作群智感知任务分配问题,并对其展开形式化分析;然后,证明了该问题为NP难解问题,并针对这一问题提出了一个基于贪心策略和最小加权集合覆盖的任务分配算法;最后,用多个算法通过实验作比较,证明了所提算法的优越性.