共查询到17条相似文献,搜索用时 109 毫秒
1.
求解Hamming距离下的最短路改进问题的一个近似算法 总被引:1,自引:0,他引:1
研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法. 相似文献
2.
最短路问题在运输网络中的应用 总被引:2,自引:0,他引:2
李玲 《长春师范学院学报》2006,25(3):58-61
最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化问题都可以转化为最短路问题来求解.本文重在研究公路网络运输中的最短路问题. 相似文献
3.
研究Hamming距离下树型网络的最短路改进问题,通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题并求解.该研究方法在一定程度上推广了已有的结果.该问题的研究有助于设计求解一般的Hamming距离下的最短路改进问题的有效近似算法. 相似文献
4.
含负权有向图最短路问题的一种新算法 总被引:1,自引:0,他引:1
王欣 《武汉科技学院学报》2007,20(5):36-39
Dijkstra算法是求解最短路问题的一种经典算法,但是它的缺点是不能用来求解含有负权的最短路问题。本文对图论中含有负权的最短路问题进行研究,提出了一种新算法,将含有负权的最短路问题先转化为不含负权的最短路问题,最后再利用Dijkstra算法求解,并用实例验证该算法的有效性,具有一定的现实意义。 相似文献
5.
多阶段有向图是常见的一种有向图,许多运输、工程、管理等实际问题能转化为有向图最短路问题进行求解,尤其赋权多阶段有向图对解决该类实际问题更具有重要意义.研究了赋权多阶段有向图的最短路问题,从图上逆序标号法、表上作业法和动态规划法不同的角度对文中实例给出了赋权多阶段有向图最短路求解方法。 相似文献
6.
孙小军 《吉林大学学报(理学版)》2015,53(3):478-482
针对带有模糊约束的最短路问题,在其模糊线性规划模型的基础上,利用容差法和罚函数法对该模型进行转化,得到了与原模型具有相同最优解与最优值的转化模型,并提出一种修正的萤火虫算法求解转化模型.数值算例结果表明,该模型与算法对求解带有模糊约束的最短路问题有效. 相似文献
7.
8.
本文对于权值为时间t的连续函数动态最短路的问题,通过先求解某个时刻从起点到终点的最短路,然后分析某个时刻的最短路与该时刻的邻域内的最短路关系,再借助有限覆盖定理,求解出某一闭时间区间内的最短路时.从一新途径研究了变权的最短路问题. 相似文献
9.
10.
李玲 《长春师范学院学报》2006,(6)
最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。 相似文献
11.
葛浩 《东莞理工学院学报》2009,16(5):31-34
主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。 相似文献
12.
最短路问题是寻找从原节点到其他节点最短的距离,它在交通运输、行程安排、信息传递中有很重要的作用.研究了具有模糊随机弧长的多属性最短路问题,通过比较解原模型与等价模型来解释模糊随机约束等价形式的有效性. 相似文献
13.
陈志民 《长春师范学院学报》2007,26(2):24-26
反优化问题是指修改给定的参数,使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题:通过修改给定网络上弧的长度,使得修改后网络中指定点之间的最短路长度不超过给定的常数,而其中修改费用是用哈明距离来衡量的,我们证明了哈明距离下的最短路反问题是强NP-完全的。 相似文献
14.
陈志民 《长春师范学院学报》2007,(4)
反优化问题是指修改给定的参数,使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题:通过修改给定网络上弧的长度,使得修改后网络中指定点之间的最短路长度不超过给定的常数,而其中修改费用是用哈明距离来衡量的,我们证明了哈明距离下的最短路反问题是强NP-完全的。 相似文献
15.
讨论了一个带权图的最短路径的算法及其若干个变形问题的算法,并在MATLAB软件环境下对最短路径问题给出了一个简捷易懂的程序。这些算法在实际应用中有较强的实用性。 相似文献
16.
朱志雄 《湖北大学学报(自然科学版)》2014,36(6):530-533,542
在研究最短通路问题的基础上,通过"最短通路"与"关键路径"的对比研究,给出PERT/CPM问题(计划评审技术图/关键路径方法的简称)相应的"对偶"的矩阵定义及"对偶"运算法则,进而推出"对偶"的计算公式. 相似文献
17.