多目标MIN-MAX度最小树问题及其求解

在多目标最小生成树问题和MIN-MAX度最小树问题的基础上,探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质,在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同,当网络图不存在Hamilton路时,引入改进的蚁群优化算法,将转移概率由基本的指数形式改进为线性形式,在不影响求解质量的前提下,提高计算效率。针对以上策略,设计了相应的求解方案,并在计算机上用Delphi编程实现。大量数值算例验证表明,算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。

曙光5000高性能计算机Barrier网络的设计

为优化Barrier操作的性能,提高大规模并行计算应用在曙光5000系统中的执行效率,文中提出了一种基于硬件的Barrier加速设计.该设计是采用树形Barrier算法,通过增强曙光5000互联网络交换芯片的功能,实现低延迟、可扩展、高可靠和可管理的Barrier网络.该网络支持并发16个Barrier操作,可在Fat-Tree拓扑环境下实现较低的Barrier操作延迟.相比已有实现,是更适合Fat-Tree拓扑的设计方案.理想情况下,1024个节点的同步操作在1.7μs内完成.根据Barrier操作归约和分发过程的特点,分别采用请求应答和超时催促两种机制,为Barrier操作的可靠性提供保障.以该设计实现的Barrier网络原型系统已通过FPGA验证.

一种新颖的基于模糊信息融合的目标空间分布结构检测算法

该文提出一种基于模糊信息融合的目标空间分布结构探测算法,文中称之为S-Prim(SpatialPrim)算法,它是融合了模糊空间关系信息的受限Prim算法,用于识别具有规则空间分布关系的目标斑点集合。在很多情况下,目标之间会呈现出有规则的阵列分布关系。为检测这类关系,S-Prim算法将子目标相互之间的空间分布关系、距离关系,以及特征属性关系进行模糊信息融合,借助Prim算法生成最小支撑树的机制,评估邻近节点之间可能具备的某些有规则的空间分布关系,主动探测子目标之间可能存在的空间分布规律,并识别目标群。实验证明,该算法稳定有效。

一个利用小顶堆构造哈夫曼树的C++算法

在研究了现有的一些算法的基础上,提出了一种新的构造哈夫曼树的C++算法。巧妙地运用了小顶堆的特点,以哈夫曼树的结点权值和结点指针组成的结构为小顶堆的数据元素,最初在小顶堆存放由叶子结点构成的若干个哈夫曼树的根结点的地址指针和作为关键值的权值,然后不断从小顶堆中取出一对权值最小的哈夫曼树的根结点指针,构造出这两个结点的双亲结点,并将双亲结点信息插入到小顶堆中。这种取出和插入的操作循环往复,直到构造出一棵独立的哈夫曼树为止。这一算法构思巧妙,简洁明快,具有很好的实际应用价值。

基于最小Steiner树的无线传感器网络数据融合算法

能源有效性是无线传感器网络(WSN)路由算法设计首要考虑的问题,可以通过数据融合合并冗余数据而有效地节约网络能耗。WSN数据融合可以看作是寻找覆盖源节点和Sink节点的最小Steiner树(MST)问题。文章提出了一种MAX-MIN蚂蚁系统算法和自适应蚁群系统算法相结合的MST构造算法(MMACS),在此基础上,提出了一种基于MST的WSN数据融合算法(DAMST),该算法采用定向扩散的机制进行兴趣散布;利用MMACS算法构造MST,源节点的数据发送到构造好的MST上,经过融合后传输到Sink节点,减少了网络中传输的数据量。通过与其它算法比较,仿真表明DAMST算法降低了网络总能耗和平均时延,延长了网络生存时间。

闽语中早于中古音的音韵特点及其历时含义

文章对闽语中早于中古音的音韵特点做了进一步的研究。首先分析闽语中六个早于中古音的音韵特点,即:(1)中古昔韵和药韵的表现;(2)中古先屑韵的表现;(3)中古麻韵二等的表现;(4)上古唇化元音的残余;(5)中古书母的表现;(6)中古来母的音值。文章还探讨了这些音韵特点的历时含义。内容包括:(1)“闽语除外假说”和闽语的定义;(2)闽语和吴语处衢片之间的谱系关系;(3)闽语在上古音构拟上所起到的作用。

民猪全基因组序列测定与分析

民猪是我国优良地方猪品种,具有高繁殖、耐粗饲、抗逆和肉质优良等特性,但遗传背景模糊。为合理保护和利用民猪资源,利用Illumina Hiseq2000测序平台,采用双末端测序方法,测定10头民猪和4头东北野猪全基因组序列,统计分析SNPs和InDel标记信息,利用NCBI数据库中已知的50个不同个体的SNPs信息作主成分分析并构建分子进化树,使用θπ和Fst两个参数筛选民猪和东北野猪基因组内受选择基因。结果表明,民猪基因组内检测8 255 874个SNPs,大量的SNPs发生在基因间区及内含子区;与猪dbSNP数据库相比,新发现7 739 173个SNPs;检测到739 647个InDel位点,其中纯合多于杂合位点。民猪在遗传距离上介于亚洲猪种和欧洲猪种之间,说明民猪在品种形成过程中,曾引入欧洲猪血统,东北野猪则与亚洲家猪和亚洲野猪聚为一类,符合其地理分布。民猪基因组内共181个基因受到选择,涉及能量代谢、脂质转运、脊椎及视神经发育等。东北野猪基因组内共411个基因受到选择,涉及神经系统、免疫应答、繁殖、线粒体能量代谢等。

决策树技术在电信行业客户流失分析中的应用

研究决策树技术,对建立决策树的具体过程进行了分析,并利用决策树技术进行客户流失分析,建立客户离网预测模型,分析哪些客户的离网概率最大及其相关因素,为市场经营与决策人员制订相应的策略、留住相应的客户提供决策依据.

《齐民要术》中的蔬菜果树栽培技术研究

成书于6世纪初的《齐民要术》是我国悠久农业史中承前继后的一部划时代经典著作。书中介绍了精耕细作的蔬菜栽培技术,如重视选地、整地、做畦、浇水和施肥的基础运作,强调选种、适播期和田间管理,提高复种指数和土地利用率等。书中还对果树栽培管理技术经验作了梳理。

一种基于模糊信息融合的Prim算法及应用

提出一种融合多元模糊空间关系信息的支撑树搜索算法,即S Prim(spatialPrim)算法,用以识别低分辨率环境下(红外、多光谱遥感、SAR、恒星导航等图像中)具有规则空间分布关系的目标斑点集合。S Prim算法将子目标相互之间的空间分布关系、距离关系,以及目标自身属性关系进行模糊信息融合,借助Prim算法生成最小支撑树的机制,评估邻近节点之间可能具备的某些有规则的空间分布关系,主动探测子目标之间可能存在的空间分布规律,从而识别目标群。实验证明,该算法稳定有效。

基于生成树的回路核

针对图的相似性问题,提出了基于生成树的回路核,其中包括基于最小生成树的回路核、基于最大生成树的回路核、基于最小生成树或最大生成树的回路核、基于最小生成树与最大生成树的回路核、基于混合生成树的回路核、基于赋权混合生成树的回路核.结果表明,所定义的基于生成树的回路核是可计算的、正定的;在实验中,回路核的识别率高于通路核的识别率,最高可达100%.

几类特殊图中的最小最大多路割

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了(2-21k2)-近似算法,k表示终端的数目。

一个描述内存工作区操作的公理语义方法

本文定义了一个内存工作区处理语言ＭＰＬ，并提出用于描述该语言的形式化方法．作为示例，文中最后给出一个程序部分正确性的验证提纲．

串并联双机器人系统任务分配的蚁群优化

针对一种新型串并联双机器人联合作业系统的任务分配进行方法设计和整体优化。分别采用蚁群优化中的近似非确定性树搜索(Approximate nondeterministic tree search,ANTS)和最大最小蚂蚁系统(Max-min-ant-system,MMAS)作为任务分配的优化策略,并在MMAS中加入局部搜索以进一步优化路径构建过程中得到的局部最优解。仿真结果以及与之前相关研究成果的对比表明,MMAS在寻优过程中的迭代收敛速度优于ANTS,且经过一段时间的开发探索之后,获得的最优解的质量也比ANTS要好;MMAS与局部搜索相结合的方法比单独使用MMAS更加进一步提高了最终解的质量。进化曲线证明了算法对系统任务分配及优化的适应性和优越性。试验结果经与传统组合优化方法对比,进一步验证了算法的优化效果。

位置敏感的社交网中最小种集选取算法研究

最小种子集合选取问题(J-MIN-Seed问题)的目标是选择一个种子集合S,在影响传播结束后,它不仅需要影响一定数量的用户(如J个用户),同时S是最小的集合.虽然该问题得到了广泛的研究,但是现有工作却忽略了一个重要事实,即地理位置信息对于J-MIN-Seed问题是非常重要的.在许多真实的应用中,例如位置敏感的口碑营销,都有地理位置的需求.因此,该文将地理位置因素融入到J-MIN-Seed问题中,提出了位置敏感的J-MINSeed问题,并证明了该问题是NP-hard问题.该问题的一个挑战是如何高效且有效地计算给定区域的影响范围.为了解决这个挑战,该文对现有的树模型进行扩展,设计出一种高效且有效的近似模型.基于此模型,该文首先提出了朴素的贪心算法MS-Greedy.MS-Greedy虽然有近似保证,但其计算量太大.为满足在线查询的需求,该文又提出了另外两种高效的算法Bound-based和Partition-Assembly-based.大量真实数据的实验结果表明:文中算法能有效地解决位置敏感的J-MIN-Seed问题.

风电场集电线路自动规划算法研究与应用

借鉴人工设计思想,提出了一种多维度约束动态规划方法。全面综合考虑集电线路设计过程中遇到的各种实际问题,包括快速子区域聚类划分、可行路径获取、三维路径规划、考虑电缆载流量经济最优拓扑、子区域间交互,算法运行过程中进行多次降阶,极大地缩短规划时间。最后,通过1个实际案例,进行人工规划和自寻优算法运行结果对比,表明了所提算法的快速有效性。

利用最小填充树分解方法实现最短路径查询

随着社会的快速发展,道路网的规模越来越大,传统的最短路径算法已不能满足当前的实时要求,本文将基于最小度的树分解查询算法扩展至有向有权图中,提出了效果更好的基于最小填充的树分解最短路径查询算法,并对查询算法求解集合的过程进行了优化,实验结果表明,随着数据规模的增长,算法的时间效率相对于采用二叉堆的Dijkstra算法得到数量级提高。

一个改进的调配算法

图中路径的基本优化策略有两种最短路径和最大权值最小路径。前者的求解有著名的Dijkstra算法;后者的求解通过先构造图的最小生成树MST,再截取其上两端点间的唯一路径就是最大权值最小路径。但是,尚未有文献提出算法同时争取两方面的优化。本文采用Dijkstra算法构造路径时不断递增的基本思想,提出MSPT算法。MSPT算法是在求得最短路径的同时最大限度地争取最大权值最小。其算法时间复杂度和空间复杂度均与Dijkstra算法相同,但比Dijkstra算法横向上增加了一层优化,更切合实际问题的需要。同时,该文给出了MSPT算法的实际应用模型。

太原唐代郭行墓“堕甑”图考略

太原唐代郭行墓东壁两幅树下人物屏风,构成了一个完整的画面。画面中“破碎的陶罐”是解读其内容的关键线索,这应是孟敏“堕甑不顾”的故事。此故事之所以被画在太原唐墓屏风中,既与孟敏洒脱大度,属于高士一类人物有关,也可能是此事发生在太原,为当地人所熟知的缘故。

基于分区的部分最值查询优化算法

大规模数据库的建立和海量数据的不断涌现,需要从海量数据库和大量繁杂信息中提取有价值的知识,可以进一步提高网络安全信息的利用率.另一方面,网络信息安全分析在面临海量数据时,其查询效率会大大降低.分区技术使用户可以将大表分解为更小且更易管理的分区,从而解决海量数据带来的一些问题.本文讨论了分区条件下部分最值的查询方法,介绍了一种用于提高这种查询效率的RBP-T(rank bisection partition tree)树型结构,并给出了相应的搜索算法.通过实验证明,我们的方法对解决海量数据情况下的部分最值查询问题是有效的.