资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k²)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k²). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.     

近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现

1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提     

边界追踪算法在地质储量计算中的应用

单井控制面积计算是油田开发中原始和剩余地质储量研究的基础。针对注采井网形成的平面变密度离散点集的边界搜索问题,本文提出以角度为判别标准,基于变搜索步长的滚边新算法进行井网边界的追踪。首先通过合理的搜索步长确定当前边界点的邻域,然后对邻域内的离散点按角度进行排序并确定下个合理边界点,最后在井网边界追踪的基础上,进一步给出储量边界外扩和单井控制面积计算方法。该算法简单、高效,可有效识别变密度平面点集的凸边界和凹边界特征,并在大庆油田的原始地质储量复算和剩余潜力评价中得到应用,提高工效5倍以上,表内地质储量复算精度2.7%,取得了很好的应用效果。     

基于DPSO的改进AO*算法在大型复杂电子系统最优序贯测试中的应用

针对大型复杂电子系统最优序贯测试问题,提出一种基于离散粒子群算法(DPSO)和改进AO~*算法相结合的方法.DPSO优化AO~*算法中每个要扩展节点的测试集从而减少测试个数;改进AO~*算法通过规定扩展节点估价值的范围,减少其回溯次数.实例验证表明,该算法不仅有效地降低了计算复杂度,大大减少测试代价,缩短测试时间,而且避免了原有AO~*算法当备选的测试集太大时容易出现"计算爆炸"的缺点.     

基于FLANN改进的KNN医疗分类算法

本文通过研究KNN（K-最近邻）算法在疾病预测领域的使用与分析,总结出KNN的2点不足,针对不足进行相应改进并提出F_KNN（循环最近邻搜索）算法：1）针对KNN计算量大、效率低下的缺点,本文采用FLANN（快速最近邻搜索）循环搜索与待测样本距离最近的点,记录若干个最近邻点作为最近邻点子集,利用此子集取代全集对待测样本进行计算,可以降低计算量,极大地提高了KNN算法效率;2）针对KNN难以对高维数据集分类的缺点,本文采用AHP（层次分析法）对样本的特征属性进行相关性研究,使用合适的参数分配权重,提高了KNN算法准确率。本文采用一组脑中风数据集对优化后的算法进行实验,实验结果表明,F_KNN准确率达96.2%。与传统KNN相比,F_KNN提高了分类性能且极大地提高了算法效率。在处理高维且较大的数据集时,F_KNN算法优势明显,具有较好的应用前景。     

基于K-means++的多视图点云配准技术

针对大规模点集可能存在噪声、离群点及遮挡等情况,提出一种基于K-means+〖KG-*3〗+的多视图点云配准方法。首先,利用K-means+〖KG-*3〗+算法的随机播种技术对下采样后的多视图点集选取初始化的质心,并根据算法的基本原理完成聚类;其次,将点云数据存入K-D树结构,并利用最近邻搜索算法建立点集间的对应关系,从而提升对应点集的搜索效率;最后,通过迭代最近点算法依照扫描顺序计算各视图聚类得到的点云数据与所有视图间的刚性变换参数,将成对配准造成的误差均匀扩散到每个视图中,直至获得最终配准结果。在Stanford三维点云数据集上进行实验的结果表明,本文提出的方法比近年的部分多视图配准算法具有更高的配准精度及鲁棒性。     

基于规范子块五点和的快速分形图像编码

分形图像编码通常需要较长的时间,编码时间主要花费于在一个海量码本中搜索每个输入子块的最佳匹配块.针对这个问题,提出一个限制搜索空间的算法.它主要基于图像块的一种新特征——五点和,把搜索范围限制在初始匹配块(五点和意义下与输入R块最接近的D块)的邻域内.实验表明:该算法能够大大减少子块匹配比较的数量,与基于叉迹的快速分形算法比较,在相同的搜索邻域内,在编码时间、图像质量和压缩比方面都更优.     

结合非空间属性的通用Skyline查询处理技术

Skyline查询作为多目标决策的重要手段之一,近年来在各个领域得到广泛的应用。提出了结合非空间属性的通用Skyline查询处理技术,采用R树对设施集及数据集建立索引,并提出了两种方法来计算Skyline。第一种是基于全最近邻算法的扩展,通过计算静态Skyline结果来裁剪部分数据集。另一种是基于渐进最近邻的算法,采用查询点导向的搜索方法,利用静态Skyline结果计算与每一类设施最远的距离,将其作为边界阈值对数据点集进行裁剪,采用数据点导向的搜索方法,为裁剪后的每一个数据点计算距其最近的设施,并将数据点与设施的距离映射到多维距离空间中,结合非空间属性进行Skyline计算。实验结果表明,第二种方法减少了I/O次数,降低了CPU执行时间,提高了计算效率。     

平面离散点集的边界搜索算法

进行有限元仿真首先要建立有限元网格模型。使用不含有任何拓扑信息的离散点集直接进行网格划分可以快速、精确地建立网格模型。使用铺路法进行网格剖分是从边界开始向内生成网格单元。该文提出一种使用搜索盒的搜索平面离散点集边界的算法。该方法将离散点分配到搜索盒中，遍历位于边界的搜索盒，将其中的点连接成边界点链表。该算法能正确地搜索包含有凹点、孔洞特征的离散点集的边界，具有较强的通用性。文中介绍了算法的基本思想，并给出算例。     

一种基于行列法离散点边界搜索算法*

平面上构建离散点的边界在地理信息系统(GIS)中应用广泛,提出了基于行列法的平面离散点边界搜索的新算法,目的是解决平面离散点边界问题,通过确定步长大小,按步长对离散点分别进行行搜索和列搜索,得到离散点的边界曲线,介绍了行列边界算法的基本思想和实现过程。该算法能够正确地搜索包含凹凸特征的离散点边界,与传统边界生成算法相比,它具有通用、实现简单等特点。该算法在油田GIS领域边界划分中得到了很好的应用,能够准确地构建油田边界。     

基于拍卖的虚拟机动态供应和分配算法

当前云计算供应商通过定价算法或类似拍卖的算法来分配他们的虚拟机（VM）实例。然而,这些算法大多要求虚拟机静态供应,无法准确预测用户需求,导致资源未得到充分利用。为此,提出了一种基于组合拍卖的虚拟机动态供应和分配算法,在做出虚拟机供应决策时考虑用户对虚拟机的需求。该算法将可用的计算资源看成是“流体”资源,且这些资源根据用户请求可分为不同数量、不同类型的虚拟机实例。然后可根据用户的估价决定分配策略,直到所有资源分配完毕。基于Parallel Workload Archive（并行工作负载存档）的真实工作负载数据进行了仿真实验,结果表明该方法可保证为云供应商带来更高收入,提高资源利用率。     

以自动化码头为中心的船舶配载优化

针对自动化码头船舶配载效率较低的问题,为了提高设备资源利用率,提出了一种基于船舶配载特点设计的固定集搜索（FSS）算法。首先,在考虑一般船舶配载原则的基础上,以桥吊作业计划为依据,引入箱区作业均衡因素,将最小化箱区翻箱量、总装船时间以及尽可能的箱区作业均衡作为目标,建立自动化码头船舶配载混合整数规划模型;其次,通过固定较优解中多次出现的元素来寻求最优解。实验结果表明,不同规模的实例下,FSS算法相较于Cplex,翻箱量和不均衡箱数分别平均减少了22.3%和11.7%,目标函数值平均优化了6.5%;所提固定集搜索算法与粒子群优化（PSO）算法、遗传算法（GA）和蚁群优化（PSO）算法相比,目标函数值平均优化了2.1%,凸显了FSS算法更高的配载效率。而为了增加案例的多样性,对箱区堆栈分布和比例进行了调整。在这个情况下,FSS算法的不均衡箱数相较上述三种算法平均减少了19.3%,设备资源利用率更高。     

基于负载均衡的无线虚拟网络映射算法

针对网络僵化的问题,目前多采用网络虚拟化（NV）方法进行解决,其关键技术是虚拟网络映射（VNE）。为解决无线VNE过程中功率和带宽资源使用不均衡的问题,基于负载均衡原理提出一种联合资源分级的无线VNE算法。首先,采用新的节点资源排序方式,其中将节点功率和平均链路带宽作为排序依据;其次,对资源进行分级,以动态调整虚拟网络请求对功率和带宽资源的需求;最后,改进功率和带宽资源的单位成本,并以最小化成本为目标函数选择资源分配方案。与原有的无线VNE算法WVNE-JBP相比,所提算法的总体接受率提高了11.7个百分点,平均功率利用率提高了4.4个百分点,平均带宽利用率提高了1.6个百分点。实验结果表明,所提算法能有效提高虚拟网络接受率和资源利用率。     

从不确定数据集中挖掘频繁Co-location模式

把挖掘频繁co-location模式的经典算法Join-based算法扩展到了UJoin-based算法,解决了从不确定数据集中挖掘频繁co-location模式的问题。针对UJoin-based算法中ED(expected distances)计算开销大的问题,介绍了两种剪枝技术:边界矩形剪枝技术和三角不等式剪枝技术,其中,在三角不等式剪枝部分,分别讨论了取1个锚点、5个锚点和9个锚点的不同情况。通过大量实验证明了剪枝策略有效避免了大量的ED计算,提高了算法的效率。     

基于八叉树的三维地质剖面生成算法

针对目前构建三维地质剖面算法复杂度高、效率低的问题,提出一种基于八叉树的三维地质剖面生成算法。利用八叉树算法对传统的地质剖面生成算法进行改进,使算法在搜索过程中的时间复杂度降低至O(log8(n/M)),在算法中加入轮廓边约束,对搜索到的边进行预处理,以保证边的正确性和有序性。采用八叉树为复杂三维地质体网格模型内的三角形创建空间索引,通过八叉树快速查找出经过剖面的三角形,计算交点并追踪出轮廓边界,通过画廊看守算法对追踪出的边界三角化并构建三维剖面。实验结果表明,该算法具有复杂度低、鲁棒性强的特点,与传统的地质剖面生成算法相比,时间复杂度由O(n2)降低到O(nlbn)。     

基于功率控制的多节点协同目标跟踪算法

为适应资源有限的无线传感器网络节点的目标跟踪需求,并在保证跟踪性能的同时降低算法复杂度,提出一种功率控制和多节点协调(PC&MC)目标跟踪算法.借鉴Rao-Blackwellized技术,实现多节点协同作业以保证对动态目标的跟踪精度,采用基于连续/离散混合模型的准高斯粒子滤波器完成对目标的跟踪,在跟踪过程中使用功率控制...     

一种面向在线查询的拼写纠错算法

搜索引擎中,在线拼写纠错根据用户查询输入补全用户查询,并给出正确的拼写建议。提出了一种面向查询补全的在线拼写纠错算法。基于真实查询的噪声信道转换方式,算法建立了用户查询输入的生成模型;利用拼写纠错对,算法采用期望最大化算法训练能捕获用户误拼行为的马尔科夫N语法转换模型;算法采用不同剪枝策略的启发式改进A*搜索算法以实现实时给出纠错补全建议。实验结果表明,提出的算法相比其他同类算法更有效。     

A resource selection scheme for QoS satisfaction and load balancing in ad hoc grid

Ad hoc grids are highly heterogeneous and dynamic, in which the availability of resources and tasks may change at any time. The paper proposes a utility based resource selection scheme for QoS satisfaction and load balancing in ad hoc grid environments. The proposed scheme intends to maximize the QoS satisfaction of ad hoc grid users and support load balancing of grid resources. For each candidate ad hoc grid resource, the scheme obtains values from the computations of utility function for QoS satisfaction and benefit maximization game for ad hoc grid resource preference. The utility function for QoS satisfaction computes the utility value based on the satisfaction of QoS requirements of the grid user request. The benefit maximization game for grid resource node preference computes the preference value from the resource point of view. Its main goal is to achieve load balancing and decrease the number of resource selection failure. The utility value and the preference value of each candidate ad hoc grid resource are combined to select the most suitable grid resource for ad hoc grid user request. In the simulation, the performance evaluation of proposed algorithm for ad hoc grid is conducted.     

一种新型的LTE系统干扰协调算法

为了解决LTE多小区系统在重度边缘负载情况下所承受的严重的小区间干扰问题,提出了一种基于小区边缘用户数的干扰协调调度算法ICPF。该算法在软频率复用干扰协调场景下提出了改进型资源分配以及二次调度思想,在初步分配资源的基础上进行频率资源二次调整,并有效地与调度算法结合起来。仿真结果表明,ICPF算法能在保证频谱利用率的前提下,提高小区边缘用户性能以及多用户分集的效果。