求解最短路径问题的DNA动态规划算法

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。     

一种基于Dijkstra算法的三角网格地表模型算法

对二维地表模型运用Dijkstra算法求解最短路径时,为了减少计算量,需要对模型进行简化后,才开始进行Dijkstra算法的求解,所以结果并不符合实际地表情况。不在模型上进行任何简化,而是直接在模型上划分三角网格来处理最原始的模型。然后用基于Dijkstra算法和矢量夹角的三角网格地表模型算法求解最短路径。通过此算法完成了一个实例的最短路径求解。结果表明,采用文中算法所得到的结果符合Dijkstra算法求得的路径和实际情况,而复杂度并没有因为未简化模型而大幅上升,并且算法具有效率高、复杂度低、稳定性好等优点。     

基于极小代数赋权有向图最短路径求解算法

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.     

格上困难问题求解的智能筛选算法及测试

在总结格密码困难问题发展和求解中关键理论与技术的基础上,从渐进最短向量问题(approx-SVP)入手,对比分析了经典格基约减算法的优缺点,重点研究了其求解推进过程中的关键技术和算法性能瓶颈,归纳了进行格基约减进而求解渐进最短向量问题的一般步骤。在经典的格向量假设基础上,提出了格向量智能筛选模型。通过优化向量选择的路径等方法,设计了基于最优路径分布的智能筛选算法、逆向求解智能验证算法和近似最短向量智能筛选算法三种求解最短向量问题(SVP)的算法,测试结果表明算法在求解格上困难问题上有效。     

双向链表人口迁移算法

最短路径搜索是路径分析中的热点问题.将双向链表和人口迁移算法的智能进化体制相结合,提出一种新的启发式智能仿生优化算法——双向链表人口迁移算法,并用于求解最短路径问题.仿真实验结果表明：双向链表人口迁移算法求解最短路径搜索问题是可行、有效的.     

最短路径问题的DNA算法

最短路径问题是在一个带权图的两个顶点之间找出一条具有最小权和路径的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间内才能得到解决,本文基于分子生物技术并利用Adleman-Lipton模型给出最短路径问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对个城市的最短路径问题,首先将它视为一个具有顶点和边的图,并将顶点,边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到最短路径问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计以及在操作中巧妙的消除了路径途经城市数目不同的影响,能使我们在合理小的范围内寻找最短路径问题的解,较大地简化了问题的复杂度。     

大规模网络最短路径算法的优化及实现

求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题．在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法．初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80％,在耗费的存储空间上减少了将近一倍．     

求最短路径问题的自适应路由遗传优化算法的设计与实现

从最短路径问题的研究背景、最短路径问题概述、求解最短路径问题的自适应路由遗传优化算法的设计及其实现等方面提出了一种新的求解最短路径问题的自适应路由遗传优化算法,实验仿真比较了该算法与Dijkstra算法的路由过程、算法的收敛性和执行的效率,结果初步证明该算法高效可行,尤其适合于大规模网络.     

移动机器人路径规划的混合差分进化算法

针对移动机器人无碰撞最短路径规划问题,提出人工势场-差分进化混合算法。建立移动机器人全局环境信息已知的无碰撞路径模型,采用差分进化算法规划机器人最优路径。针对差分进化算法变异因子,采用适应性调节策略;针对差分进化算法在交叉操作过程中的不可行解,提出人工势场法不可行路径修正策略,提高算法寻求最短路径的有效性。实验结果表明,所提混合算法的收敛速度和求解质量均优于基本差分进化算法,实现了移动机器人的无碰撞路径问题的有效求解。     

多种运输方式模型优化及求解

对可阶段化运输网络，提出了将路径选择与交通运输方式相结合的组合优化模型．通过虚拟一个运输网络，转化为一个与原问题等价的最短路径问题，并设计了相应的遗传算法对其求解，通过实例计算表明，该算法对该问题是可行和有效的．     

带有模糊约束最短路问题的数学模型及算法

针对带有模糊约束的最短路问题,在其模糊线性规划模型的基础上,利用容差法和罚函数法对该模型进行转化,得到了与原模型具有相同最优解与最优值的转化模型,并提出一种修正的萤火虫算法求解转化模型.数值算例结果表明,该模型与算法对求解带有模糊约束的最短路问题有效.     

含负权有向图最短路问题的一种新算法

Dijkstra算法是求解最短路问题的一种经典算法，但是它的缺点是不能用来求解含有负权的最短路问题。本文对图论中含有负权的最短路问题进行研究，提出了一种新算法，将含有负权的最短路问题先转化为不含负权的最短路问题，最后再利用Dijkstra算法求解，并用实例验证该算法的有效性，具有一定的现实意义。     

基于粘贴系统求解无向图最短路径问题的DNA计算模型

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。     

DNA芯片在最短公共超串问题中的应用

DNA芯片技术是近年来生命科学与信息科学的新兴研究领域，其突出特点在于它的高度并行性、多样化、微型化以及自动化，最短公共超串问题是计算机科学中的NP-完全问题．笔者在DNA计算和DNA芯片基础上，提出了基于DNA芯片解决最短公共超串问题的DNA计算新模型．该模型可对信息高度并行获取，并且具有操作易自动化的优点．     

非可加平衡交通分配问题的列生成算法

为求解非可加平衡交通分配问题,基于列生成算法基本框架,采用K最短路算法生成需要的路径,采用幂罚函数法求解平衡路径流问题,提出一种新的算法,并进行数值模拟,将算法用于求解含路径特定行驶费用和路段容量随机降级下的路径行驶预算2类非可加费用情形。结果表明,所提出的算法能有效求解非可加平衡交通分配问题,并获得高精度的满足 Wardrop用户平衡准则的平衡路径流(误差E≤10-9),即对于每一个O D对,流量大于0的路径的行驶费用几乎都相等,且等于最小行驶费用。     

指派问题与最短路径问题的相互关系

尽管指派问题与最短路径问题是运筹学中的经典问题,也为大家所共知;但是,我们却很少知道这两个问题间的相互关系。本文揭示了两问题间的内在联系,进而使我们有可能利用指派问题的匈亚利法来解决最短路径问题。反之,亦可使用最短路径的解决问题方法来处理相应的指派问题。     

面向动态时间弯曲距离的灰关联聚类方法研究

灰色关联聚类是灰色系统分析的重要研究领域.现有的灰关联聚类方法在处理不同长度序列数据时,通常采用补齐或删除数据方式进行处理,增加了系统的不确定性.在动态时间弯曲距离基础上,提出了一种新的灰关联聚类方法,通过计算序列间距离矩阵的最短路径来度量相似程度,最终完成序列的灰关联聚类.该方法无需对序列数据进行人工干预,具有更强的鲁棒性.实验结果表明,在处理不同长度数据序列时,聚类结果更为准确.     

基于遗传算法的汽车式移动机器人路径规划方法

对文题进行了数学描述，提出了一种基于遗传算法的汽车式移动机器人最短距离路径规划新方法，探索了解决非完整系统路径规划问题的新途径．利用经改装的遥控汽车模型进行了路径规划实验，取得了令人满意的实验结果     

公共交通路网描述方法及诱导模型设计

在采用传统的公共交通路网描述方法的公交网络中,会出现大量两节点间有多条同向边的情况,这使得无法求解公交网络中的最短路径问题.有鉴于此,文中提出了一种新的公交路网描述方法,该方法克服了以上问题,使得所有经典的最短路径算法都能够用于公交诱导系统.在此基础上设计了3个单目标和一个多目标公交诱导模型来满足不同乘客的需求,同时对文中提出的描述方法和模型的有效性进行了证明.最后,以广州市的公交线路网络为例,对所提出的公交诱导模型进行了试验,结果表明所提出的方法和模型是十分有效的.     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.