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

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

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

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

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

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