共查询到20条相似文献，搜索用时 93 毫秒
1.
文章针对Dijkstra和Floyd算法特点及在智能运输中的特点,将两种算法结合起来,形成求解物流配送中两点间最短路径的优化算法-混合算法.该方法用Floyd计算多对顶点之间的最短路径,在路径中少数顶点之间的邻接关系发生变化时,利用Dijkstra计算这些顶点之间的最短路径,加上其余部分路径就得到该图中各对顶点之间的新的最短路径,在约束条件下最终求出各点间最短路径.实验证明,混合算法比Dijkstra及Floyd效率提高11％-20％.本文研究结果可对物流配送中最短路径的选择有所帮助. 相似文献
2.
3.
本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度.仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15％～25％,当节点越多这种减少越明显,可提高搜索路径的实时性. 相似文献
4.
A^＊算法的改进及其在路径规划中的应用 总被引：2，自引：0，他引：2
A*算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要.本文针对路径规划问题,对A*算法作了以下改进:一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题;二是利用k-d树空间索引结构,动态加载节点信息,减小内存使用空间.实验结果表明,改进后的A*算法的搜索效率得到了明显的提高. 相似文献
5.
旅行商路径优化问题是经典的网络分析问题之一。由于旅行商问题具有NP Hard特性,主要通过智能优化方法或启发式算法来获得近似最优解。然而,单一智能优化方法存在运算量过大、参数选择苛刻,对初值依赖性强等缺陷,很难快速实现全局优化。结合多种优化机制和邻域搜索结构设计混合启发式算法可在一定程度上解决这一问题。本文结合遗传算法的全局寻优能力和禁忌搜索的记忆功能,设计实现了一种基于分散集中策略的禁忌遗传算法,即采用遗传变异算子作为分散策略构造邻域,开辟新的搜索空间,有效提升获得全局最优解的概率;将禁忌搜索作为集中策略进行局部寻优,避免迂回探测,充分体现禁忌搜索较强的“爬山”能力,并通过实际交通网络和不同规模的节点集合,从求解精度、稳定性和效率三个方面对算法进行了评价。结果表明,本文提出的交通网络旅行商路径优化的禁忌遗传算法平均求解精度比禁忌搜索算法提高了9%,略优于ArcGIS;当与ArcGIS求解的TSP路径长度差异在1%以内时,禁忌搜索算法已经难以获得对应精度的TSP路径,而禁忌遗传算法效率比遗传算法提高了50%。且禁忌遗传算法具有很好的并行化潜力。 相似文献
6.
快速Dijkstra最短路径优化算法的实现 总被引：12，自引：1，他引：12
在分析已有Dijkstra算法的基础上,提出快速Dijkstra最短路径优化算法.该算法是将提高时间效率放在第一位,以十字链表结构记录顶点(Vertex)和边(Edge)为基础,采用顶点分区和记录绝对地址来优化Dijkstra算法的方法. 相似文献
7.
最短路径分析是物流配送最基本的网络分析,等价于图论中的结点间求解最短路径的问题。本文在研究迪杰斯特拉算法基础上,基于组合技术对该算法进行改进。首先利用图的节点——弧段联合结构;其次搜索方法改为双向搜索;最后对扫描点按其所在边的权值进行排列。实验表明改进算法运行效率较高。 相似文献
8.
基于启发式图搜索的遥感影像道路半自动提取 总被引：1，自引：0，他引：1
启发式图搜索法用于线状目标识别的原理是:用图结构表示边缘点和边缘段,根据启发函数计算顶点权值,在图的路径上建立相应的代价函数,通过在图中搜索对应的最小代价的通道以找到最优路径.图搜索法是一种全局最优方法,它在受噪声影响较大时效果仍然较好.文中使用了启发式图搜索法(A*算法)实现了道路的半自动跟踪.它的基本思路是:首先利用自适应平滑滤波算子进行道路信息增强,然后对传统的道路数学模型进行了进一步的扩展,突出了对道路几何特性和辐射特性的描述,并依此构建图搜索的代价函数,实现了基于启发式图搜索法A*算法的道路半自动跟踪.经实验证明,该方法进行遥感影像的道路半自动提取效果较好. 相似文献
9.
10.
GIS网络分析中最短路径的实现 总被引：9，自引：1，他引：8
本文提出了一种基于矢量角度的最短路径搜索算法,设计出一种类似于面向对象的数据存储结构来存储网络图中的节点及弧段对象,在最短路径的搜索上引入矢量夹角标量值作为搜索因子,充分利用了网络图中各点元素和线元素间的拓扑关系,提高了搜索的趋势性,同时还考虑了各弧段的长度值(或权值),较好的将网络图中对象的空间信息和属性信息相结合。 相似文献
11.
An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning 总被引：5，自引：0，他引：5
Human beings' intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers' choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks. 相似文献
12.
Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic, so as to improve running efficiency and suitability of shortest path algorithm for traffic network. The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path. It is argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors difficult to expect or quantify influence the drivers’ choice greatly. It makes the drivers prefer choosing a less shortest, but more reliable or flexible path to travel on. The presented optimum path algorithm, in addition to the improvement of the running efficiency of shortest path algorithms up to several times, reduces the emergence of those factors, conforms to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, it does not require the completeness of networks in the lowest hierachy and the applicability and fault tolerance of the algorithm have improved. The experiment result shows the advantages of the presented algorithm. The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks. 相似文献
13.
Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled. However, the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost, and not the path simplicity. To balance these factors, this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy. The proposed algorithm started searching from a starting point, and expanded layer by layer through searching zero-level reachable points until the endpoint is found, and then deleted unnecessary points in the reverse direction. The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points, and form a fewest-turn-path graph (G*). After that, a classic Dijkstra shortest path algorithm was executed on the G* to obtain a fewest-turn-and-shortest path. Comparing with the shortest path in Baidu map, the algorithm in this work has less than half of the turns but the nearly same length. The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research. 相似文献
14.
15.
最短路径分析是GIS空间分析中最基本和最关键的问题,Dijkstra算法是有效解决该问题的理论基础。本文基于GIS空间分析特征,从数据存储结构、搜索技术及网络算法本身等方面对传统Dijkstra算法进行了优化与改进,并对该算法在交通导航系统中的应用进行了探讨。 相似文献
16.
17.
18.
针对障碍环境中路径规划存在的运算效率低、最短路径遗失问题,根据凸包边界在构建空间网络模型过程中具有快速高效的特点,结合路径与障碍物的相对位置关系,提出了一种基于双侧凸包扩张模型的路径快速规划算法.该算法在对凸包边界算法进行改进的基础上,提取左右侧关联障碍物的凸包边界作为网络模型,利用最短路径算法搜寻目标路径,并在Arc... 相似文献
19.