共查询到18条相似文献，搜索用时 109 毫秒
1.
本文构建了圆柱和圆台表面最短路径的函数模型,给出了最短路径的几何解释,论证了圆柱表面最短路径问题,提出了一个基于数学实验的圆台表面最短路径的猜想. 相似文献
2.
在导航过程中,当最短路径道路上有拥挤、堵塞或中断的情况发生时,利用Dijkstra最短路径算法中的最短路径长度和前驱结点两个辅助向量数据,可迅速在其邻接结点中选择一条新的最短路径。实现了最短路径的动态调整,从而可以尽快地到达目的地。 相似文献
3.
研究机器人避障最短路径的问题.要求在一个区域中存在十二个障碍物,由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的最短路径.我们通过证明具有圆形限定区域的最短路径是由两部分组成的:一部分是平面上的自然最短路径(即直线段),另一部分是限定区域的部分边界(即圆弧),这两部分是相切的,互相连接的.依据这个结果,根据线性规划知识设定机器人的行走路径为目标函数,将所设变量的变化范围作为约束条件,最后用Lingo(11.0)软件求得目标函数的最小值,使得机器人沿最短路径到达目标点.建立了最优化模型,最短路径依次如下:O→A最短路径为:470.3636O→B最短路径为:853.1174O→C最短路径为:1092.8224O→A→B→C→O最短路径:2714.3069O→A最短时间为:96.01764 相似文献
4.
描述了使用Floyd算法求最短路径的三种路径重构的方法：正向追踪算法、递归追踪算法、反向追踪算法。它们都是通过记录最短路径中某个顶点来实现路径重构,区别在于它们记录了最短路径中不同的中间顶点,从而需要使用不同的策略来输出路径。 相似文献
5.
张蓉 《天津职业院校联合学报》2015,(2):47-52
本文针对机器人避障的最短路径和最短时间路径问题建立优化模型,主要研究机器人行走过程中如何避开障碍物到达目标点的最短路径及最短时间路径。经分析可得,最短路径一定是由线和圆弧组成的。为方便计算,把较长的路径拆分为较简单的线圆结构图。依据这种方法,无论多复杂的路径图都可以拆分为这种相对简单的线圆结构来求解。对于最短路径问题,可通过穷举法找出可行路径,再用AutoCAD作出精确的路径图选出相对较短的路径,并利用Mathematic计算出路径长度,经计算可得机器人路障的最短路程。对于最短时间问题,由于转弯的半径和弧的圆心是未知的,路径是无法确定的,所以建立了非线性规划的优化模型,用LINGO软件求解得到。 相似文献
6.
受顶点数限制的最短路径计数问题在复杂性网络的社区识别、介数计算等方面有重要应用,但目前对其研究较少。Bellman算法能有效解决边带有负权且无负圈的最短路径问题,但对结点数受限定的最短路径的计数问题,直接用Bellman公式进行求解,则存在重复计数的问题。对Bellman递推关系式进行改进,建立新的求结点数受限制的最短路径的递推关系式和求结点数受限制的最短路径数目的递推关系式,从而给出了结点数受限定的最短路径计数问题的一种求解算法,并验证了其正确性。 相似文献
7.
图论中的最短路径问题在计算机中有着广泛的应用,特别是城市地理信息系统中很多城市道路网相关问题均可纳入最短路径问题的范畴之中。文章首先对几种常见最短路径的算法进行介绍,重点分析了基于城市应急系统中救援路径的A＊算法,并给出了算法实现。 相似文献
8.
9.
唐金文 《渭南师范学院学报》2006,21(2):51-54
在GlS领域,对最短路径搜索问题的算法研究和应用属Dijkstra算法.但是,Dijkstra算法通常仅研究计算一条最短路径.文章通过对Dijkstra原始算法的基本原理和步骤进行分析研究,做如下改进:1、从已通过顶点集到未通过顶点集的可能存在的多条最短路径中,不丢弃任何一条最短路径.而Dijkstra原始算法仅在可能存在的多条最短路径中任选其中一条即可;2、Dijkstra算法的每一步骤,不仅要求路径最短,同时还要求经过的顶点最少,从而求出被原始算法忽略的所有可能存在的最短路径;结果最终可以求出带权图中一起始点到其余顶点的所有最段路径. 相似文献
10.
本文从城市道路网络的实际特点出发，对城市电子地图的道路网进行网络分析，将最佳路径搜索问题转化为图论中的最短路径搜索问题，通过对最短路径搜索算法的分析，实现了一种求解城市道路网两点间最短路径的算法，将求城市道路网两点间最短路径目标约束转化为求最短路问题，随之建立最短路模型，并描述了用Matlab程序进行求解的过程。最后用实例验证了模型和算法的可用性。 相似文献
11.
12.
王新成 《温州职业技术学院学报》2014,(1):54-56
在存在障碍物的平面场景中,规划机器人由出发点到达目标点的最短路径和最短时间路径,可大大提高机器人的工作效率.机器人通过障碍物区域的部分边界,在线圆相切的情形下,建立机器人避障的最短路径和最短时间路径的规划模型,并采用Mathematcia7.0数学软件可得到机器人避障问题的最优解. 相似文献
13.
张祥波 《四川职业技术学院学报》2012,22(4):150-152
本文证明了赋权完全图Kn中关于最短H圈与最短H通路的两个定理,由此得到了它们的一个上确界.通过探讨最短H圈的有关性质,得到了关于最短H通路的对偶性结论,文末研究了它们之间的关系,使之更接近最优解. 相似文献
14.
摘要：本文要解决机器人避障行走的最短路径和最短时问问题．主要研究了在一个区域中有12个不同形状的小区域是机器人不能与之发生碰撞的障碍物,机器人从区域中的0点出发避开各种障碍物到达最终目标点的最短路径和最短时问数学模型．我们对问题1采用初等数学中的解析几何和三角函数知识,建立基本线圆结构求路径的数学模型,分内公切线、外公切线和经过定点的动圆三种情形讨论,对动圆我们采用将圆形障碍物的半径增加r,或把切线转角用由定圆心到定点连线的夹角近似代替,都分解为基本线圆结构数学模型来求解,用穷举法结合matlab编程算出可能的走法的总路径的最小值．对问题2我们采用建立时间与行走转弯半径的数学模型,用搜索法结合matlab编程,求出最短时间．结果是：㈣的最短路径为471．0372．D→B的最短路径为858．6000．O→C的最短路径为1093．7000．O→A→B→C→O的最短路径为2783．7000O→A．的最短时间为94．5649． 相似文献
15.
基于最短路径优化问题Dijkstra算法程序的设计和实现 总被引：1，自引：0，他引：1
在九十年代公认的求最短路径的最好的算法是由E.W.Dijkstra于1959年提出的标号算法,此算法可以很好地解决求最短路径问题,但是该算法采用手工求解,计算量大且很繁琐.本文在此算法的基础上采用矩阵运算的方法,从而实现了完全应用程序求解,在很大程度上解决了上述问题所遇到的难点,使求最短路径和最短距离这两个较复杂的问题变得非常容易求解. 相似文献
16.
探索使用不确定理论中的期望值模型处理最短路径问题,将网络中有向边的权值描述为不确定变量,提出了利用99表表示的期望值简化最短路径通用模型,从而把模型直接转化为确定的最短路径问题模型,用传统方法如Dijkstra算法等即可求解.最后通过算例证明了模型的可行性与有效性. 相似文献
17.
陈恩水 《南通职业大学学报》2013,(3):53-57
研究机器人避障行走问题,即在一个区域中存在多个障碍物,由出发点到不同的终点,根据机器人的运动特点精确设计最短路径或最短时间的路径。建立了一次避障最短路长模型,得到路径长度和切点坐标的计算公式;提供了将多次避障转化为一次避障的方法以及路径选择的一般过程。针对4个不同特性的最短路径问题实施计算,给出了数值结果;针对1个最短时间路径问题,建立了时间优化模型。并运用MATLAB获得数值结果。 相似文献
18.
数据结构中最短路径算法的实现 总被引：1，自引：0，他引：1
最短路径算法种类繁多,比较有名的算法包括:Dijkstra算法、Ford算法、Floyd算法、Moore算法、A*算法、K值算法,而即使同一种算法也有多种不同的实现方式。本文介绍了求最短路径的Dijkstra算法的设计思路及Visual C 语言编程实现。实验表明:该算法能高效地求出一个顶点到其它各顶点的所有最短路径。 相似文献