一种基于链暗示技术的Min-CVCB问题的精确算法

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku k1)|G| 1.26ku k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku k1)|G| 1.1892ku k1),极大地改进了目前的最好结果.     

无线网络中最小权虚拟骨干网连通部分的新方法

无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小。通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法。同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+ε)-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。     

内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。     

高维空间球集覆盖问题的改进1+ε近似算法

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。     

基于积极集策略的最小闭包球问题算法研究

首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法.对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε).然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点.将该策略结合到提出的算法中,得到一个基于积极集策略的算法.最后,实验结果表明基于积极集策略的算法能够快速、有效地求解m》n的大规模数据集的近似最小闭包球.     

一般图中的最小概要表示集问题

在一般图中,通常基于图的拓扑结构来刻画任意2个节点之间的相似度。基于节点相似度提出概要表示集SRS的概念,从图中寻找最少节点数的概要表示集称为最小概要表示集问题。证明了在一般图中求解最小概要表示集问题是NP (非确定性多项式)难的,不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概要表示集问题,得出近似比结果。     

带测度函数的连通支配集问题

连通支配集问题在网络广播上有着广泛的应用，本文引入测度函数的概念，提出了带测度函数的连通支配集问题（CDS（F）），使得它具有更广的应用范围。文中首先给出问题的形式定义，证明了它在各种情形下的NP完全性，并给出多项式时间的近似算法，它的近似度为Ln△＋3（△为图中顶点的最大度数）。     

一种可重构阵列的最小瑕点覆盖算法

关于可重构阵列的瑕点覆盖问题受到了很多文献的关注，特别地，关于可重构阵列的最小瑕点覆盖问题等价于二分图的受约束最小点覆盖问题，并被证明是NP-完全问题。针对本问题提出的算法运行时间为O(1．19^k kn)，这里k为可替换行与列的数目，改进了原有的最好结果，其运行时间为0(1．266k kn)，较好地组合并扩展了研究参数计算的最新技术与经典匹配理论，且具有较好的实用价值。这是关于可重构阵列的最小瑕点覆盖问题算法又一较大的改进，也是目前最小点覆盖问题相关参数算法的较有意义的改进。     

控制集与部分控制集问题的原始-对偶算法

图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为△＋1的近似算法（△为图中顶点最大度）。     

改进的最优顶点覆盖贪心边近似算法

最优顶点覆盖问题是6个基本的NP完全问题之一，无法在多项式时间内得到最优解，除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时，证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。     

Call for Papers The 6^th International Conference on Grid and Cooperative Computing

Recent years have seen rapid advances in various grid-related technologies, middleware, and applications. The GCC conference has become one of the largest scientific events worldwide in grid and cooperative computing. The 6th international conference on grid and cooperative computing (GCC2007) Sponsored by China Computer Federation (CCF),Institute of Computing Technology, Chinese Academy of Sciences (ICT) and Xinjiang University ,and in Cooperation with IEEE Computer Soceity ,is to be held from August 16 to 18, 2007 in Urumchi, Xinjiang, China.     

法律信息库系统

本文分析了法律数据库的结构和特点，介绍了采用面向对象设计方法和超文本数据库技术开发和实现法律信息库系统将作为重要网络资源之一为不同用户进行法律咨询服务。     

International Journal of Automation and Computing Table of Contents

正~~     

Information for authors

正SCIENCE CHINA Information Sciences(Sci China Inf Sci),cosponsored by the Chinese Academy of Sciences and the National Natural Science Foundation of China,and published by Science China Press,is committed to publishing highquality,original results of both basic and applied research in all areas of information sciences,including computer science and technology;systems science,control science and engineering(published in Issues with odd numbers);information and communication engineering;electronic science and technology(published in Issues with even numbers).Sci China Inf Sci is published monthly in both print and electronic forms.It is indexed by Academic OneFile,Astrophysics Data System(ADS),CSA,Cabells,Current Contents/Engineering,Computing and Technology,DBLP,Digital Mathematics Registry,Earthquake Engineering Abstracts,Engineering Index,Engineered Materials Abstracts,Gale,Google,INSPEC,Journal Citation Reports/Science Edition,Mathematical Reviews,OCLC,ProQuest,SCOPUS,Science Citation Index Expanded,Summon by Serial Solutions,VINITI,Zentralblatt MATH.     

Erratum to: Fast global kernel fuzzy c-means clustering algorithm for consonant/vowel segmentation of speech signal

正Erratum to:J Zhejiang Univ-Sci C(ComputElectron)2014 15(7):551-563doi:10.1631/jzus.C1300320The original version of this article unfortunately contained mistakes.Algorithm 6 should be as follows:Algorithm 6 FGKFCM-F clustering Input:(1)X={x_1,x_2,…,x_N},,x_iR~d,i=1,2,…,N,the dataset;(2)C,1C≤N,the number of clusters;(3)ε0,the stopping criterion;     

Journal of Zhejiang University-SCIENCE C (Computers & Electronics) Total contents

正~~     

磨机负荷专家控制系统设计及仿真研究

磨矿过程的大滞后和时变性等特点,致使对磨机负荷的最佳工作点很难进行稳定、高效的控制,针对以上情况,借鉴生物界的免疫反馈原理和遗传算法,利用模糊控制可以有效地实现对非线性、纯滞后、复杂的对象进行控制的优点,并结合PID与自寻优方法,设计出磨机负荷专家控制系统,用VB编写OPC客户端及控制程序,实现对磨机负荷的动态优化控制;试验结果表明,文章提出的控制策略能够增强系统的稳定性,且在干扰存在的情况下也能很好的跟随系统的参数变化,在提高磨机台时产量的同时增加了矿厂的经济效益.     

基于人工蜂群的无线传感器网络能耗均衡算法

由于无线传感器网络中的节点链路状况、数据传输能耗及节点剩余能量的限制,造成网络中部分感知节点寿命缩短,影响网络生存周期,提出了一种基于人工蜂群算法的WSNs能耗均衡算法,优化网络能耗均衡,从而提高网络寿命;文章给出了网络能耗相应的数学模型及优化求解算法,介绍人工蜂群算法的寻找食物过程,阐述了人工蜂群算法在网络能耗均衡方面的实现步骤;通过实验仿真证明,文章提到的算法与LEACH分簇算法、蚁群优化算法相比,具有更好的能耗和负载均衡能量、丢包率和时延性,有效地提高了网络生存周期.     

Thermodynamic modeling of the Al–Bi,Al–Sb,Mg–Al–Bi and Mg–Al–Sb systems

All available thermodynamic and phase diagram data of the binary Al–Bi and Al–Sb systems and ternary Mg–Al–Bi and Mg–Al–Sb systems were critically evaluated, and all reliable data were used simultaneously to obtain the best set of the model parameters for each ternary system. The Modified Quasichemical Model used for the liquid solution shows a high predictive capacity for the ternary systems. The ternary liquid miscibility gaps in the Mg–Al–Bi and Mg–Al–Sb systems resulting from the ordering behaviour of the liquid solutions can be well reproduced with one additional ternary parameter. Using the optimized model parameters, the experimentally unexplored portions of the Mg–Al–Bi and Mg–Al–Sb ternary phase diagrams were more reasonably predicted. All calculations were performed using the FactSage thermochemical software package.