对于路径规划问题的一些思考

问题

路径规划问题，输入一个出发点和目的地，输出一条从出发点到达目的地的最小代价的路径。 我们需要达到的目的就是如何能够快速有效找到这条路径，或者在快速找到路径和最小代价路径中做一个权衡。 全文接下的路径规划问题都特指实际生活中的路径规划问题，这类问题的特点就是，移动的代价永远是正的（由于距离不可能为负）。

问题的表示

路径规划问题来源于现实，而现实中的地图（一张图片）往往需要经过处理才能正确被计算机程序所高效使用。

对于地图APP而言，这一部分可能通过人工的（或者是通过AI算法）地图数据整理，将地图中的道路信息标注出来， 这样，一个普通意义上的地图，就能够抽象为计算机中的图，即节点和边的集合。其中，道路就是不同的边，联通多条道路的路口就是不同的节点。至此，可以采用图中的路径规划算法（如迪杰斯特拉算法）进行路径规划。

前者的做法，是根据人类社会的道路交通体系来进行抽象。对于机器人（或其他非人物种）而言，在实际的路径规划中，可能不存在预先设定好的道路，或者是遵循一定的交通规则。在没有障碍物的情况下，在一个2D平面中，可以通过“两点的连线”确定一条最短路径。也就是说，在这种情况下，确定一条最短路径最重要的影响因素就是障碍物了。采用对一个2D平面进行细分，分成多个更小的区域，将可通行区域和障碍物区域进行分离，也是一种常见的方法。

表示图的数据结构往往有２种，

  1. 邻接矩阵 (Ajacenct matrix)
  2. 邻接表 (Ajacency list)