Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

树上推广的Multicut问题的近似算法

给定边上有费用的树T,终端集合族X={S\\-1,S\\-2,…,S\\-l},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2（l-k+1）,k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O（n\\+\\{16-ε\\}）以内是困难的（对某个小的常数ε>0）.     

一类非线性极小极大问题的改进粒子群算法

针对一类非线性极小极大问题目标函数非光滑的特点给求解带来的困难,利用改进的粒子群算法并结合极大熵函数法给出了此类问题的一种新的有效算法。首先利用极大熵函数将无约束和有约束极小极大问题转化为一个光滑函数的无约束最优化问题,将此光滑函数作为粒子群算法的适应值函数;然后用数学中的外推方法给出一个新的粒子位置更新公式,并应用这个改进的粒子群算法来优化此问题。数值结果表明,该算法收敛快﹑数值稳定性好,是求解非线性极小极大问题的一种有效算法。     

改进的Bloom Filter算法及其性能分析

基于Bloom Filter的搜索过滤器不仅会有误判的发生,并且在查询目标进入过滤器后,查询整个关键字的步骤耗费太多成本.针对上述问题,提出了一套新的搜索过滤器架构.此架构在比对步骤中以关键字的特征来建立一个查表目录,当误判发生时,只需要以其关键字最小值所分配的位置做查询并判别是否正确.实验结果表明,该过滤器不仅能减少误判率的发生,还能降低整个过滤器的搜索成本,让搜索过滤器有更好的性能.     

求解多车型校车路径问题的混合集合划分的GRASP算法

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。     

基于幂律分布的网络用户快速排序算法

随着网络论坛、博客、微博的发展,引出社会网络中的用户排序问题。将在线网络论坛中用户映射为节点,用户评论过程中形成的回复关系映射为有向关联图,其节点度符合幂律分布。且论坛中用户的主题发布行为和回复关系符合Pagerank算法的互增强和随机游走特性,因此选用Pagerank算法排序用户影响力。该文提出的研究问题 如何提高用户排序应用中数据的存储和运行效率。天涯网络论坛中80%以上用户入度为0,据此,根据入度是否为0划分为两个集合,对入度为0集合按出度构造链接表,设计了基于集合划分的高效排序算法SD-Rank。SD-Rank时空复杂性为O(V′),V′为入度非0节点集。对天涯网络论坛真实用户数据的实验结果表明 SD-Rank算法时空复杂性优于Pagerank算法。     

分布式信息检索中文档集合划分问题的评价

分布式信息检索的文档集合划分方案的评价是一个困难的问题,目前还没有良好的评价标准.从文档集合划分问题本身出发,给出了两个划分模型来刻画文档集合划分问题,从而使这两个模型可以作为文档集合划分的有效评价指标.在此基础上,提出了一种类Huffman编码的模型快速求解算法,可以求出在给定查询测试集情况下的最优文档划分方案,该方案可以作为其他文档划分方案的参考.实验表明,两个文档划分模型可以成为有效的文档集合划分评价标准.     

基于平衡划分的并行集合交算法

对集合交运算,基于划分点定位算法提出并分析了一种新的并行算法INTERSECT-DL.在INTERSECT-DL算法中,数据被平衡地划分,分配给所有处理机,所以各处理机的工作负载相同.给出了在网络并行计算环境下的实验结果,并与INTERSECT-S、INTERSECT-NS算法进行了对比.理论分析和实验的结果都表明INTERSECT-DL算法具有很高的并行效率和扩展性.     

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

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

参数曲面的有限元网格化

基于推进波前法,本文提出了一种针对三维Trimmed参数曲面的有限元网格剖分方法,首先对曲面参数空间进行剖分,利用结点密度函数（与曲率有关）和生成内部结点的公式,使网格单元和结点能同时生成,然后把网格反映射到曲面上,从而实现参数曲面的三角形网格剖分。     

分布式网络爬虫的设计与实现

提出一种可部署于单一网域及多网域间的分布式爬虫DSpider。DSpider能够通过调整节点规模和连接超时阈值,有效部署于LAN和WAN两种网络环境中。首先简要介绍了DSpider的系统结构,然后详细分析了DSpider的任务调度策略,并且在实验中将DSpider爬虫部署在LAN和WAN两种环境中的不同性能作了详细的分析。     

求极大独立集的程序实现研究

独立集有着广泛的应用,尤其广泛应用于系统故障诊断领域。在求简单图极大独立集的程序实现方面,目前开展的研究工作还比较少。介绍简单图极大独立集的一种求取算法,剖析了该算法在使用面向对象程序设计模式中的实现方式,提出在定长字符串模式匹配中采用异或运算的运算法则来进行字符串模式匹配,由此作为多元式代数运算的基础对这个算法进行程序实现,并分析了这种字符串模式匹配的时间效率。     

Approximating minimum independent dominating sets in wireless networks

We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.     

Eliminating Cycles in the Discrete Torus

In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain?We look at two different edge structures for the discrete torus. For (? _m ^d )₁, where two vertices in ? _m are connected if their ? ₁ distance is 1, we show a nontrivial upper bound of \(d^{\log_{2}(3/2)}m^{d-1}\approx d^{0.6}m^{d-1}\) on the number of vertices that must be deleted. For (? _m ^d )_∞, where two vertices are connected if their ? _∞ distance is 1, Saks et al. (Combinatorica 24(3):525–530, 2004) already gave a nearly tight lower bound of d(m?1) ^d?1 using arguments involving linear algebra. We give a more elementary proof which improves the bound to m ^d ?(m?1) ^d , which is precisely tight.     

决策表属性约简的相对划分粒度表示

粗糙集理论认为知识就是分类.本文对知识的分类能力给予了量化,提出利用划分粒度来定量地表示知识的分类能力.在划分粒度概念基础上,针对决策表定义了相对划分粒度并研究了它的性质,相对划分粒度可以定量表示决策表的条件属性子集相对于决策属性的分类能力的强弱;最后证明了对一致决策表的属性约简来说,相对划分粒度表示与Pawlak提出的代数表示是等价的.     

无线自组网络中的消息最优的连通控制集

在无线自组网中,提出了一种虚拟骨干网连通控制集(connected dominating set)。然而,寻找最小连通控制集(minimum connected dominating set)是一个NP困难的问题。在很多文献中已经提出了计算最小连通控制集的近似算法,这些算法大都存在近似比很差、时间复杂度和消息复杂度高等问题。近年来,提出了一些新的构造连通控制集的分布式启发式算法。这些新的启发式算法基于生成树的构造,这使得在迁移和拓扑更改的情况下维护连通控制集的通信开销非常昂贵,会对整个网络的性能及生存时间产生影响。因此消息最优的连通控制集也就被提出。在保证构建消息最优的连通控制集的情况下,通过建立一种新的求解极大独立集的模型,考虑到圆不能密铺会造成一定的误差,通过使用正六边形来代替R为0.5的圆,从而求得了一个更为精确的三跳内极大独立集,改善了文献[16]中的结果,得到了更小的连通控集近似比,其值为143opt+33。     

无线传感器网络中基于网关的多级簇树维护更新算法

由于无线传感器网络节点的能量具有不可再生性,为了减小和均衡网络中各节点的能量损耗,要求把能效高放在首位,以尽可能的延长网络生存期。文中介绍一种利用图论中极大独立集和极小支配集的概念设计的基于能量的有网关的多级簇树EAMCT-G(Energy-Aware Multilevel Clustering Tree with Gateway)算法,并提出该算法的局部维护和更新算法,使得EAMCT-G算法具有可扩展性好和自恢复能力,最后通过仿真验证算法的有效性。