k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设dmax/dmin表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明dmax/dmin≤ω+ε+(的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(NOlog logn)).然后给出k-Median问题的一个局部搜索算法,分析表明,若有dmax/dmin≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

合取范式3可满足问题的局部搜索近似算法

合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k≥4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k≥4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.     

k-median问题反向贪心随机算法

k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。     

多服务中心设置问题局部搜索算法的分析与实验

讨论了多服务中心设置问题的局部搜索近似算法及其在实际计算中表现出的新性质。首先对局部搜索算法求解多服务中心设置问题的实际近似性能比给出了一个针对性分析结果,然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

短块移动排序的14/11近似算法

块移动是基因重组的一种重要形式.短块移动是将排列中的元素最多移动到偏离原来两个位置的块移动.Heath和Vergara最先给出短块移动排序近似度为4/3的多项式时间算法.本文设计了近似性能比为14/11的短块移动排序新算法.首先讨论了具有伞形结构排列图的子排列的排序方法,并将这种子排列称为‘伞’,设计了特殊子排列伞短块移动排序的多项式时间精确算法.然后给出关联伞子排列短块移动排序的贪心算法.讨论了5种特殊子排列的短块移动排序方法,证明了它们短块移动距离的新下界,从而证明此贪心算法的近似性能比为14/11,这是目前解答短块移动排序问题近似性能比最小的多项式近似算法.     

基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。     

K-median问题贪心近似算法的分析与实验

讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法,证明该算法的近似度为O(ln(n/k)),通过实验证明该贪心算法在实际应用当中可以取得较好的效果,大约有90%的客户能被距离其最近、次近和第三近的设备服务。     

European Community policy and the market

Abstract This paper starts with some reflections on the policy considerations and priorities which are shaping European Commission (EC) research programmes. Then it attempts to position the current projects which seek to capitalise on information and communications technologies for learning in relation to these priorities and the apparent realities of the marketplace. It concludes that while there are grounds to be optimistic about the contribution EC programmes can make to the efficiency and standard of education and training, they are still too technology driven.     

一种自适应子融合集成多分类器方法

融合集成方法已经广泛应用在模式识别领域,然而一些基分类器实时性能稳定性较差,导致多分类器融合性能差,针对上述问题本文提出了一种新的基于多分类器的子融合集成分类器系统。该方法考虑在度量层融合层次之上通过对各类基多分类器进行动态选择,票数最多的类别作为融合系统中对特征向量识别的类别,构成一种新的自适应子融合集成分类器方法。实验表明,该方法比传统的分类器以及分类融合方法识别准确率明显更高,具有更好的鲁棒性。     

Explanation and prediction: an architecture for default and abductive reasoning

Although there are many arguments that logic is an appropriate tool for artificial intelligence, there has been a perceived problem with the monotonicity of classical logic. This paper elaborates on the idea that reasoning should be viewed as theory formation where logic tells us the consequences of our assumptions. The two activities of predicting what is expected to be true and explaining observations are considered in a simple theory formation framework. Properties of each activity are discussed, along with a number of proposals as to what should be predicted or accepted as reasonable explanations. An architecture is proposed to combine explanation and prediction into one coherent framework. Algorithms used to implement the system as well as examples from a running implementation are given.     

Three Process Perspectives: Organizations, Teams, and People

This paper provides the author's personal views and perspectives on software process improvement. Starting with his first work on technology assessment in IBM over 20 years ago, Watts Humphrey describes the process improvement work he has been directly involved in. This includes the development of the early process assessment methods, the original design of the CMM, and the introduction of the Personal Software Process (PSP)^SM and Team Software Process (TSP){^SM}. In addition to describing the original motivation for this work, the author also reviews many of the problems he and his associates encountered and why they solved them the way they did. He also comments on the outstanding issues and likely directions for future work. Finally, this work has built on the experiences and contributions of many people. Mr. Humphrey only describes work that he was personally involved in and he names many of the key contributors. However, so many people have been involved in this work that a full list of the important participants would be impractical.     

基于复小波噪声方差显著修正的SAR图像去噪

提出了一种基于复小波域统计建模与噪声方差估计显著性修正相结合的合成孔径雷达(Synthetic Aperture Radar,SAR)图像斑点噪声滤波方法。该方法首先通过对数变换将乘性噪声模型转化为加性噪声模型,然后对变换后的图像进行双树复小波变换(Dualtree Complex Wavelet Transform,DCWT),并对复数小波系数的统计分布进行建模。在此先验分布的基础上,通过运用贝叶斯估计方法从含噪系数中恢复原始系数,达到滤除噪声的目的。实验结果表明该方法在去除噪声的同时保留了图像的细节信息,取得了很好的降噪效果。     

How do children do mathematics with LOGO?

Abstract  This paper considers some results of a study designed to investigate the kinds of mathematical activity undertaken by children (aged between 8 and 11) as they learned to program in LOGO. A model of learning modes is proposed, which attempts to describe the ways in which children used and acquired understanding of the programming/mathematical concepts involved. The remainder of the paper is concerned with discussing the validity and limitations of the model, and its implications for further research and curriculum development.     

Editorial: Special issue on recent advances in hybrid control theory and applications

正The demands of a rapidly advancing technology for faster and more accurate controllers have always had a strong influence on the progress of automatic control theory.In recent years control problems have been arising with increasing frequency in widely different areas,which cannot be addressed using conventional control techniques.The principal reason for this is the fact that a highly competitive economy is forcing systems to operate in regimes where     

Information for Authors

正Aim The Journals of Zhejiang University-SCIENCE(A/B/C)areedited by the international board of distinguished Chinese andforeign scientists,and are aimed to present the latest devel-opments and achievements in scientific research in China andoverseas to the world’s scientific circles,especially to stimulateand promote academic exchange between Chinese and for-eign scientists everywhere.     

Enhancing a leaf radiative transfer model to estimate concentrations and in vivo specific absorption coefficients of total carotenoids and chlorophylls a and b from single-needle reflectance and transmittance

The relative concentrations of different pigments within a leaf have significant physiological and spectral consequences. Photosynthesis, light use efficiency, mass and energy exchange, and stress response are dependent on relationships among an ensemble of pigments. This ensemble also determines the visible characteristics of a leaf, which can be measured remotely and used to quantify leaf biochemistry and structure. But current remote sensing approaches are limited in their ability to resolve individual pigments. This paper focuses on the incorporation of three pigments—chlorophyll a, chlorophyll b, and total carotenoids—into the LIBERTY leaf radiative transfer model to better understand relationships between leaf biochemical, biophysical, and spectral properties.Pinus ponderosa and Pinus jeffreyi needles were collected from three sites in the California Sierra Nevada. Hemispheric single-leaf visible reflectance and transmittance and concentrations of chlorophylls a and b and total carotenoids of fresh needles were measured. These data were input to the enhanced LIBERTY model to estimate optical and biochemical properties of pine needles. The enhanced model successfully estimated reflectance (RMSE = 0.0255, BIAS = 0.00477, RMS%E = 16.7%), had variable success estimating transmittance (RMSE = 0.0442, BIAS = 0.0294, RMS%E = 181%), and generated very good estimates of carotenoid concentrations (RMSE = 2.48 µg/cm², BIAS = 0.143 µg/cm², RMS%E = 20.4%), good estimates of chlorophyll a concentrations (RMSE = 10.7 µg/cm², BIAS = − 0.992 µg/cm², RMS%E = 21.1%), and fair estimates of chlorophyll b concentrations (RMSE = 7.49 µg/cm², BIAS = − 2.12 µg/cm², RMS%E = 43.7%). Overall root mean squared errors of reflectance, transmittance, and pigment concentration estimates were lower for the three-pigment model than for the single-pigment model. The algorithm to estimate three in vivo specific absorption coefficients is robust, although estimated values are distorted by inconsistencies in model biophysics. The capacity to invert the model from single-leaf reflectance and transmittance was added to the model so it could be coupled with vegetation canopy models to estimate canopy biochemistry from remotely sensed data.     

Mr. Twinn’s bombes

This article discusses the history and design of the special versions of the bombe key-finding machines used by Britain’s Government Code & Cypher School (GC&CS) during World War II to attack the Enigma traffic of the Abwehr (the German military intelligence service). These special bombes were based on the design of their more numerous counterparts used against the traffic of the German armed services, but differed from them in important ways that highlight the adaptability of the British bombe design, and the power and flexibility of the diagonal board. Also discussed are the changes in the Abwehr indicating system that drove the development of these machines, the ingenious ways in which they were used, and some related developments involving the bombes used by the U.S. Navy’s cryptanalytic unit (OP-20-G).