一般设施定位问题计算复杂度和近似算法研究

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243 0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1 ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.     

神经网络求解图最短路径问题的一种新方法

本文给出一种求解图最短路径问题的实用反馈式神经网络，并证明这两种网络的求解稳定性，这种网络基于最小值选择网而构成，对任意有向图和无向图均能收敛到其唯一的稳定点，由此求得图所有顶点对间的最短路径及最短路径长度，本文结果是神经网络求解非ＮＰ－骓难解类优化问题的一种新尝试。     

k-means聚类问题的改进近似算法

研究了Ostrovsky给出k-means问题的（1＋ε）-近似算法,针对算法中取样参数小的以及枚举数量大的不足,证明了可以选择一个更大的取样参数减小取样点集,基于随机算法,提出新的枚举策略减少枚举数量。本文分析了算法的成功概率。改进算法的期望时间复杂度为O（2O（kα2/ε）dn）,其中d、n分别为问题实例的空间维数和输入点个数,α是小于1的分隔系数。算法的成功概率为121-e-21εk（1-O（α））。与Ostrovsky给出的算法相比,算法的运算效率得到很大的提高。     

金属矿山深部巷道稳定性测试与分析

深部高地应力条件下巷道所处的应力环境复杂、岩石变形破坏加剧,准确的测定巷道松动圈范围是确定合理支护参数的重要依据。通过数值模拟对金川二矿区深部巷道松动圈范围的计算结果表明,金川矿区深部巷道松动圈范围较大的区域主要分布在巷道左侧帮和底板,深度达到1.5m-2.95m。现场测试结果也表明,巷道两帮和底板松动圈范围较大,其深度为1.1m-2.85m,数值模拟结果与现场测试结果吻合较好。同时说明,金川矿区当前所采用的锚杆长度已无法满足深部巷道支护的需要,应在巷道松动圈测定的基础上对深部巷道的支护参数进行优化,采取更加科学有效的支护措施。     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

（19期已排版）基于无迹卡尔曼滤波的行波波头辨识

行波测距的关键问题是行波到达时刻的准确标定。然而系统在过零点发生故障或者经高阻接地短路时,故障行波信号比较微弱,利用奇异性判断行波突变的方法会出现很大的误差。为了准确捕捉故障暂态行波,文中提出了一种新的行波辨识方法,通过分析行波传输特性,构建行波波头数学模型,利用无迹卡尔曼滤波的状态估计能力,对行波波头进行辨识,从而获得行波到达故障检测装置的时刻。仿真结果可以看出,在信噪比较低的情况下,该方法依然能够辨识行波波头,具有很好的工程实用性。     

基于最小聚类求解k-means问题算法

针对每个划分子集要求至少满足一定数量点的k-means问题,设计了该问题的随机近似算法.给出一个样本子集,证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点,进一步设计近似度为2的随机算法.设计了该问题的(1+ε)随机近似算法,算法的成功概率至少为3/2k+2.利用取样技术,设计了k-means问题的局部搜索随机算法.     

一类排污问题在树图上的线性算法

ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案．     

一种并行计算K阶线性递归N方程组的新方法

一种并行计算Ｋ阶线性递归Ｎ方程组的新方法朱大铭，马绍汉，马军（山东大学计算机科学系、济南２５０１００）ＡＮＥＷＭＥＴＨＯＤＦＯＲＳＯＬＶＩＮＧＴＨＥＳＹＳＴＥＭＯＦＫ－ＴＨＯＲＤＥＲＬＩＮＥＡＲＲＥＣＵＲＲＥＮＣＥＥＱＵＡＴＩＯＮＳＩＮＰＡＲＡＬＬＥ...     

并联电容器极壳之间交流耐压试验噪声问题探讨

叙述了并联电容器极壳之间进行交流耐压试验时出现的噪声现象,针对这些异常噪声产生的原因进行了分析,并对并联电容器进行极壳间交流耐压试验的施加电压回路进行了说明;并从电容器的原材料质量和制作工艺控制方面提出了改进措施以避免这种噪声的产生;指出了只有减小并联电容器的局放才是消除这些异常噪声的关键.