3-维匹配问题的一种固定参数枚举算法

枚举问题的多个最优解是计算机科学中人们日益关注的一个研究方向。运用固定参数枚举理论和着色技术对3-维匹配问题提出了一个高效的固定参数枚举算法,即给定一个含有n个带权值的元组集合S,两个非负整数k和z,该算法能在时间O(5.483kkn2z)内枚举出S中权值最大的z个k-matchings,进而表明了3-维匹配问题是固定参数线性可枚举的。     

带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).     

超平面覆盖问题的参数化改进算法

超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+nlogk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+nlogk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1(dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进.     

加权3-Set Packing 的改进算法

Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).     

一个基于着色和动态规划的3-维匹配问题算法

3-维匹配问题是六个经典的NP完全问题之一,在调度、分配、交通和网络流等问题方面有很强的应用.参数计算理论是近年来发展起来的研究和解决NP-难问题的新方法.针对3-维匹配问题,目前确定式参数算法的最好结果是O*(163k).本文结合着色和动态规划技术,提出了一个算法运行时间为O*(3.423k)的确定式参数算法,大大提高了算法的运行效率.     

基于加权分治技术的set packing精确算法

加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.set packing问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的set packing问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N) 的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.     

P2-Packing问题参数算法的改进

P_2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O(2~(5.301k))的参数算法,其核的大小为15k.通过对P_2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O(2~(4.142k))的参数算法,大幅度改进了目前文献中的最好结果.     

基于局部比值法的强弦图带权控制集问题的线性时间算法

一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。     

工作流系统带权角色与周期时间访问控制模型

带权角色激活任务和周期时间授权是工作流系统访问控制研究尚未解决的核心问题.以基于角色的访问控制模型为基础,提出了一种新的工作流系统带权角色与周期时间访问控制模型WRPTAC(weighted role and periodic time access control).讨论了周期时间表示方法,定义了工作流系统授权新概念和时态授权推导规则,给出了时间复杂度为O(n²)的时态授权推导规则一致性验证图论算法,并定义了任务激活约束规则.它能够表达复杂的工作流系统访问控制约束.     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

Generalised fuzzy weighted mean and its applications

Fuzzy weighted arithmetic average or fuzzy weighted average (FWA) for short has been deeply studied. However, no attention has been paid to other fuzzy weighted means such as fuzzy weighted geometric mean (FWGM), fuzzy weighted harmonic mean (FWHM) and the like. This paper presents a very general fuzzy weighted mean, which we refer to as generalised fuzzy weighted mean (GFWM). It includes FWA, FWGM, FWHM, fuzzy weighted quadratic mean (FWQM) and fuzzy weighted root-power mean (FWRM) as its special cases. Linear programming models for solving GFWM and its special cases are developed and the order relationships among FWA, FWGM and FWHM are investigated. Numerical examples that illustrate the computational processes of FWA, FWGM and FWHM are provided and their order relationships are numerically examined.     

信息过滤中基于统计与规则的关键词抽取研究

目前的研究大多把向量空间模型中特征项的选取与权重的计算分开,掩盖中文分词时产生的语义缺失,导致特征项区分度下降。为此,提出一种基于统计与规则的关键词抽取方法。利用句法规则提取出基本短语,以取代词袋模型中的词,考虑特征项位置、分布及语法角色等信息,综合加权计算特征项权重。实验结果表明,与现有方法相比,该方法能够更有效地进行文本信息过滤。     

一种新的加权关联规则模型

关联规则挖掘可以发现大量数据项集之间隐含的关系,在许多领域得到了广泛应用。目前很多关联规则挖掘算法已经被提出,这些算法一般都认为每个数据项的重要性相同。然而在现实中各个项目的重要性往往不同,从决策者角度出发,他们往往会优先考虑利润较高的项目,而忽略利润较低的项目。论文分析了现有加权关联规则文献中存在的问题,提出了一种新的加权关联规则模型,给出了有效挖掘加权频繁项集的MWFI算法。     

Reliability analysis of computer solutions of systems of linear algebraic equations with approximate initial data

A weighted least squares problem {ie863-01} with positive definite weights M and N is considered, where A ∈ R^m×n is a rank-deficient matrix, b ∈ R^m. The hereditary, computational, and global errors of a weighted normal pseudosolution are estimated for perturbed initial data, including the case where the rank of the perturbed matrix varies. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 83–95, November–December 2008.     

一种改进的加权关联规则挖掘方法

考虑属性数量和属性权值对关联规则的影响,提出一种新的加权支持度和加权置信度计算方法,在挖掘加权关联规则时通过改进加权支持度设置模型保持Apriori算法的频繁集向下封闭特性。与Apriori算法和水平加权关联规则挖掘方法的比较结果证明该方法能快速有效地挖掘重要的关联规则。     

带权区域上任意两点间的近似最优路径算法调研

自1991年由Mitchell和Papadimitriou提出带权值区域问题以来,人们开始认识到带权值模型的通用性较强,陆续有很多学者开始研究这个问题。在二维带权区域近似最优路径问题中,一个二维空间被划分成n个三角形区域,每个三角形区域与一个正的权值相关联,不同的三角形区域权值可以不同。如何快速求解出任意两点间的一条路径并使其代价最少就是文中研究的内容。对此问题的国内外现状进行了详细阐述与比较,并提出一个能获得更为逼近最优路径的结果且牺牲运行时间较少的可行方案,最后指出此问题的发展趋势。     

一种改进的加权序列模式挖掘算法

在加权序列模式挖掘中,基于候选码生成-测试方法的MWSP是目前应用性最好的算法之一,然而在挖掘过程中容易出现候选组合爆炸的情况,为此文章提出了一种高效的加权序列模式挖掘算法（PWSM）。PWSM算法引入k-最小加权支持数概念并利用前缀投影数据库原理有效地避免了候选组合爆炸的发生,并且在挖掘的过程中充分利用最小加权支持数,再次对算法进行优化。实验表明,该算法较MWSP算法能更加有效地从序列数据库中挖掘加权序列模式。     

一种改进的加权频繁项集挖掘算法

FP-growth算法是挖掘频繁项集的经典算法,它利用FP-树这种紧凑的数据结构存储事务数据库与频繁项集挖掘相关的全部信息,但对于挖掘加权频繁项集并不合适。分析了现有加权频繁项集挖掘算法中存在的问题,并对FP-树进行改进,构造新的加权FP-树,提出了有效挖掘加权频繁项集的算法。最后举例说明了算法的挖掘过程,并通过实验验证了算法的有效性。     

一种基于概率的加权关联规则挖掘算法

针对关联规则数据挖掘在实际应用中出现的问题:不能挖掘小概率事件中的关联规则, 提出了基于概率分布的加权关联规则挖掘算法。该算法同时改进了加权支持度计算方法,保持 Apriori算法的频繁集向下封闭的特性,并在实践中得到了有效的应用。     

加权Myriad滤波器的研究

为了克服在图像处理领域常用的线性滤波器的不足,非线性滤波器就成了非常有意义的一个研究方向。Myriad算法是基于稳定模型的一种非线性滤波算法,它能够充分利用稳定分布的多种模式来进行非线性信号加权处理。Myriad滤波作为一种图像滤波算法,和常用的中值滤波相比,其优势在于不仅能够有效地滤除盐椒噪声,还能够使细节部分保持得更好。本文提出了中心加权Myriad滤波器和自适应加权Myriad滤波器,通过对参数K的调节,平衡在窗口中去除噪声和保持图像细节之间的矛盾,而所加权重也能够根据图像自适应变化。