鲁 毅，高永平，龙江腾

(东华理工大学 信息工程学院，江西 南昌 330013)

0 引言

随着工业化社会的发展，货物的搬运和输送成为重要的问题，其中移动机器人技术得到了极大的关注[1]，移动机器人技术可以极大地提高货物的运输能力，使得货物的运输更加的自动化，而在移动机器人技术中，机器人路径规划算法[2]一直是研究重点，路径规划算法有Dijkstra算法[3]，BFS算法[4]，A*算法[5]等，Dijkstra算法可以搜索到一条最优路径，但是搜索效率太低，BFS算法搜索效率很高，但是不一定能搜索到一条最优路径，A*算法结合了Dijkstra算法和BFS算法的优点[6]，但是也存在一些缺点，因此，本文提出改进A*算法，既能寻找到一条最优路径，而且搜索效率也比较高。

1 传统寻路算法

1.1 Dijkstra算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法[7]，用于计算从起点到其他各顶点的最短距离。主要是从起点开始不断向外搜索，直到搜索到终点结束。算法原理：假设一个带权有向图G，将其分成A，B两个集合，其中A集合中存放的是已访问顶点和其最短路径值，B集合中存放的是未访问的顶点，算法步骤如下：

1)初始时，将起点S放在集合A中，集合B中存放其他所有顶点和起点S到其他顶点的距离。

2)从集合B中选取到起点S的最短距离的顶点a，并将顶点a加入到集合A中，同时从集合B中删除顶点a.

3)以顶点a为中间点，更新集合B中各个顶点到起点S的距离。

4)循环执行步骤2和3，直到遍历完图中所有的顶点为止。

Dijkstra算法是一种盲目式搜索算法，所以搜索效率较低，对于n个节点的图，计算起点到其他各节点的最短距离，算法的时间复杂度为O(n2)，因此，在大型地图中寻路效率比较低。……