基于物品移动的局内装箱算法的改进

局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.     

局内装箱算法综述

系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。     

图近似查询算法研究

从数据管理中的近似查询方向,对图数据的近似查询算法进行了研究.依据近似查询的类别,分别介绍了近似查询中的经典算法,并对这些算法进行了详细的分析和讨论,从索引单元以及索引机制比较了各种算法适用的范围以及应用领域.重点阐述和比较了各算法的特点及查询性能,分析了各个算法存在的优势和不足.对近似查询中现有算法的不足及未来的研究方向进行了讨论.     

演化算法求解近似最大匹配问题的时间复杂性分析

虽然演化算法已经广泛地被用于求解不同的组合优化问题，但是对于其时间复杂性目前仍然了解得比较少。最近，在这方面有了一些初步的研究，然而迄今的结果大多局限于讨论一些简单的演化算法(如(1 1)类型的演化策略)和人造的模型问题(如二进制类型的示例问题)，很少涉及到使用种群、杂交操作演化算法和传统的组合优化问题。因此，理论上需要分析演化算法，求解一些典型的组合优化问题的时间复杂性。     

粗糙集的近似约简及其算法

针对经典粗糙集中属性约简的不足,进一步拓展粗糙集属性约简的应用。提出了一种粗糙集属性近似约简的概念和一种新的粗糙集属性重要性的定义并给出和证明了属性近似约简的性质,理论证明了近似属性约简是传统属性约简的一种推广。在保持知识库分类能力基本不变的条件下,利用所给属性重要性作为启发信息给出了粗糙集属性近似约简的算法。通过一个具体的例子,说明了近似属性约简在信息系统中处理模糊和不确定性知识的可行性和有效性。     

基于高阶近似的链路预测算法

目前大部分链路预测算法只研究了节点与邻居节点之间的一阶相似性，没有考虑节点与邻居的邻居节点之间的高阶相似性关系。针对此问题，提出一种基于高阶近似的链路预测算法（LP-HOPA）。首先，求出网络的归一化邻接矩阵和相似度矩阵；其次，利用矩阵分解的方法将相似度矩阵进行分解，得到网络节点的表示向量以及其上下文的表示向量；然后，通过高阶网络表示学习的网络嵌入更新（NEU）算法对原始相似度矩阵进行高阶优化，并利用归一化的邻接矩阵计算出更高阶的相似度矩阵表示；最后，在四个真实的数据集上进行大量的实验。实验结果表明，与原始链路预测算法相比，大部分利用LP-HOPA优化后的链路预测算法准确率提升了4%到50%。此外，LP-HOPA算法能够将基于低阶网络局部结构信息的链路预测算法转换为基于节点高阶特征的链路预测算法，在一定程度上肯定了基于高阶近似链路预测算法的有效性和可行性。     

网页近似重复检测算法研究

搜索引擎的爬行程序在日益庞大的互联网中采集到的网页包含有大量的重复或近似重复网页,这不仅降低了检索效率,增加了存储空间,还降低了最终用户的体验。本文针对现有的网页近似重复检测技术进行了比较,并重点讨论了改进的模糊哈希算法对网页内容进行近似重复检测。     

基于签名的近似垃圾邮件检测算法

针对垃圾邮件短小、一定时间内在网络上重复、大量地散发的特点,提出了基于签名的近似垃圾邮件检测算法（ASD）。该算法以句为基本单位,求取邮件所含的全部句子的摘要,垃圾邮件的近似检测转变为两个摘要集近似度的比较。通过与近似文本查询算法DSC、DSC-SS、I-Match的比较,ASD算法在近似垃圾邮件查询中,表现出样本集的存储空间大小适中、运算时问短、鲁棒性高、高准确率、高召回率的特征。     

二维模式近似匹配的快速算法

给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。     

基于近似度的不完备信息系统属性约简

在容差关系下,针对属性集P在分类中的不同个体贡献,引入粗糙集的近似度概念,结合属于/不属于集合Rp(x)的元素贡献的不确定性,定义一种新的知识熵,从而实现基于近似度的不完备信息系统属性约简算法。仿真结果表明,与IEARA算法相比,该算法具有较高的约简效率。     

基于近似技术的双层规划进化算法

双层规划涉及上层和下层两个最优化问题,上层规划问题的约束域由下层规划问题隐式确定,双层优化以上层目标为主,而下层目标在下层变量方面必须达到最优。双层规划问题的递阶结构使其具有很高的计算复杂度,特别是频繁计算下层问题会累计很大的计算量。为了有效求解这类问题,提出一种基于近似技术的进化算法。首先,采取多种群协同进化,分别利用交叉和变异算子平衡算法的开采和勘探能力;其次,基于灵敏度分析理论,设计了新个体的近似评价方式以减少算法的下层求解次数。一个算例的近似效果演示结果表明,由近似技术得到的近似后代个体与精确后代个体的位置大部分是重合的。除此之外,在10个常用算例上的结果显示,所提算法比多值映射算法获得了更好的最优解;并且根据CPU时间比较,说明近似技术有效地提高了找到最优解的速度,减少了运行时间,验证了所提算法采取的近似技术的有效性。     

基于模糊近似度的Web文本过滤模型

从1991年诞生以来,WWW(World Wide Web)得到了迅猛的发展,它已经成为拥有约3亿用户、400万站点的巨大分布式信息空间、它包含了技术资料、商业信息、新闻报道、娱乐信息等多种类别和形式的信息,资源分布很分散,且没有统一的管理和结构。如何快速、准确地从浩瀚的信息资源中提取用户所需要的信息已经成为一个新的研究课题。WWW上最多的就是文本信息,因此Web信息处理的核心就是如何处理这些Web文档。数据挖掘和知识发现(Data Mining and Knowl-edge Discovery,DMKD)可以帮助人们从大量原始数据中挖掘出隐含的、有用的尚未发现的信息和知识,有效地解决信息丰富知识贫乏问题。因此,基于Web文本信息的挖掘作为数据挖掘的一个新主题,引起了人们的极大兴趣。Web文本信息的挖掘就是在大量训练样本的基础上,得到文本数据间的内在特征,并以此为依据在网络资源中进行有目的的信息提取。在本文中,我们首先介绍了Web文本信息的向量空间表示模型(VSM),并在此模型的基础上提出了一     

信度网近似推理算法（下）

2 仿真方法基于信度网的精确推理算法通过利用各节点之间的条件独立性来加快推理计算,前面介绍的基于搜索的方法则不仅利用节点间的条件独立性而且利用概率分布的一些特性进行近似计算,但是在很复杂的问题领域要想通过分析条件独立性和利用概率分布的特征来加速推理计算往往不太现实。基于仿真的方法则另     

面向缺失数据的布鲁姆近似成员查询算法

随着网络的发展,越来越多的场景需要在不完整数据下进行近似成员查询,传统成员查询的布鲁姆过滤器不能满足上述要求。提出面向缺失数据的布鲁姆近似查询算法,先对高维不完整数据的缺失部分进行预填充,通过PCA算法,将高维数据转换到低维数据,使用局部敏感哈希函数与标准哈希函数结合的方式将低维数据存储到布鲁姆过滤器中。使用两个真实数据集验证了所提算法的功能,所提面向缺失数据的布鲁姆近似查询算法,能有效地解决存在缺失数据的近似成员查询问题。     

一种楔波近似快速算法

为了降低多边形区域上矩计算的复杂度和减少楔波近似的运算时间，提出了一种楔波近似快速新算法。采用任意局部退化模型代替局部恒定退化模型，对比实验结果表明：新算法与现有文献的算法相比，运算速度提高了3个数量级；适用于不同参数的模型，灵活性得到较大提高。     

具有稀疏障碍的近似迷宫算法

本文中给出了一个在具有稀疏障碍的迷宫中寻找给定两个单元之间的最短路径的走迷宫算法,算法以“不改变方向”为预测条件,沿直线方向扩展。经大量的随机实验对比,结果证明本文中的算法大量地缩减了搜索范围,是一个高效的算法。     

信度网近似推理算法（上）

信度网提供了一套强有力的图形工具来表达基于概率的领域知识,并且已经成功地应用在诸多实际问题中,如：故障诊断、预测、模式识别、数据挖掘等。目前基于信度网提出了多种推理算法以精确计算待求概率值[2,4,12,19,21-23,26,30]这些算法在某些信度网上具有很高的推理效率,但是在最坏情况下这些算法的计算时间复杂度都是NP－难的。     

基于网格上近似的大规模数据集离群点检测算法GROUT

通过对数据集中离群点分布特性的分析，给出离群点的解析定义，并在度量意义下采用数据空间网格化方法实现对密集数据主体的过滤，从而构造了在时间和空间上均具有极高效率的离群点检测算法。     

一种基于路径相似度的蚁群算法

提出了路径相似度的概念,并根据较优可行解与最优解的相似度,来进行路径选择和信息素更新,以求能更快加速收敛和防止早熟、停滞现象。该算法根据截之间的相似度,自适应地调整路径选择策略和信息量更新策略。基于旅行商问题的实验验证了算法比一般蚁群算法具有更好的全局搜索能力、收敛速度和解的多样性。