直角多边形布图区域内的二次布局算法

提出了一种直角多边形布图区域内的基于动态划分的二次布局算法——DPRR．通过在传统的二次布局算法中引入一种新的圆盘划分和分布约束生成策略,解决了直角多边形布图区域里的单元布局问题,并且由于该算法在迭代优化过程中动态地划分电路并生成分布约束,且不限制单元在布图区域的不同部分间自由移动,所以它可以在一定程度上避免优化过程中出现的“局部最优”,从而达到更高的布局质量．对一些电路实例的测试和比较结果也证明DPRR是一种高效优良的布局算法,并且它十分适用于解决非矩形的直角多边形布图区域内的标准单元布局问题．     

基于AutoCAD的简单多边形剖分算法

在充分挖掘AutoCAD图形中简单多边形自身隐含的垂直与共线关系的基础上,提出一种新的基于直角顶点判定和凹凸顶点判定的简单多边形剖分算法。该算法首先判断出多边形顶点的直角特性和凹凸性,然后根据多边形自身的特点按照一定的先后次序进行剖分,力求把多边形分割成直角梯形、矩形和直角三角形的形式。其中判断辅助线连接次序的优先级是实现剖分算法的关键。程序实现中采用递归算法,对分割后的多边形重新进行判断,直到多边形分割完毕。     

基于曲率匹配和递归排序的自适应排样算法

为提高盘状毛坯的使用率,提出一种口腔修复加工中模型边界在盘状毛坯中的排样算法,主要包括边界匹配、多边形定位及递归排序.首先基于协方差矩阵及矩阵SVD分解算法对模型多边形进行分段,并采用等弧长曲线采样曲率匹配确定待匹配模型边界;然后依毛坯边界角度分布及沿圆周排样的思想确定模型轮廓的旋转和平移定位;最后提出一种基于包络率的递归排序算法,对在排样过程中发现的大孔洞可动态地调整排样顺序.实验结果表明,该算法可以处理不规则模型边界在任意形状毛坯中的排样,能有效地降低加工成本.     

四元数球面Bézier样条插补算法的研究

为了简化五轴CNC数控系统中的刀具定向运动的编程工作,提出一种基于四元数球面Bézier样条插补算法.该算法根据建立的刀具运动的空间数学模型,实时插补计算出刀具路径点和刀具定向矢量.实验结果表明,该算法不仅保证了刀具平移运动和旋转运动的同步协调性,而且有效的提高了加工精度,满足了五轴高速高精的加工要求.     

允许自由旋转的2个简单多边形匹配算法

为了解决二维不规则排料问题中的匹配问题,提出了一种允许自由旋转条件下,2个无孔洞的简单多边形之间的匹配算法.该算法基于2个多边形可以自由旋转的假设,对它们之间NFP为凹或凸的情况,选择适当的匹配方法,找出一种使得其匹配后空隙尽可能小,同时保证其整体的矩形的规整度也较高的匹配方案;并用匹配空隙的利用率、匹配后整体面积的利用率,以及匹配后整体的矩形规整度等多个指标来衡量匹配的效果.实验选择于ESICUP中的部分代表性的多边形样例与多个算法进行对比实验,结果表明,该算法在任意旋转精度的要求下,均具有运行速度快的特点,可以很好地应用于服装排料等实际问题.     

基于解开操作的直角多边形随机生成算法

集成电路物理设计的测试需随机生成直角多边形以覆盖所有的情况。基于此,提出一种基于解开操作的直角多边形随机生成算法,可应用于超大规模集成电路物理设计算法的测试和分析。该算法随机生成一个点序列,逐一将每对相交的线段解开,直至找不到任何相交线段。对该算法的有穷性作出证明,并以实验证明该算法简单有效。     

复杂曲面加工精度检验中曲面法矢与刀具扫描体求交算法的研究

提出了一种用于实现矢量与扫描体（代表五轴数控加工铣刀的运动）求交的有效算法,该算法首先对曲面法矢和刀具扫描体进行预处理,将曲面法矢与刀具扫描体之间的求交问题转化为有向线段与三角网格之间的求交计算,然后建立有向线段和三角网格的求交子集,减少了不必要的求交计算,提高了乍法的效率。文中举例说明了该算法在复杂曲面NC精度检验中的应用。     

面向三维重建的加工基准匹配技术研究

基于加工基准的匹配是制造毛坯动态演变序列三维模型重建过程中的关键点,在前驱三维工序模型投影视图与当前工序图已关联的前提下,通过分析加工基准的类型和特点,结合二维工序图表达形式,提出加工基准的获取方式及基准三元图形这一概念,同时结合这个概念介绍了加工基准匹配算法.最后通过实例验证该算法的可行性和有效性.     

基于强化学习的遗传算法求解一种新的钻削路径优化问题

孔加工是机械制造的基本工序之一.针对数控机床的刀具路径优化问题,提出一种新颖的孔加工刀具路径优化模型-----带可决策孔的孔加工多刀具路径优化问题(MTdDPO).在该模型中,工件上的孔分为两类:固定孔和可决策孔.MTdDPO的目标是通过判断可决策孔的路径归属和路径内各孔的加工顺序来实现加工路径长度的最小化.为实现MTdDPO的优化,提出基于强化学习的分段遗传算法(RLSGA).在RLSGA中,种群被视为智能体,智能体的状态是种群的多样性系数,3种不同的分段交叉算子是智能体的动作,智能体的奖励与种群的适应度值和多样性系数的变化有关.针对MTdDPO,新建5个基准测试问题,并在测试问题上将RLSGA与其他4个算法进行对比.结果表明,RLSGA的表现明显优于其他算法,RLSGA能够有效地解决MTdDPO问题.     

一个基于图的多边形拓扑关系生成算法

提出了一个基于图的多边形拓扑关系自动生成算法。该算法只需利用图中弧与多边形的拓扑信息,避免了多边形内角的计算与比较,算法中根据图的拓扑特征采取有效的策略,加快了多边形自动生成的速度。给出了算法的实例。     

基于知识图谱和重启随机游走的跨平台用户推荐方法

针对单一社交网络平台中推荐相似用户结果单一,对用户兴趣和行为信息了解不够全面的问题,提出了基于知识图谱和重启随机游走的跨平台用户推荐方法（URCP-KR）。首先,在分割、匹配出的目标平台图谱和辅助平台图谱的相似子图中,利用改进的多层循环神经网络（RNN）预测出候选用户实体,再综合利用拓扑结构特征相似度和用户画像相似度筛选出相似用户;然后,将辅助平台图谱中的相似用户的关系信息补全到目标平台图谱;最后,计算目标平台图谱中的用户游走到社区内每个用户的概率,从而得到用户之间的兴趣相似度来实现用户推荐。实验结果表明,与协同过滤（CF）算法、基于跨平台的在线社交网络用户推荐算法（URCP）和基于多开发者社区的用户推荐算法（UR-MC）相比,URCP-KP在推荐精确率及推荐多样性等方面均有所提高,推荐精确率最高可达95.31%,推荐覆盖率最高可达88.42%。     

基于知识图注意网络的个性化推荐算法

现有的大多数利用知识图谱的推荐算法在探索用户的潜在偏好时没有有效解决知识图谱中存在的不相关实体的问题,导致推荐结果准确率不高。针对这一问题,提出了基于知识图谱和图注意网络的推荐算法KG-GAT(knowledge graph and graph attention network)。该算法将知识图谱作为辅助信息,在图注意网络中使用分层注意力机制嵌入与实体相关的近邻实体的信息来重新定义实体的嵌入,得到更有效的用户和项目的潜在表示,生成更精确的top-N推荐列表,并带来了可解释性。最后利用两个公开数据集将所提算法和其他算法进行实验对比,得出所提算法KG-GAT能够有效解决沿着知识图谱中的关系探索用户的潜在偏好时存在的不相关实体的问题。     

MCI患者高阶动态功能连接的图论网络构建方法及分类

针对在低阶脑网络应用图论忽视了功能连接高阶动态性的问题,提出了一种基于高阶动态功能连接的图论网络构建方法(GNC-HodFC),提取高阶FC网络的图论特征以对轻度认知障碍患者和健康被试者进行差异性分析及分类。首先定义了表征高阶动态脑网络连接的图论节点和边;然后利用滑动窗相关技术提取低阶功能连接信息,提出平稳性判据,选取最优特征子集以构建图论的节点;最后提出自适应阈值策略对高阶动态功能连接信息进行选取以构建图论的边,最终完成高阶动态脑网络的图构建。实验结果表明,GNC-HodFC的平均分类准确率可以达到70.5%,优于其他三种对比方法,且患者组和健康组的图论特征中存在显著性差异,GNC-HodFC方法可以为轻度认知障碍的诊断提供新的辅助手段。     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

接口自动机的良构性检测算法及其实现

针对构件式系统中任一构件的非良构性会导致系统不能正常运行的问题,提出一种基于接口自动机（IA）来分析和检测构件良构性（well-formedness）的算法,并据此实现了一个构件良构性检测原型系统。该算法首先构造与接口自动机同构的可达图;其次,基于可达图通过深度优先遍历生成一条覆盖所有迁移的有序集;最后,根据该有序集检测在外界环境满足其输入假设的情况下,每个属于方法的活动到其对应返回活动的路径的自治无异常可达性,从而实现接口自动机的良构性检测。根据所提算法在Eclipse平台设计并实现了构件良构性检测原型系统T-CWFC,该系统通过JFLAP建立构件的接口自动机模型并构造其可达图,进而对接口自动机作良构性检测并输出相关检测信息。最后通过对一组构件的良构性检测实验验证了算法的有效性。     

On setup level tool sequence selection for 2.5-D pocket machining

This paper describes algorithms for efficiently machining an entire setup. Previously, the author developed a graph based algorithm to find the optimal tool sequence for machining a single 2.5-axis pocket. This paper extends this algorithm for finding an efficient tool sequence to machine an entire setup. A setup consists of a set of features with precedence constraints, that are machined when the stock is clamped in a particular orientation. The precedence constraints between the features primarily result from nesting of some features within others. Four extensions to the basic graph algorithm are investigated in this research. The first method finds optimal tool sequences on a feature by feature basis. This is a local optimization method that does not consider inter feature tool-path interactions. The second method uses a composite graph for finding an efficient tool sequence for the entire setup. The constrained graph and subgraph approaches have been developed for situations where different features in the setup have distinct critical tools. It is found that the first two methods can produce erroneous results which can lead to machine crashes and incomplete machining. Illustrative examples have been generated for each method.     

知识增强的图神经网络序列推荐模型

现有基于图神经网络的序列推荐模型大多仅关注用户与项目交互的结构性信息,序列偏好的学习仅涉及项目交互顺序,缺乏项目自身的内容信息,并且未有效利用用户信息及挖掘项目之间更深层的语义关系。提出一种知识增强的图神经网络序列推荐模型KGGNN,引入知识图谱,并结合用户交互数据构建协同知识图谱,学习得到项目语义关联辅助信息以及用户关联辅助信息。将交互序列构建成有向序列图,利用门控图神经网络以及用户关联辅助信息学习序列中项目节点的结构性信息。通过注意力机制组合项目向量作为全局序列偏好,将最近交互的项目作为当前兴趣偏好,融合两者形成最终序列偏好,并结合项目语义关联辅助信息进行模型预测。在Amazon-Book、Last-FM、Yelp2018这3个公开数据集上的实验结果表明,辅助信息能有效提升序列推荐的准确性,该模型在命中率（HIT@K）和归一化折损累计增益（NDCG@K）2个指标上相较于GRU4Rec、NARM、SASRec等模型均有显著提升。当评估指标K值选取10时,与KGSR模型相比,其HIT@10指标在3个数据集上分别提升12.9%、4.5%、6.9%,NDCG@10指标在3个数据集上分别提升...     

WDM网状网络中静态流量疏导的收发器节约辅助图模型

对于WDM光网络中的静态流量疏导，提出了一种收发器节约的辅助图形（TSAG）模型。基于辅助图提出了一种收发器节约的方法（TSABAG），针对不同的流量可以给辅助图中不同的边分配不同的权值，以实现不同的疏导策略。仿真试验证明，TSAG模型极大地节约了占用的收发器资源，而且拥有较高的吞吐量。     

A technique for drawing directed graphs

A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast     

Fast Tensor-Product Solvers: Partially Deformed Three-dimensional Domains

We discuss the numerical solution of partial differential equations in a particular class of three-dimensional geometries; the two-dimensional cross section (in the xy-plane) can have a general shape, but is assumed to be invariant with respect to the third direction. Earlier work has exploited such geometries by approximating the solution as a truncated Fourier series in the z-direction. In this paper we propose a new solution algorithm which also exploits the tensor-product feature between the xy-plane and the z-direction. However, the new algorithm is not limited to periodic boundary conditions, but works for general Dirichlet and Neumann type of boundary conditions. The proposed algorithm also works for problems with variable coefficients as long as these can be expressed as a separable function with respect to the variation in the xy-plane and the variation in the z-direction. For problems where the new method is applicable, the computational cost is very competitive with the best iterative solvers. The new algorithm is easy to implement, and useful, both in a serial and parallel context. Numerical results demonstrating the superiority of the method are presented for three-dimensional Poisson and Helmholtz problems using both low order finite elements and high order spectral element discretizations.