无线传感器网络关键区域覆盖优化算法

针对无线传感器网络中的关键区域覆盖NP完全问题,提出了一种启发式的关键区域覆盖优化算法CACOA.该算法对关键区域格点与一般区域格点,分配不同的权值创建感知区域图和终端集合,并以迭代合并方式创建加权节点Steiner树,进而形成具有最少数量的格点集合,并以格点集合中优化的格点位置来构建覆盖关键区域的传感器放置方法.理论分析证明了提出的CACOA算法一定能完全覆盖关键区域并形成一个有效的无线传感器网络,且算法的复杂度为O(n4).详细的仿真实验及与现有覆盖机制NPCC的比较表明,提出的覆盖优化算法CACOA在关键区域格点数、感知范围、发送范围和关键区域格点选择分布概率变化时放置的传感器数量明显少于NPCC覆盖机制.     

一种求解带权集合覆盖问题的近似算法

以优化形式描述的集合覆盖问题是一个NP难问题,设计快速有效的近似算法,具有重要的理论与现实意义.基于贪心算法思想,提出了一种求解带权集合覆盖问题的近似算法,并讨论了该算法的相对近似比.     

无线传感器网络中最优覆盖节点集的求解算法

在传感器节点高密度部署的环境中,如何保证在满足"覆盖要求"的同时,使用的节点数目最小是一个NP完全问题.结合遗传算法在处理集合搜索中的广泛应用,设计了一种基于遗传算法的节点集搜索机制.在保证充分覆盖的前提下,令一部分冗余节点进入低功耗休眠状态,形成最优覆盖节点集.最后进行了算法的性能评价和网络覆盖的仿真实验.结果表明,该算法能以较小的代价完成最优节点集的搜索,有效提高整个网络的生存时间.     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

有限集合的相容关系与完全覆盖

非空有限集合A的完全覆盖S={A1,A2,…,An}决定了A上的相容关系R=∪ni=1(Ai×Ai).研究了R的最大相容类集合和完全覆盖S之间的关系,给出相容的完全覆盖、极大相容完全覆盖、极小相容完全覆盖和恰当完全覆盖的定义,证明了相容的完全覆盖其成员均为R的最大相容类,而极大相容完全覆盖恰为R的最大相容类的全体,并给出这几种完全覆盖之间的关系.     

无线传感器网络多目标关联覆盖

针对多目标网络覆盖中传感器节点和目标的关联关系,依据数据挖掘中的关联规则挖掘技术,设计了多目标关联覆盖算法MTACA．考虑到能量的有效性,利用关联规则挖掘方法动态地确定目标集合和传感器节点集合,通过节点集合工作状态的转换完成目标的完全覆盖,延长了网络使用寿命．同时,改进了适应区域覆盖的PEAS算法,使其适应多目标覆盖的应用．通过仿真对MTACA和改进的PEAS算法进行了性能分析．结果表明：MTACA算法和改进的PEAS算法在目标完全覆盖能力和网络使用寿命上明显优于随机部署网络;MTACA算法在目标完全覆盖能力、网络使用寿命、网络剩余能量以及节点间能量消耗均匀性上明显优于改进PEAS算法．     

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.     

一种基于混合覆盖矩阵的pairwise测试用例生成方法

测试用例集的生成是组合测试的一个关键问题,但是使用完全组合覆盖生成测试用例集是NP完全问题.对偶覆盖要求测试用例集至少覆盖输入参数的每一个取值对.该类方法在测试代价和效率方面进行了很好的折中,一直受到广泛关注.基于混合覆盖矩阵,提出了一种pairwise覆盖的测试用例生成方法.实例分析表明,该方法具有生成的测试用例较少、时间消耗小等特点.     

密钥覆盖问题的NP完全性证明

 给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础.     

关于集合的等价格和完全O—单半群的同余格

本文证明了任何集合的等价格都是M对称格,并将Pastijn和Petrich关于正则半群的同余理论应用到完全O-单半群中,从而得到比较简明及系统的完全O-单半群的同余理论。     

关于并列管道型机器排序的复杂性

考虑一个有两个功能部件的机器模型,每个部件要么是有序的,要么类似于管道并列的。关于这类机器模型的3个 NP-完成结果在[1]中有所阐述。本文说明的是当先前限制因素和其他限制因素削弱时,这三个NP-完成结果仍然正确。     

基于GAlib和聚类技术的WMN网关部署优化研究

将网关部署问题化为数学模型,用集合覆盖问题求解多目标优化问题。其次采取了分簇、遗传算法、聚类算法相结合的方式设计了算法,实现部署网关的数量较少,骨干网中普通路由器与对应网关间的跳数较小的目标。同时仿真分析表明该聚类技术对仅基于GAlib提出的网关部署方案有着良好的优化效果。     

遗传算法在WSNs多Sink节点布局中的应用

无线传感器网络应用一直受到有限资源及能量的约束,sink节点布局算法是长时期内需要研究的一个关键问题.实际情况下,由于节点资源受限或无线链路的问题,sink节点经常存在服务失败的情况.因此,提出一种无线传感器网络中多sink节点的P中值布局模型,同时使用遗传算法对属于NP完全问题的sink节点布局模型进行求解计算,并对算法的计算精度、效率进行了分析.仿真实验结果表明,基于遗传算法而提出的布局模型能够有效降低无线传感器网络的能量消耗,提高网络服务效率,延长网络的生存期.     

四点法曲面造型的自然边界条件

研究四点插值细分法在曲线曲面造型应用中的边界条件确定问题．针对四点法的特点，对传统几何造型技术中常用的非线性自然边界条件决定方法进行改进，基于等腰梯形四点共圆的事实，提出通过求轴对称点而得自然边界点的线性方法，很好地解决了四点法在曲面造型应用中的关键问题。     

数据挖掘中一种基于集合覆盖的元素重要性估计算法

对给定数据集合的元素重要性进行估计是数据挖掘领域中的一项重要应用。现有的技术都是通过排序或选择来发现重要元素,其主要缺点是没考虑高排名对象可能非常相似甚至完全相同这一事实,忽略了高排名对象间的冗余性。因此,在强调多样性的场合,该方法性能有限。本文通过将排序和选择相结合,提出一种基于集合覆盖的元素重要性估计算法。该算法不仅考察单个集合覆盖的解,而且计算元素参与的高质量集合覆盖数量,进而为元素分配重要性分值。基于实际数据的实验和用户学习结果表明,本文算法性能高效,元素重要性评估结果的有用性高,且与人类感知相一致。     

Heawood图的一对对偶树的分解和4-着色

阐明了任意平图的4-着色的主要思路,给出了对偶树的定义。对偶图中的一对对偶树与对偶图的Hamilton路径相互依存,提出了任意平图的4-着色的方法步骤。得到利用上述方法得到的一对对偶树及具有的性质。介绍了Heawood图的由来和基本特点、Heawood图的4-着色的2种方法步骤,通过对偶图的2个区域的划分,实施了Heawood图的4-着色,借助于Heawood图的对偶图的Hamilton路径的分解构造了2棵对偶树。借助于此方法所得的Heawood图的25个顶点的4-着色方案达到236个,从而使Kempe的4-cc猜想"证明"中的漏洞得到弥补。     

部分赋值一阶逻辑公式的条件求值——NP完全性及在特定情况下的求解

部分赋值的一阶逻辑公式的条件求值问题是在关系数据库应用,尤其是在分布式环境下应用中经常遇到的问题。此问题在一般意义下的解是NP完全的。本文首先证明此问题的解存在的充要条件,从而推知其NP完全性。然后给出该问题在一种特定情况下的求解方法。     

禁忌搜索与遗传算法在求解时间表问题中的对比研究

时间表问题属于NP完全问题，一般来说，只能找出用于实际工作的“亚优解”(sub-optimal solution)，对遗传算法和禁忌搜索算法用于求解时间表问题进行了对比研究，结果表明，禁忌搜索算法能找出比遗传算法更好的时间表，而且禁忌搜索算法所花费的搜索时间也比遗传算法少。但是，遗传算法能同时产生几个不同的逼近最优解的解。     

浅析邓小平对毛泽东人才思想的创造性运用与发展

邓小平的人才理论是邓小平理论的重要组成部分,他在人才地位、人才衡量标准、人才选拔任用以及人才培养等方面都是对毛泽东人才思想的创新与发展。