基于树分解的时序最短路径计数查询算法

最短路径计数是图计算中的一个重要研究问题,旨在查询顶点间的最短路径数,在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图,但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比,时序图增加了时间信息,结构更复杂,在查询顶点间的路径数时必须考虑边的激活时间,因此静态图中最短路径计数方法不再适用于时序图,并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题,提出一种基于树分解构建TG-TL(Temporal Graph-Tree Label)索引的方法。该方法包含构建索引和在线查询两个阶段,构建索引阶段根据时序图的属性设计时序树分解算法,将时序图转化为树结构;然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法;在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明,与基于TG-base(Temporal Graph-base)索引的查询算法相比,所提算法在查询效率上至少提升了61%,因此所提算法在时序图最短路径计数问题上具有高效性和有效性。

基于树分解的空间众包最优任务分配算法

随着配备高保真传感器的移动设备的普及以及无线网络资费的快速下降,空间众包作为一种问题解决框架被用于解决将位置相关的任务(如路况报告、食品配送)分配给工人(配备智能设备并愿意完成任务的人)的问题.研究空间众包中最优任务分配问题,关键在于设计出将每个任务分配给最合适的工人的任务分配策略,以使得完成的总任务数目最大化,而所有的工人可以在完成所分配的任务后,在预期最晚工作时间之前返回起点.找到全局最优分配是一个棘手的问题,因为该问题不等于单个工人的最佳分配的简单累加.注意到,仅有部分工人存在任务依赖,因此利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法,该算法可以快速地更新启发函数界限,从而高效地对不可能成为最优解的分配方案尽早地进行剪枝.实验结果表明:所提出的方法是非常有效的,可以很好地解决最优任务分配问题.

图的树分解及其算法应用研究进展

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。

特征谓词知识树分解策略的研究

搜索空间约减是智能规划研究中的重要内容之一.谓词知识树是一种特殊的树状结构,它表达了规划领域中实现同一谓词的所有动作.在规划求解过程中,这些动作的前提条件通常是不能同时得到满足的.因此,提出了知识树的分解原理以及基于特征前提的知识树分解策略,并给出了相应的分解算法.对任意一个规划领域,利用该分解算法可将知识树分解成若干个较小规模的知识子树,使其对具体规划状态具有更强的针对性.在规划求解过程中使用知识子树可以避免一些不必要的动作搜索,提高规划效率.实验结果表明分解算法是有效的.

结合Separator的约束满足问题树分解方法

基于树分解的回溯搜索算法,结合separator分解算子提出一种新的搜索算法BTD+-MAC.该算法在搜索时,优先选择separator中的变量进行相容性检查和实例化,由于树宽度的减小能提高约束传播的效率,进而提高问题求解效率.对几组benchmark问题进行测试,测试结果表明,该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.

零件形状特征图树分解原理及应用

如何用特征构造零件的信息模型,是特征建模中至今悬而未决的同题,本文作者从零件形状特征关系图入手,研究了零件形状特征关系图的一些构造规律,首次提出了零件形状特征图树分解原理,并比较成功地运用到了回转类零件的特征建模和相应的基于特征的CAD系统开发之中,为用形状特征构造零件信息模型以及开发基于特征的CAD系统提供了理论依据和建模思路。

基于平均度的树分解启发式算法

很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。

基于改进树分解技术的约束满足问题的符号ADD求解算法

为提高大规模约束满足问题(CSP)的求解效率,提出了基于改进树分解技术的符号ADD求解算法。通过CSP的ADD描述,将树分解技术的树聚类与符号ADD结合,以提高算法的求解效率。采用改进最大基数(MC)的变量选择法,提高构造弦图的效率,引导团的构造以及连接树的生成。对大量随机生成的测试用例进行实验仿真,结果表明,基于改进树分解技术的符号ADD求解算法求解效率优于BT-FC-ADD算法和BT-ADD算法。

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。

基于树分解结构的Top-k最短路径查询算法

基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径。将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询。本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径。实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内。

一种基于树分解的图上点区间编码方法及应用

根据图上节点所在位置与邻居节点特征,可以使用不同策略为每个图上节点进行区间编码,基于区间编码,许多在大型图上的应用如知识图谱查询、智能问答等的处理可以加速或得到准确性上的提升。针对此种情况,提出一种基于树分解算法的图上点区间编码方法,并在大型知识图谱上通过智能问答歧义消除的应用验证该方法的有效性。实验结果表明,该方法能够有效地表达出图上节点的位置特征,并帮助智能问答中的实体消除歧义。

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

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

基于二进制树分解的动态防碰撞算法

针对现有的无线射频识别系统(RFID)二进制树防碰撞算法所需的搜索时隙较多,系统识别速率较低,提出了一种基于二进制树分解的动态防碰撞算法。该算法利用标签EPC的唯一性,对发生碰撞的比特位进行深度分解,根据碰撞位调整搜索状态,从而进一步减少搜索时隙数并提高了系统的呑吐量。通过对算法的分析和仿真结果表明:基于二进制树分解的动态防碰撞算法相对于动态二进制搜索算法有明显的优势。

基于线性时间算法的故障树模块扩展分解方法

故障树分析被广泛应用于核工业、航空航天和交通控制等安全攸关领域的安全性分析中。然而,像核电站等大型工业所使用的大型故障树的分析需要耗费大量的计算资源,导致分析效率低下,时间消耗过多。为了解决此问题,对现有的线性时间算法进行改进,提出新的故障树简化规则和模块扩展分解算法。首先提出等效事件的概念,扩展线性时间算法所分解的模块数;在考虑时间复杂度和资源利用率的基础上,提出一套新的简化规则,以合理地去除故障树中的冗余信息。实验证明,提出的分解方法能有效地优化故障树分析,进一步减少大型故障树分析的计算时间和内存消耗。

小波包分解树结点与信号子空间频带的对应关系及其应用

小波包变换的Mallat分解算法可以把较宽的信号频带划分成相等带宽且互不重叠的窄频带,但由于信号子空间频带的频率大小并非按照分解树结点(node)编号的大小顺序排列,各个结点重构信号的频率范围不易判定.本文通过分析小波包变换的Mallat分解算法与分解滤波器的关系,设定频带编号与结点编号间进行二进制转化的运算规则,得到了小波包分解树结点与信号子空间频带的对应关系,然后通过模拟信号进行了验证.结果表明,本文给出的小波包信号子空间频带的排列规则是正确的.

基于分解树的复杂产品装配实例表示方法

基于实例的装配方案设计有利于提高装配方案的设计效率和准确性,而装配实例的表示和存储是基于实例的装配方案设计的基础。因此,提出基于分解树的装配实例表示方法。该方法包含2部分:1基于分解树表示装配结构;2基于分解树表示装配规划方案。并实现了基于邻接矩阵的装配方案存储,总结了基于邻接矩阵的装配实例存储方法的4个性质。并采用实例验证了该方法是有效的。

一种快速分解大整数的小因子的优化分解树OFT算法

分解大整数的小因子是解决IFP ,DLP问题的诸多攻击方法中的重要运算模块 .本文在目前分解大整数小因子算法的基础上 ,提出的优化分解树 (OptimizedFactorizationTree)算法 ,利用树型数据结构和相应的构造算法与回溯算法 ,配合以作者提出的分解表截支方法和优化分组策略 ,可以将分解大整数小因子的速度提高 5 0 %以上 .该算法还可以为大整数素性判别做高效过滤 ,快速识别大部分合数 .

小波包最优基分解树的降噪滤波方法研究

装载机的传动系统工作时传感器所采集到的信号受环境干扰大,不利于数据分析,因此在研究其工作状态时需对数据信号进行降噪滤波。本文以5t装载机的前轴扭矩信号为研究对象,剥离其趋势项后采用小波包变换法进行db9-6尺度分解,进而通过小波包最优分解树得到重构信号。通过与巴特沃斯去噪、小波变换去噪法对比后得出:巴特沃斯滤波处理法相较于原始信号存在相位偏移;小波包最优基分解树去噪后的信噪比、均方根误差分别为16.38与74.71,与小波变换去噪法相比结果近似,更适用于工况识别、人工智能算法等领域。研究结果可为其他同类型工程机械数据信号处理提供方法依据。

基于动态树冲突分解的协作随机接入方案

提出一种基于动态树冲突分解的协作随机接入方案(DTCRA)。该方案设置一个由冲突节点个数决定的信道增益门限值,若源节点与接入点间的信道增益大于该门限值,则源节点重传数据包,否则由中继节点放大转发,从而实现了动态树冲突分解,获得了多用户分集增益并降低了空时隙数量。数值与仿真结果表明,提出的方案相比于其它传统类和跨层类随机接入方案,具有更好的吞吐量、时延和能量效率性能。

多子波树型分解算法

多子波分解是一个较新的概念,它是把一个地震道分解成不同形状的地震子波的集合,然后对子波频率进行筛选,对不同的目标重构出新的地震道,以此来提高地震分辨率,识别地层异常信息。本文以树型结构为基础,提出了全树型分解、分段树型分解、分段回归树型分解三种分解算法并取得了较好的分解效果。