网树求解有向无环图中具有长度约束的简单路径和最长路径问题

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.

最长路径问题研究进展

最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用。参数计算理论产生后,参数化形式的k-Path问题成了研究的热点。介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果。最后,提出了该问题的进一步研究方向。

用最长路径法自动生成通风网络图

通风网络图是矿井通风管理的重要图件之一,也是进行矿井通风系统模拟、网络解算、通风系统优化的基础资料。根据通风网络图的特点,介绍了一种由通风网络结构数据自动生成通风网络图的方法,并进行了开发实现和实践应用。

基于GA与最长路径并联通路法优化通风网络图绘制

针对矿井通风网络图分支交叉的问题,基于最长路径对网络图节点分层,以遗传算法优化节点排序,主要采用堆积木的组合思想来进行层间交叉与层内交叉操作,提高层次图的质量(减少分支交叉数),并以重心定位启发式算法来增强遗传算法的局部搜索能力,提高遗传算法的搜索质量。最后,以改进的最长路径并联通路法绘制出较优的通风网络图。

基于遍历搜索二叉树中最长路径的算法研究

在对二叉树存储结构进行分析的基础上,介绍二叉树遍历算法的一种应用,即基于求解二叉树深度算法设计实现的搜索二叉树中最长路径的算法。这里详细介绍了搜索二叉树中最长路径问题的分析解决思路,在对可能的预期结果进行分析的基础上,给出了算法的设计方案,同时给出了具体的C语言算法描述。

一种基于最长路径的脉冲序列抽取算法

针对传统的动态关联算法在脉冲序列抽取方面存在的不足,提出了一种基于最长路径原理的脉冲序列抽取算法。该算法首先将待抽取的脉冲序列转换为一个经过拓扑排序的有向无环图,然后求解该有向无环图的最长路径,最后根据该最长路径抽取出相应的脉冲序列。相比较于传统的动态关联算法,基于最长路径的算法性能受设置的容差大小的影响较小,可以有效地提高脉冲序列抽取的正确率,并且具有较高的稳定性,从而能够更好地满足信号分选算法的实际工程需要。仿真实验表明了该算法的有效性。

林区轮伐期优化的隐式图建模和最长路径算法

针对森林经济效益最大化的轮伐期优化问题,首先分析了木材产出利润模型,将利润最大化转化为图的最长路径问题,建立了一个隐式图模型。其次,提出了最长路径算法,并对隐式图模型进行求解,用得出的最长路径计算出最优轮伐期。最后,对模型和算法的实用性进行了验证。本文设计了3组试验,分析林地投入产出、木材产出利润和木材产量对最优轮伐期的影响机理。分析结果表明:林业投资回报周期长,且利润回报受到市场利率的显著影响;轮伐期的确定主要取决于木材产量函数的选择。

考虑门逻辑功能的最长路径搜索算法

在静态时序分析中,寻找最长时延路径以及最坏情况下时延是最重要的任务。考虑门的逻辑功能,提出了一种精度更高的最长路径搜索算法。由于门的时延大小不仅取决于输入信号的过渡(transition)时间和负载电容大小,还取决于输出信号的状态(上升或下降)以及其它管脚状态(高电平或低电平),因此,该算法极大地提高了静态时序分析的精度。文章还给出了区段搜索算法,可以找出时延在给定范围内的所有路径。这两个搜索算法对每条边至多遍历一次,时间复杂度依然为线性。

随机网络最长路径的概率分布

利用马尔可夫骨架过程理论研究随机网络的最长路径问题,给出其最长路径长度的分布函数.

面向异构处理平台的最长路径列表调度算法

任务调度算法的研究一直是异构计算技术研究中的热点,充分挖掘异构处理平台的并行优势,可最大限度实现平台资源的高效利用。通过分析异构处理平台的执行特点,设计符合异构处理平台的任务调度策略,提出面向异构处理平台的最长路径列表调度算法(Longest path list scheduling algorithm,LPLS)。算法在任务优先级阶段,基于最长路径列表计算优先级,最耗时路径上的任务被优先调度;在处理器选择阶段,遵循任务完成时间最小的原则,所选择的处理器可使下阶段任务的完成时间更短,异构平台整体处理时间更小。仿真实验结果表明,相比于经典的HEFT算法,LPLS算法是一种负载更加均衡的算法,具有调度长度更短、效率更高等优势。

寻找图中两顶点间最长路径的算法设计

在"图"这种数据结构中,求解任意两顶点之间最长路径算法,有着广泛的理论和应用背景,而其求解算法却研究较少,没有像求解最短路径算法那样有成熟的算法(Dijkstra算法和Floyd算法[1])和广泛的影响。讨论并实现了一种查找图中任意两顶点间带权路径长度中最长路径的算法。使用该算法可以回答图中任意两个顶点之间的最长路径长度及任意两顶点间存在的不同路径的数目。

一种图的st编号路径长度算法

通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度。用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径。使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径。st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用。

一种带匹配路径约束的最长公共子序列长度算法

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。

基于HSV和骨架提取的水稻种子芽根长度自动化测量方法研究

种子的芽长和根长是评判种子质量的重要指标。传统的人工测量芽长与根长的方式,存在着繁琐、费时费力、易受主观判断影响等问题。利用图像处理技术的芽长根长自动检测算法能够提高芽长根长检测的效率,也避免了主观因素导致的误差。本研究基于HSV色彩空间和骨架提取,设计了种子芽长根长的检测方法。首先对图像进行阈值分割,其次再利用骨架提取算法结合深度优先搜索寻找水稻幼苗拓扑结构中最长路径,最后根据HSV色彩空间分割出的种子区域对芽和根进行分离,且采用间隔选取像素点坐标的方式计算欧式距离,并分别统计芽和根的长度。结果表明,本文方法自动测量的芽和根长度与人工实测数据的相关系数分别为0.998和0.997,平均百分比误差分别为1.48%和1.57%。基于HSV色彩空间和骨架提取的复合算法能够对种子萌发过程中的芽长与根长进行快速、准确地测量。

由通风网络结构数据自动生成通风网络图研究

通风网络图是矿井通风管理的一种重要图件。本文根据通风网络图的特点,介绍了一种由通风网络结构数据自动生成通风网络图的方法,并进行了开发实现和实践应用。

通风网络图自动生成与编辑软件的研制

为了改变矿井通风网络图绘制困难的现状,达到高效绘制目的,通过对各种绘制方式的深入研究,提出了基于.NET的AutoCAD二次开发实现通风网络图自动生成与编辑的技术,着重分析了通风网络图自动生成的具体实现原理和算法,并在此基础上进行了开发实现和实践应用。应用结果表明,由该软件自动生成的通风网络图符合绘制原则。同时,利用步骤模仿技术实现了动态可视化图形编辑功能,很好地满足了现场工程技术人员的绘图需求,提高了绘图效率。

保持连通的边缘细化算法

传统的图像边缘检测算子一般都只能得到多像素宽边缘,这为后续的图像处理带来了一定困难。结合边缘走向趋势的估计技术以及对连通关键点判断的方法,提出了一种新型的边缘细化算法———保持连通的边缘细化算法。该算法能在保持边缘原有信息(连通和走向)的前提下,以较小的计算开销,给出理想的或是可接受的单像素宽细化结果。

区域产业集群发展关联网络的建模与实证分析——以汽车行业和石化行业为例

本文首先根据投入产出直接消耗系数表,结合复杂网络理论的建模思想构建了一类有向加权网络——区域产业结构网络,然后运用2007年全国投入产出数据研究了该网络的一系列特征值。在研究网络的路径问题时,考虑到网络边权是一种相似权,进而转向研究网络的最长路径及其蕴含的产业经济意义。以此为基础,论文又构建了产业间最强关联网络和产业集群发展关联网络,一方面梳理出区域产业规划过程中的关键产业部门,另一方面通过与发达国家和地区进行比较,识别出产业集群化过程中存在的问题。最后选取了汽车行业和石化行业进行了产业集群发展可行性方面的实证分析。

基于内容的视频拷贝检测研究

提出基于图的视频拷贝检测方法,该方法将视频序列匹配结果转换为匹配结果图,进而将视频拷贝检测转换成在匹配结果图中查找最长路径的问题。实验结果显示基于图的序列匹配算法拷贝定位准确度高,可弥补图像底层特征描述力不足的缺陷,节约检测时间,批量定位2段视频序列中可能存在的多段拷贝。

基于分层法的通风网络图绘制算法研究

最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径,采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中;且采用几何相交方法判断分支交叉,效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层,求解整数规划问题优化节点分层减少长边;采用模拟退火遗传算法优化节点排序,从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程,采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。