使用Dijkstra算法构建可见性图的最短路径方法

"本文介绍了计算流体力学与传热学中的一种特定算法——构造可见性图，用于求解最短路径问题。" 在计算几何领域，可见性图是一种用于表示平面上一组互不相交的多边形障碍物之间可视关系的图。在【标题】"构造可见性图-计算流体力学与传热学 陶文全"中，讨论的核心是如何高效地构建这样的图以找到从起点`pstart`到终点`pgoal`的最短路径。【描述】中提到了Dijkstra算法的应用，这是一种解决图中单源最短路径问题的经典算法。在障碍物数量为n的情况下，Dijkstra算法的复杂度为O(n^2)。 然而，直接应用Dijkstra算法来构建可见性图会导致较高的时间复杂度，即O(n^2logn)。这是因为每个障碍物的边需要与其他所有障碍物的边进行交互检查，导致潜在的O(n^2)操作，再加上Dijkstra算法本身的O(logn)时间。【描述】中提出的定理15.3表明，可以在O(n^2logn)的时间内找到穿越障碍物的最短路径。 为了降低复杂度，文章提出了名为`VISIBILITYGRAPH(S)`的算法。这个算法首先初始化一个空图`G`，然后逐个处理图中的顶点，检查它们与其他顶点的可见性。通过`VISIBILITYVERTICES`子过程，对于每一个顶点v，找出与其可见的所有顶点w，并将(v, w)添加到图的边集中。这样，算法每次仅关注一个顶点，避免了对所有顶点对进行直截了当的测试，从而减少了计算量。 【标签】中的"计算几何 算法 邓俊辉 第三版"表明，这些内容可能源于邓俊辉翻译的《计算几何：算法与应用》的第三版。这本书是计算几何领域的经典教材，涵盖了多种几何算法，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位和Voronoi图等。 【部分内容】引用了另一本计算几何著作，作者为Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars，书中涉及线段求交、多边形三角剖分、线性规划等主题，进一步证明了在计算几何中解决这些问题的广泛性和重要性。 构造可见性图是计算流体力学和传热学中解决路径规划问题的关键技术，它涉及到计算几何的算法，特别是最短路径问题的优化和效率提升。这些知识对于理解复杂环境中的路径搜索和优化问题具有重要意义。