P2P网络最可信路径算法

针对分布式环境下P2P网络的特点,以及间接获取信息时的可信性,定义了间接获取信息时两个节点之间路径可信度的相关概念,提出了两个节点之间的最可信路径算法、最小可信路径算法,量化了最可信和最小可信路径的可信度,量化了两个节点之间传输消息时可信度的分布区间,分析了最可信和最小可信路径算法具有多项式的时间复杂度.通过典型应用,验证了最短路径并非最可信路径,最可信路径选择具有重要的使用价值.特别是在大规模分布式环境中,为人们从最可信路径获取信息提供了保障.     

大规模多模式交通网络构建方法对比分析

针对目前大规模多模式交通网络构建方法对比研究的不足,对不同构建方法在计算效率与结果上的差异展开研究.首先,在6个不同规模公交网络上对比了公交区段和超路径2种网络表达方法对扩展网络规模的影响.其次,提出了公共交通站点与路网匹配连接方法,并使用节点压缩方法创建衔接网络.最后,在大规模多模式交通网络上,计算了10万对出租车载客行程OD的3种最短路径,并将其广义时间费用与实际出租车行程比较.研究结果表明：在计算耗时方面,路线>超路径>简单路径;在平均最短路径费用方面,简单路径>路线>超路径;与实际出租车行程相比,简单路径、路线和超路径最短路径费用更低的OD对比例分别为39.21%、41.29%和42.83%.     

应用最小生成树构造最优通信网

信息社会中，通信网络建设在快速发展，建设费用昂贵，如何使建设线路最短，从而降低建设成本成为国家关注的重点。该文针对建设路径最短的问题，应用数据结构中的最小生成树理论引入了与最小生成树相关的基本概念与定理，分析了通信网络线路与最小生成树的关系，最后，应用最小生成树算法解决了通信网络线路最短的实际问题。     

具有线性路阻函数的路径流量分配效率

用户均衡和系统最优是两种最基本的流量分配方式,前者是用户出行时追求费用最小,而不考虑其他用户如何选择路径;后者是对所有用户进行管制,追求网络上总费用最小。针对系统最优时部分路径上费用过大的问题,讨论了路阻函数为线性时,同一路径上两种不同分配方式费用的大小关系;同时,定义了重载路径和轻载路径,并给出两种路径的判别方法。     

大型网络优化管理中协调信息的传递路由

对大规模网络分解—协调过程中产生的协调信息在网络中的传递问题进行了研究,根据两种不同的优化目标：总的通信代价最小和各代理的最大等待时间最小,提出了两种不同的中央代理选取原则：中央代理到其它代理的最短路径总长和中央代理按最短路径发信息到其它代理所用时间是所有可能方案中的最小者,并分别给出确定协调信息传递路径的算法,最后给出了一个算例说明运用本文中提出的两个路由算法选取最佳中央代理的过程。     

基于最短路径的求解与创新

笔者于2012年5月参加西北工业大学数模竞赛,试题详见问题充数部分。问题一：把矩形框架的四个顶点,八个入口点和花园内部四个交叉点总共是十六个点都看做是顶点,构造道路建设费用矩阵B,求得连接这十六个点的最小生成树,接下来,用迪杰斯特拉算法加以修改和完善（简述—下方法：按P1,P2……的先后顺序,用迪杰斯特拉算法,求得总述中11对入口之间最短路径,若该路径小于这两个入口直线距离的1．4倍,就保留这个路径,若某两个入口之间没有这样的路径,就通过已保留的路径,结合线性规划的方法,构建新的路径,使得该两入口之间存在小于其直线距离的1．4倍的路径,且使得新构建的路径之和尽量的小）使得总述中所说的11对入口之间存在路径总长不大于直线距离的1．4倍的道路,即为最佳路径设计。最终得到符合题意的最短路径为394．56m。问题二：在问题1得到方案的基础上进行优化,用Floyd算法求解出任意两个路口仅通过矩形图边的最短路径矩阵Df=（dfij）n＊n,用求出的最短路径dfjj与vj,vj,两点的直接连接的距离d,的1．4倍做比较得出不可周向矩阵T=（tij）n＊n,并用matlab程序计算出矩阵T,最终得到符合题意的最短鲒径为358．62m。针对问题三：在问题2中,道路有经过湖面的,这不符合第三问的要求,因此,在假设第二问的解是最优的情况下,绕过湖面所在地,求出其长度最小的道路设计,模型仍沿用第二问的原理,在第二问的基础上求解出满足题意的解,最终得到符合题意的最短路径为360．7149m。     

交通网络最优安全路径选择模型与算法

针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.     

黑龙江省旅游路线优化设计

讨论了游遍黑龙江省30个旅游景点最短路径问题。将30个景点之间的关系转化为图论问题,建立赋权图,利用蚁群算法来解决最短路径问题,并用Matlab软件编程进行蚁群算法和改进的Dijkstra算法实现和仿真。同时最短路径问题也可以看成在赋权图上找到一个权最小的Hamilton回路。从而得到黑龙江省最优旅游路线。     

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

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

网络图任意两点间最短路径问题的计算机实现

最短路径问题是网络分析中的一个最基本的问题,著名的旅行推销员问题,中国邮路问题,运输网络的最小费用最大流问题及最小根树问题等都建立在此问题的基础上。本文用集合并的思想解决了Floyd算法中路径寻求在计算机上实现的问题,并给出了负回路的判别方法,从而也解决了中国邮路、旅行推销员等相关问题的计算机实现问题。     

关于动态最短路问题的探讨

主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。     

基于优化调度模型的焦炉推焦计划编制方法

针对焦炉正常和异常2种工况,提出基于优化调度模型的焦炉作业计划编制方案。在正常工况下,建立使设备总的机械行程最短、出焦延迟时间最短和检修时间足够长的优化调度模型;在异常工况下,通过将乱笺炉号、事故状态、病号炉3种情况归结为乱笺炉号的情况,建立系统实现目标不变,以恢复过程中所有小循环总费用最小为目标的异常工况下的优化调度模型。针对2种优化调度模型,分别提出正常工况下的焦炉作业计划编排方法和基于Dijkstra算法的异常工况焦炉作业计划编排方法,该方法将实际的乱笺问题转化为最短路径问题。仿真实验结果表明,采用该方法实现了推焦计划的自动编制,提高了生产效率和企业的经济效益,证明该方法是有效的。     

基于最短路搜索的多路径公交客流分配模型研究

提出了一种首先采用最短路算法搜索有效路径集，再根据有效路径的广义费用，由改进的Logit模型确定每条有效路径的选择概率，进而计算每条线路客流量的公交客流分配模型。其中，任意两交通区之间的有效路径集是以换乘次数最少为准则，通过对不同选择情况下公交路网进行最短路搜索而获取。该模型既体现了乘客的费用最小的选择心理，又反映了出行线路多样性的实际情况，而且算法简单、有效。初步实践证明，具有较强的实用性。     

基于道路繁忙程度下的城市交通路径选择算法

针对城市公交自助查询问题,提出了一种基于交通繁忙程度下的公交选择算法。首先构建基于繁忙程度权重的公交网络权值矩阵。然后针对四种不同的公交地铁混合线路对权值矩阵进行修正。最后在此基础上建立三种实用的双目标动态模型:最少换乘下的最短时间、一定换乘忍耐下的最短时间、一定换乘忍耐下的最少花费。实验表明,该模型是解决基于整个交通网络系统不同交通繁忙程度下,用户出行选择的个体最优选择的有效途径。     

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

时变最短路问题是最短路问题的一个推广.假设图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)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

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

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

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

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

一个低代价最短路径树算法

为了对最短路径树SPT（Shortest Path Tree）进行代价优化，提出了路径驱动的思想，主要是生成SPT时通过路径节点共享的方式来优化其总体代价。基于这个思想进行搜索过程优化，设计了一个路径节点驱动的低代价最短路径树算法LCSPT（Low—cost Shortest Path Tree Algorithm），这个算法生成的组播树在保证最短路径的同时降低了整个树的总体代价。仿真实验表明：LCSPT算法不但能正确地构造最短路径树，而且其构造的SPT总体代价与其它同类算法相比得到了最大限度的优化。     

机器人避障行走最优路径的MATLAB求解

本文主要研究在一个存在十二个障碍物(要求目标点与障碍物的距离至少超过10个单位)的区域中,机器人如何寻找最短路径和最短时间路径的问题,利用Matlab软件强大的计算和绘图功能,对机器人避障行走路线的最短路径和最短时间路径分别给出了两种不求解方法。     

一类网络容量扩充问题

给定一个连通网络,找两点之间的最短路,作为两点之间的流量路径。每条路径都有一定的需求,网络中每条边的容量至少为经过该边的所有路径的需求之和,若某条边的容量小于经过该边的所有路径的需求之和,则需要对其容量进行扩充。每种扩充方案的扩充费用是关于扩充容量的函数。本文给出解决该问题的一个多项式时间算法,使得各边容量达到需求,且总的扩充费用最小。