共查询到20条相似文献,搜索用时 125 毫秒
1.
单源最短路径问题的改进算法 总被引:3,自引:0,他引:3
周玉林 《上饶师范学院学报》2001,21(3):18-22
探讨了单源最短路径问题算法所能达到的时间复杂性的下界,提出了时间复杂性为O(m m)和O(nlogt m)的改进算法,其中n=|V|,m=|M|,t为从优先队列中抽取最小结点的次数,我们主要用Fibonacci堆和拓扑排序的思想方法。 相似文献
2.
网络最短路径算法的改进及实现 总被引:2,自引:0,他引:2
从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进.定义新的节点类来高效存储网络的拓扑信息,节省了计算机存储空间;采用满二叉堆数据结构对节点进行排序并选取最短路径节点,大大提高算法效率.仿真例子表明,对于某些网络结构,改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N2)近似降至O(N). 相似文献
3.
从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进.定义新的节点类来高效存储网络的拓扑信息。节省了计算机存储空间;采用满二叉堆数据结构对节点进行排序并选取最短路径节点。大大提高算法效率,仿真例子表明.对于某些网络结构.改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N^2)近似降至o(N)。 相似文献
4.
《华中科技大学学报(自然科学版)》2021,49(2):32-36
从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上。证明了一般路径运算矩阵的幂长公式并得到了简单图存在哈密顿回路的充要条件,分析了矩阵乘法运算的总时间复杂度,结果表明本算法比其他同类方法计算量大大减少,为图论相关路径问题研究提供了一个新的研究方法。 相似文献
5.
温晓磊 《天津理工大学学报》2009,25(1)
为了解决无向网络的最短路径优化问题,本文采用的是遗传算法和模拟退火算法相结合的思想,阻止早熟现象的发生,保证种群的多样性,防止陷入局部寻优情况的出现,并且定义了无向网络中的结点结构.仿真比较实验说明,混合算法不仅比单一遗传算法运算时间缩短,而且可以找到最短路径,证实了该算法的可行性. 相似文献
6.
洪玉振 《河海大学学报(自然科学版)》2001,29(1):34-39
对应于一般单件车间排序问题,构造了一种由节点、最短路径和相邻路径组成的隙网络,通过网络分析,探讨了求解这一最复杂的排序问题的局部最优解问题,与启发式方法相比,该方法为优化方法;与分支定界法和整数规划法相比,该方法是一种有效算法,即随着问题规模的增大,它具有多项式时间复杂性。 相似文献
7.
《福建师范大学学报(自然科学版)》2017,(3)
在室内复杂停车场的路径规划问题上,许多方法使用了单源最短路径的典型算法Dijkstra算法对最短路径进行规划,但该算法需要花费大量时间和空间来计算和存储与最终路径无关节点.为了提高算法效率,通过把地图中所有的结点进行顶点归一、区域集合划分以及区域编号排序等策略,大大提高了算法运行效率.实验显示,在随机对某结点目标进行最短路径搜索时,搜索时间可以缩短80.8%到98.9%,大大减少了时间复杂度和空间复杂度. 相似文献
8.
尝试性地将设计结构矩阵应用于业务流程优化设计中的拓扑排序问题,提出了基于设计结构矩阵(DSM)的拓扑排序新方法,并设计了邻接矩阵方法运算规则.与传统方法比较,它不仅克服了传统算法对环路的限制,而且由于其从两个方向同时搜索,设计思路简单、效率高,为设计结构矩阵在业务流程优化中的应用进行了积极的探索. 相似文献
9.
图的应用问题的求解前提是图的模型的创建,而图在计算机中的存储方式是各类算法的使用前提。用二维数组表示的邻接矩阵来存储图,是常用的方式。在此基础上,探讨了拓扑排序、最短路径及状态转换问题的图的邻接矩阵的初始化问题。 相似文献
10.
陈业斌 《华中科技大学学报(自然科学版)》2009,37(4)
定义了有向双环网络G(N;r,s)新的路由模型--二叉树模型,给出了O节点到二叉树模型任意一层节点的最短路径的路南策略.证明了有向双环网络的直径等于其二叉树的树高,研究了任意两节点之问的最短路径与其所在层及其相应位置的关系,给出有向双环网络任意两节点最短路径的算法.运用此算法,只需简单的算术运算和关系运算,就能快速求出任意两节点的最短路径. 相似文献
11.
由于未考虑DAG(directed acyclic graph)任务的自身结构, 基于G-EDF(global earliest deadline first)的DAG并行任务模型的可调度性分析存在很大的悲观性,因此本文针对DAG任务集在多处理器系统中采用G-EDF调度策略下的响应时间分析进行了研究.首先针对carry-in任务实例执行的情况提出更加精确的carry-in工作量估算方法.基于该carry-in工作量估算方法提出一种基于完成时间的问题窗口工作量估算方法.最后,结合上述两个改进策略提出了基于G-EDF的DAG任务响应时间分析方法.仿真实验表明,所提出的方法较目前已知的调度策略方法可调度性至少提高15%,最高可达25%. 相似文献
12.
13.
MCM布线中求取最大加权不相交匹配的有效算法 总被引:3,自引:2,他引:1
MCM在集成电路封装中的广泛应用,迫切需要高效准确的布线.四通孔布线算法用于实际MCM布线时,需要解决最大加权不相交匹配问题.基于现在解决此问题较复杂,在描述四通孔布线和把此问题转化为求取最大链问题的基础上,提出了一种有效算法来解决最大加权不相交匹配问题,其主要思想是利用求最长路径的方法来解决最大链问题;证明了此算法并给出实际的布线结果.实践证明,此算法和以前的方法相比具有简单和高效的特点 相似文献
14.
文章将任务调度分为资源分配和调度执行2个阶段,定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务依赖图中边的权值;分析了任务图冻结消减和执行消减对任务图结构的影响;提出了基于LBT的网格依赖任务调度算法;实验表明该算法有效地减弱了网格动态性对调度结果的影响。 相似文献
15.
针对新闻视频镜头切变时颜色特征的变化, 提出了一种基于颜色直方图加权的方法, 即采用加权颜色直方图作为特征求相邻两帧的帧间差, 并与自适应阈值进行比较, 确定潜在的镜头边界。同时针对新闻视频中经常出现的闪光灯现象对镜头检测的影响, 采用改进的滑动窗口法进行二次检验, 进一步确定镜头边界, 有效减少了视频中物体运动过快对镜头边界检测的影响。实验结果表明, 该方法与传统方法相比, 其检测效果较好, 且计算复杂度低, 易于实现。 相似文献
16.
为提高信息检索中检索结果的查准率,提出了基于句法分析以及带权路径长度的句子相似度计算方法。该方法首先对用户问句进行了分词、词性标注以及句法分析处理,并根据处理后的结果对该句进行了关键词提取、加权和同义词近义词扩展处理。然后提出了基于带权路径长度计算的方法,并用该方法计算用户问句与检索信息标题句之间的相似度,即问句的带权路径长度与标题句的带权路径长度的相对比值,以此对检索结果进行二次排序,提高检索结果查准率。实验表明,该句子相似度方法能有效地提高信息检索中检索结果的查准率。 相似文献
17.
18.
一种基于二维EMD的图像融合方法 总被引:1,自引:0,他引:1
图像融合是图像处理中的一个重要内容,常用的小波图像融合主要是基于像素级融合,这种方法容易失去局部特征相关性较强的特性,融合后会出现局部斑点现象.该文应用二维EMD方法在像素级也进行了讨论,并且针对EMD分解的特殊性,提出了一种用二维EMD(two—dimensionalEMD)进行图像融合的方法,采用对IMF(intrinsicmodelfunction)分量在对应频率段上进行线性加权融合,提出了几种常用计算加权系数的方法.通过实验分析和性能评价表明,基于二维EMD的图像融合较小波图像融合效果较好,更能提取图像细节. 相似文献
19.
针对正态分布场合下无失效数据的情形,利用最小二乘估计,加权最小二乘估计和模糊加权最小二乘估计三种方法,给出正态分布参数和可靠度的计算方法. 相似文献
20.
一种基于小波系数自适应加权平均的解剖和功能医学图像融合算法 总被引:3,自引:0,他引:3
为了有效地融合解剖和功能医学图像中的信息,提出一种基于窗口标准差的小波系数自适应加权平均融合算法.它的优点在于能动态地在系数之间分配权重,从而达到提高融合效果的目的.实验结果表明该方法优于传统的加权平均系数组合方法. 相似文献