资源描述：
《网树求解有向无环图中具有长度约束的简单路径和最长路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、网树求解有向无环图中具有长度约束的简单路径和最长路径问题计算机学报..第卷第期.年月网树求解有向无环图中具有长度约束的简单路径和最长路径问题李艳孙乐’朱怀忠引武优西趵’河北工业大学经济管理学院天津”河北工业大学计算机科学与软件学院天津摘要具有长度约束的简单路径,。问题是指求解图中任意两点间路径长度为/的简单路径数,是?问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解,,问题的算法,。.网树是一种多树根多双亲的数据结构.算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对。算法
2、进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法,.,。算法可找到所有最长路径,对,算法做进一步改进形成改进的。算法,改进的。算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了.和改进的。算法的正确性与有效性.关键词有向无环网络;简单路径;长度约束;最长路径;网树中图法分类号号:./....∞?’?’’,,,,?//.?是一.?,?..,..?..;;;;收稿日期:?;最终修改稿收到日期:?。本课题得到国家自然科学基金,、河北省自然科学基金及河北省高等学校青年基金项目
3、资助.李艳,女,年生,博士,副教授,主要研究方向为数据挖掘与智能计算.;..孙乐,男,年生,硕士研究生,主要研究方向为数据挖掘与智能计算.朱怀忠,男,年生,硕士,讲师,主要研究方向为数据挖掘与智能计算.武优西通信作者,男,年生,博士,教授,主要研究领域为数据挖掘与智能计算.:..万方数据李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题,问题.本文在有向无环图中求解该问题形成了.,引言可在具有周期间隙约束的序列模式挖掘和具图是一种比线性表和树更为复杂的数据结构.有间隙约束的模式匹配等方面得到应
4、用.等人妇提出了具有周期间隙约束的序列模式挖掘问在线性表中,结点间为单前驱单后继的线性关系;在题,并将该模式挖掘方法应用在序列挖掘中;树结构中,结点间为单前驱多后继的非线性关系;而等人口将具有周期间隙约束的序列模式在图结构中,结点问则为多前驱多后继的非线性关挖掘方法应用于购买模式的挖掘.尽管等人系.图中任意两个结点之间都可能相关,因此图已经采用了空间变换的方法进行序列模式挖掘,但是此被广泛应用于诸如语言学、逻辑学、物理、化学、电气方法的基础是具有间隙约束的模式匹配问题口?.文工程和计算机科学等学科中.献研究
5、了具有间隙约束和一次性条件的模式匹在图论中,最长路径问题配问题的求解方法,给出了将具有问隙约束的模式是指在给定的图中找出一条最长的简单路径.在无匹配问题转换为有向无环图的算法,这使得具有间向图中求解最长路径问题是著名的难问题,现隙约束的模式匹配问题与问题建立有的研究主要基于近似算法心、参数化算法¨.另外了实质性联系.一类研究是针对特殊图进行求解,并给出多项式时为了解决问题,本文利用网树间复杂度的求解算法,如和采用数据结构简称网树,进行求解.网树一种深度优先搜索策略对伴相似图是一种多前驱多后继的非线性数据结构
6、,是对树结中最长路径问题进行了求解;和构的拓展.网树不仅具有树结构的所有概念,如根结¨在二部置换图点、叶子结点、双亲、孩子、路径、层等,而且除根结点中对最长路径问题建立了线性时间复杂度的外,网树中任意结点可以有多个双亲结点.本文提出求解算法,其求解的二部置换图既是一个置换图也是了网树求解有向无环图中具有长度约束的简单路径一个二部图;等人口在区间图~算法中运用动态规划思想,对最长路径问题给出,,算法了时间复杂度为‖的求解算法;和将该问题转化为一棵网树,然后利用网树的树根路在有向无环图径数这一特殊性质对该问题进
7、行求解.,所有边的长度非负的情况下,对最算法的时间复杂度和空间复杂度分别为×以×长路径的方差和期望的边界进行了计算.和卵,这里仇,,行和分别表示两点间是一问题是指在给定的图中找出一条长度为的路径长度约束、顶点最大出度以及顶点数和边数.是的简单路径,是最长路径问题的一种特殊情况.对算法做进一步改造,可以形成求解等人口基于分治思想对一般图中的忌问最长路径问题的算法题进行了研究,提高了该问题的计算速度.问,.对算法做进一步题在诸多领域具有非常重要的应用.等人在改进形成改进的算法,该算法使得网树生物学约束下,采用
8、彩色编码技术,在酵母蛋白质相退化为一棵树,并使算法的时间复杂度和空间复杂互作用网络中查找蛋白质传导路径,其求解方法是度分别为和竹,这里和分别将蛋白质作为结点,蛋白质之间的相互作用关系作表示图的顶点数和边数.为边,以此构成的生物蛋白质作用网络,权值最大的本文第节对.问题进行定义;志一代表信号传导路径;等人∽利用第节介绍网树的概念和性质;第节提出?推广的不均衡性走一算法,同时分析该算法的时问复杂度和空间对忌个车辆的路
