Hamming距离下树型网络的最短路改进问题

研究Hamming距离下树型网络的最短路改进问题,通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题并求解.该研究方法在一定程度上推广了已有的结果.该问题的研究有助于设计求解一般的Hamming距离下的最短路改进问题的有效近似算法.     

Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.     

含负权最短路问题的一个改进标号法

在不出现负回路的情况下,给出了在赋权的网络图中求两点之间的最短路问题的一个改进标号法,该方法对于网络图中出现负权的情况也有效.最后给出了该算法的数值实验结果.     

Hamming距离下瓶颈约束最小支撑树反问题

讨论Hamming距离下瓶颈型约束最小支撑树反问题,给定的一个支撑树,修改给定网络边上的费用,使给定的支撑树成为最小支撑树且支撵树中边费用最大值不超过给定的常数,用瓶颈Ham-ming距离来衡量修改的权值,并给出瓶颈Hamming距离下的约束最小支撑树反问题定理的证明.     

随机网络的最短路问题

研究了随机网络上的最短路问题，并给出了一个启发式算法ESP来寻找期望最短路，以及启发式算法KESP寻找K-期望最短路，最后举出一个实例来证明算法的有效性．     

哈明距离下的最短路反问题

反优化问题是指修改给定的参数,使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题:通过修改给定网络上弧的长度,使得修改后网络中指定点之间的最短路长度不超过给定的常数,而其中修改费用是用哈明距离来衡量的,我们证明了哈明距离下的最短路反问题是强NP-完全的。     

哈明距离下的最短路反问题

反优化问题是指修改给定的参数，使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题：通过修改给定网络上弧的长度，使得修改后网络中指定点之间的最短路长度不超过给定的常数，而其中修改费用是用哈明距离来衡量的，我们证明了哈明距离下的最短路反问题是强NP-完全的。     

网络优化中最短路问题的改进Floyd算法

在Gauss-Seidel迭代法思想的基础上,提出了一种改进的Floyd算法来计算任意两点之间的最短路问题。通过对带权邻接矩阵按照行列由小到大和由大到小的顺序进行计算,只需两步迭代求得最短路长。算法分析和计算实例表明,改进的Floyd算法大大减少了迭代次数,提高了算法效率。     

经过转化可用动态规划方法求解最短路问题

最短路问题在实际中应用得非常广泛,用动态规划方法求解此类问题时,要求所求问题具有明显的阶段,但实际工作中的某些问题不能直接划分出阶段,若将此类问题经过转化可变成定阶段的能用动态规划方法求解的“标准模型”。     

装箱问题的一种新的近似算法

 研究了一维装箱问题(Bin Packing Problem),给出了一个新的近似算法:交叉装填算法(简称CF算法).证明了CF算法达到装箱问题的最好的近似值3/2;并且当这些物件的大小按非增性质预先排序后,CF算法的时间复杂度是线性的.     

求解最短路径问题的一种改进的人工蜂群算法

针对传统算法在计算大规模路网的优化问题时所表现出来的计算时间长、存储空间大等缺点,提出了一种改进的人工蜂群算法来求解最优路径选择的方法．试验结果表明,对于有向图和无向图,该算法都具有较好的全局寻优能力,即能获得满足条件的最优路径．     

最短路问题的通用算法--最短初等链法

最短初等链法是求解网络图最短路问题的通用算法，它突破了以往诸算法的局限性，适用范围广，具有广阔应用前景。     

模糊最短路问题的一种新算法

作者讨论了从一个指定点到另一个指定点的最短路问题,其弧长都是不精确的模糊数.利用模糊数的某种序关系,作者提供了一种新算法来处理模糊最短路问题,该算法由基于中心点的模糊数比较方法构成,基于中心点的模糊数比较方法可找到模糊最短路长,并获得相应的模糊最短路径.作者给出了4个解释性的实例并验证了算法的可行性.     

求解路网最短路的快速算法

探讨了最短路算法在交通分配中的重要地位。在此基础上．比较了现有最短路算法的优缺点,同时提出了一种改进的矩阵迭代算法．并利用该算法对一简单路网进行了验证。     

时变网络中零等待时间最短路问题的一个对偶算法

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

最短路问题的灵敏度分析与最短路调整

本文讨论的是无负回路的有向网络,在己知网络各节点间最短路的前提下,当网络中的个别节点、权值、弧发生变化时,变化对最短路有无影响,若有,如何利用变化前的最短路得到改变后的最短路,即:利用网络的独特优势,建立最短路问题的灵敏度分析算法.     

最短路问题的Auction算法在无圈网络中的改进

提出了Auction算法在无圈网络中的一种改进．在改进的新算法中，采取了新的推进(extension)方式，从而成功地降低了算法的复杂性．改进后算法的复杂性为O(m)，此处m是图的弧数．     

时间依赖的交通网络模型及最短路径算法

为了解决传统最短路径算法不能很好地应用于实时公交查询系统的问题,研究了时间依赖的交通网络模型和理论基础,提出了一种时间依赖的最短路径算法,以此算法为基础实现了南京市公交查询系统。实践证明,时间依赖的交通网络模型能更好地反映实际交通网络的运行情况。