基于自动机的迷宫路径规划求解算法优化

汤 伟，赵 静，古 婵

（陕西科技大学电气与控制工程学院，陕西西安 710021）

迷宫问题一直是数据结构和图形学领域的经典问题［1］，其求解的方法是从入口到出口的多条路径中找寻一条最短路径，即最优路径。传统迷宫的求解有深度优先搜索、广度优先搜索［2］等算法，该类方法虽应用广泛，但存在着许多不足。如深度优先搜索［3－4］是通过堆栈实现的，虽能找到一条通路，但因其搜索方法的原因，不能保证是最短路径。广度优先搜索［5］是通过队列或列表来实现的，该方法虽然能找到最短通路，但需层层推进且需要的存储空间大、搜索时间长，从而导致效率较低。以上两种求解方法会随着迷宫规模及复杂度的增大，计算量呈指数性增加。随后出现了一些仿生智能算法［6］如遗传算法［7－8］、蚁群算法［9－11］、粒子群算法［12－13］等。遗传算法是通过设计编码、适应值函数、遗传操作和在演化过程中对基因进行“改良”［14］来实现。该算法可以求得迷宫的最短路径，但是否为最短路径还有待考证。蚁群算法是多只蚂蚁通过不断的自适应调整信息素协作完成，采用的是概率搜索的方法，需要较长的计算时间且容易出现停滞现象［15］。粒子群算法是一种基于群体协作的随机搜索算法，是对鸟类集群觅食以及鱼类集群行为的模仿［16］，该算法易陷入局部最优。仿生智能算法是用并行处理的方法来解决大规模问题，该类算法可以得到一个很好的解，但大多是近似最优解且是否为最短路径还有待理论考证。还有学者提出了A∗算法，它将启发式函数 BFS和常规 Dijkstra算法结合在一起［17－19］，是一种在工作空间中求解最短路径的全局搜索方法。A∗算法相较于传统算法寻路时间减少，相较于仿生智能算法，它能找到最优路径，但由于该算法自身的限制，存在冗余点多、内存开销大、寻路时间长、仅保留单条最短路径等的不足。

针对以上存在的不足，本文提出了一种基于自动机模型的求解方法。首先，在迷宫的可行路径上用自动机建模，并结合自动机结构特性进行节点简化。其次对简化后的模型求最短。最后通过MATLAB仿真，结果表明该算法不仅能够快速有效地求解迷宫最优路径，而且也解决了以往算法存在的不足，如传统迷宫耗时过长、冗余点过多等问题。

1 理论回顾

1.1 迷宫问题的描述

如图1所示，长为m宽为n的网格区域（1≤m≤10，1≤n≤10）表示迷宫，其中黑色网格表示墙，为不可行区域；白色网格表示通道，为可行区域。迷宫求解就是在可行区域的多条路径中寻找一条通路，移动方格最少的通路即最优路径。

图1 迷宫［20］

1.2 自动机

自动机［21］是描述正规语言的一种方法，它的特点是采用状态子集的可达性来定义语言。同时包含的状态和事件等基本要素可用来描述离散事件动态系统［22］（DEDS）。

自动机用五元组 G ＝ （Y，Σ，η，y0，Ym） 来表示，其中：Y为有限状态集合，y是 G的一个状态，∀y∈Y；Σ为有限事件集合；η为状态转移函数η：Y×Σ→Y；y0∈Y为初始状态；Ym∈Y为终态集。自动机G产生的语言L（G）定义为使状态转移函数η（σ，y0）有定义的输入符号串σ∈Σ的一个集合，也即

自动机G的标识的语言Lm（G）定义为使状态转移函数η（σ，y0）属于标识状态集Ym∈Y的输入符号串σ∈Σ的一个集合，也即

有限自动机G是整齐的，则需满足以下条件：

（1）有限状态集Y的任一状态均为从初态可达。

（2）有限自动机G产生的语言L（G）的任一符号串，均可构成自动机G的标识语言Lm（G）中某个符号串的前缀。

1.3 Dijkstra 算法

Dijkstra算法是一种典型的求单源最短路径算法，用于计算有向图中一个顶点到其他顶点的最短路径［23－24］。 该算法在求最短路径时，首先需要设置距离向量 d［］，保存路径的向量 p［］，d［］用于保存入口到分支节点的向量，p［］用于保存最短路径上某一分支点的前驱节点。传统算法通常只能求单条最短路径，而要求多条最短路径，则需让每一个节点都维护自己的前驱节点数组［25］。例如：对于点yi，在遇到距离相同的路径时，把yi在这条路径的前驱节点记录下来，而非抛弃或覆盖；在遇到更短的路径时，把yi的前驱点数组清空，存入新的前驱点。

求解最短路径的算法步骤是：

（1）初始化，集合S存放已经确定的最短路径，初始时只包含源点，即S＝ ｛y0｝，y0的距离为0。集合V包含除y0外的其他顶点。若y0与V中的yi有边，则顶点 yi对应的距离值 d［i］等于〈y0，yi〉 的权值，若 yi不是 y0的邻接点，则 〈yi，y0〉权值为∞。

（2）从集合V中选取一个距离y0最小的顶点yk，把yk加入集合S中，以yk为新的中间点，修改集合V中各顶点的距离。若从源点y0经过yk到顶点yi的距离小于原来y0到yi的距离，则修改y0到yi的距离值为 〈y0，yk〉 ＋ 〈yk，yi〉， 反之，则保持不变。

（3）重复步骤2直到所有顶点都包含在集合S中，则结束算法。

该算法是以某一顶点为中心向外层层扩展，直至搜索到所有节点的最短路径。但该算法存在以下两个问题：

（1）搜索时需遍历可走路径中的所有节点，但这些节点有很多都是冗余点，这就使得找出的路径存在很多不必要的拐点；

（2）遍历可行路径中的所有节点也会导致寻路时间过长、效率低等问题。

2 自动机建模

首先，对迷宫问题建模，若对所有块进行建模，会存在状态集过大、计算过于复杂的问题，因此只在迷宫中的可行块上建模。自动机为五元组，由Y状态集、Σ事件集、η状态转移函数、y0初始状态、Ym标识状态组成。可行块对应自动机的状态，可行块之间的移动对应自动机的事件。所以可使用自动机建模，在计算迷宫最优路径的长短时需要把距离可视化。因此，把权值w引入自动机模型中，自动机用六元组 G ＝ （Y，Σ，η，w，y0，Ym） 表示。 其中，w 是可加的，w：（yi，yj） → N＋表示驱动状态转移所需要的成本。用J（w）表示某一段路径的权重，定义如下

本文针对图1所示的迷宫用六元组自动机G＝（Y，Σ，η，w，y0，Ym） 建模。 首先找到迷宫的入口和出口，设置为初始状态y0和标识状态ym。 剩余的可行块按照从左到右，从上到下1，2，3…进行编号，每个块用相应的状态y1，y2，y3…表示。状态和事件存在着以下的关系yi×Σ∈Y，若i和j（i≠j）为相邻状态，在两状态之间添加事件和权值，事件用bi，j表示，权值 w 为 1。 状态集合 Y ＝ ｛y0，y1，y2，…，ym｝， 事件集合 Σ ＝ ｛b0，1，b1，0，b1，2，b2，1，…｝，η：y0×y0，1→y1，y0∈Y为初始状态，ym∈Y为终止状态。建好的自动机模型如图2所示。

图2 自动机模型

3 简化自动机模型

3.1 无效状态的删除

传统的迷宫问题求解通常是对每个可行块进行依次搜索，在这些可行块组成的路径中，有些通道进入后需退回到进入块中的某一可行块进行再搜索，这就使得生成的路径部分重合，路径过长且不是最优路径。因此需要删除多余可行块，优化可行路径。可行块的删除对应状态节点的删除。

定义 1：对 ∀yi∈ Y， 必然 ∃bi－1，i＆bi，i－1∈ Σ，使 η（yi－1，bi－1，i） ＝ yi＆η（yi，bi，i－1） ＝ yi－1， 若 ∃bi，i＋1＆bi＋1，i∈ Σ， 使 η（yi，bi，i＋1） ＝ yi＋1＆η（yi＋1，bi＋1，i） ＝ yi，则yi称之为有效状态。若不满足则为无效状态。

有效状态组成有效路径，无效状态类似于死胡同，进入无效状态后，需退回进行再搜索。无效状态使得路径部分重叠，该类状态造成了路径存储空间及寻路时间的浪费。省略该状态也可行至终点，所以删除无效状态即可简化路径。无效状态的删除如算法1所示。

算法1：无效状态的删除

输入：自动机建好的模型

输出：有效路径组成的自动机模型

说明：（1）该算法是迭代算法。删除一个无效状态后，当前无效状态相邻的有效状态有可能变为无效状态。因此搜索无效状态相邻的状态进行再判断，直至路径中所有的无效状态全部删除。（2）该算法删除后的路径为有效路径。无效状态删除后，重复率下降，因此权重J（w）变小，存储空间变小及寻路时间变短。（3）无效状态即为冗余点。在寻找最优路径时，冗余点影响判断，浪费时间。该算法删除的无效状态，使得冗余点多的问题得到改善，寻找最优路径更加高效。

根据算法1对图2进行无效状态的删除。如状态y33经过事件b33，36到达状态y36，而状态y36有且只有事件b36，33可以进行转移，转移到状态y33。y36状态不满足定义1。因此，该状态为无效状态，对该状态及相连事件 b33，36、b36，33进行删除。 删除后搜索该状态相连的状态y33，发现该状态也变为无效状态，对其进行删除操作。无效状态全部删除后的自动机模型如图3所示。

图3 无效状态删除后的自动机模型

3.2 可替状态的删除

在无效状态删除后的基础上发现，存在一类分支状态，可以朝着两个方向进行搜索，搜索各经过一个不同的状态之后，可到达同一状态。组成的两条路径中开始状态、汇合状态及所经过的路径长度都相同，因此两条路径是重复路径，可对其中灵活性较差的路径进行删除且该路径的删除不会影响最优路径的求解。

定 义 2： 若 （∃s1＝ bj，j＋1＆bj＋1，j＋3∈ Σ∗） 使η（yj，s1） ＝ yj＋3， （∃s2＝ bj，j＋2＆bj＋2，j＋3∈ Σ∗） 使η（yj，s2） ＝yj＋3且 yj＋1≠ yj＋2， 则称 yj＋1，yj＋2为可替状态。

yj，yj＋1，yj＋3组成一条路径， yj，yj＋2，yj＋3组成另一条路径。这两条路径中的起点、终点和J（w）都相同。因此，该两条路径为重复路径，但经过的中间状态 yj＋1、yj＋2不同，则称该中间状态为可替状态。删除其中一个可替状态，该可替状态所在的重复路径就会被删除。

删除的条件为 （∃s3＝ bj＋1，p∈ Σ∗） 使得 η（yj，s3） ＝ yp，（∃s4＝ bj＋2，q∈ Σ∗） 使得 η（yj，s4） ＝ yq，s3，s4集合中多的保留，少的删除，留下的路径灵活性较强。可替状态的删除如算法2所示。

算法2：可替状态的删除

输入：有效路径组成的自动机模型

输出：重复路径删除后的自动机模型

说明：（1）删除重复路径中的可替状态，删除该状态对路径的长度无影响，J（w）的值不变。删除可替状态后到终点的多条路径中冗余点相应减少。（2）路径的重复问题使得数据冗余，导致内存开销大。因此，删除重复路径使得冗余点减少，内存开销相应减少。

根据算法2对图3进行可替状态的删除。如：状态y9经过事件b9，1到达状态y1，再由状态y1经过事件 b1，2转移到状态 y2；y9也可经过事件 b9，10到达中间状态y10，再由状态y10经过事件b10，2到达状态y2。两条路径中起始状态为y9，汇合状态为y2，可替状态为 y1、y10， 中间相连的事件集 s3＝ b1，9，s4＝ b10，2、b10，14。 s3＜ s4，因此保留状态y10，删除状态y1及相连的事件。删除后的自动机模型如图4所示。

图4 可替状态删除后的自动机模型

3.3 迭代删除

做可替状态删除时，可能出现无效状态；做无效状态删除时，可能出现可替状态。因此，需进行两种算法的迭代处理，直至所有冗余点删除完成。无效状态删除后，路径变为有效路径；可替状态删除不影响路径的求解。因此，两种算法的迭代，不会影响到最优路径的求解。迭代删除如算法3所示。

算法3：迭代删除

输入：重复路径删除后的自动机模型

输出：无冗余状态的自动机模型

说明：（1）通过算法1、2、3进行了冗余点的删除，使得后续在寻找最优路径时，搜索范围减小，内存开销减少，则搜索效率相应地提高。（2）通过以上算法，对路径上的冗余点进行了删除，使得任意两节点之间路径最短，权重最小，则自动机简化后的模型全局最优。

根据算法3对图4进行迭代删除。如状态y2经过可替状态的删除后，从有效状态变为无效状态，删除该状态。所有冗余点删除后的自动机模型如图5所示。

图5 迭代删除后的自动机模型

3.4 可行状态的优化

迭代删除后模型的冗余点都已被删除，但迷宫较大时仍存在状态和事件过多的问题，因此要对模型进行进一步的优化。剩下的路径为可行路径，在此路径上对权值w及权重J（w）进行状态和事件的优化可提高计算效率及节约存储空间。

数组A1存放的是节点删除后其中一条路径上的状态节点，0表示初始状态y0，m表示标识状态ym，剩余的为通道状态。数组B1存放着初始状态、分支状态及标识状态。

状态节点的优化思想如下：

（1）数组C1中存放分支状态节点之间的权值，初始值为0。

（2）在数组A1中搜索数组B1状态之间存在多少个通道状态节点，因通道状态节点的移动路径是唯一的，所以引入权值进行优化。依此类推，找到所有分支状态之间的权值。

（3）搜索剩余路径进行省略并引入权值。

说明：通过对可行路径中的节点筛选，使一些不必要的节点被省略，只留下关键节点进行保存。节点大批量地减少，使得计算机的内存开销也大幅减少。

对迭代后的自动机模型图5进行状态优化。首先把一条路径的所有状态节点放入数组A1；把初始状态节点y0、分支状态节点y7、y24、y41及标识状态节点ym放入数组B1；其次，选择相邻的分支节点引入权重进行简化，如：路线y7→y8→y9→y10→y14→y15→y16→y19→y24，y7经过8个状态到达y24，则y7到y24权重J（w）为8，把权重放入数组C1中。优化的数组存放如图6所示。

图6 可行状态的优化

对所有路径进行状态优化，优化后的自动机模型如图7所示。其中状态和事件个数大大减少，状态由原来的43减少到6，事件由96减少到14。通过以上状态的删除及优化，不仅减小了计算机的存储量，也提高了路径求解的效率。

图7 优化后的自动机模型

4 最短路径求解

本文在自动机模型的基础上进行了简化，简化分为节点删除和节点优化两个部分，节点删除去除了路径中的冗余点，节点优化筛选可行路径的关键节点保存，使得内存开销减小。因此，在简化后的模型上使用Dijkstra算法可以快速、高效地计算出最短路径，最短路径，如表1所示。而传统Dijkstra算法计算结果如表2所示。

表1 优化算法求解

表2 传统Dijkstra算法求解

从表1可知，初始状态到标识状态的最短距离为14，找到两条最短路径为y0→y1→y29→y41→ym或y0→y1→y24→y41→ym。 经过此方法不仅能求得多条最短路径，且路径的距离及路线都能详细给出。

对比：（1）传统的Dijkstra算法，同时也会计算多条死胡同路径的距离，增加了不必要的工作量。而优化算法，在一开始就删除死胡同路径，只保留到目标点的最短距离。（2）传统的Dijkstra算法虽然有权值，但在求栅格地图的迷宫时，所有权值都为1，对后续求解没有大的作用。优化后的算法对不必要的节点进行省略，省略的节点利用权值表示，发挥了权值的作用。（3）传统的Dijkstra算法通常只能求单条最短路径，而本文在简化后的自动机模型上用文献［24］的改进算法，求出多条最短路径。（4） 传统Dijkstra算法的时间复杂度为O（n2）。 而优化算法的时间复杂度等于简化模型的时间复杂度O（p）及简化后节点的复杂度O（q2）之和，p＋q＝n。简化使得绝大部分节点被省略，只剩少部分节点进行最短路径的计算。根据公式可知O（p）＋O（q2） ＜O（n2），且随着迷宫规模的增大，简化模型的时间复杂度O（p）可以忽略不计，则优化算法的效率相较于传统算法显著提升。

对图2中的自动机分别用传统的Dijkstra算法和优化算法求解。由表2可知，时间复杂度为432＝1 849。由表1可知，时间复杂度为37＋62＝73。用MATLAB仿真求解10×10迷宫时，传统的Dijkstra算法用时为36 ms，优化算法用时0.8 ms，其时间复杂度相差较大。随着迷宫规模的增大，两者的时间复杂度相差会更大。

5 仿真及分析

5.1 执行命令次数

表3是A∗算法、Dijkstra算法和本文算法找到最优路径的前提下，所要执行命令次数的对比。从表3可知，Dijkstra算法在找最优路径时，会搜索所有的可行状态节点，执行命令的次数等于可行状态节点个数；A∗算法在障碍物多且复杂的情况下，其寻找最优路径时冗余点较多，执行命令次数相应也较多；在障碍物较少的情况下，其寻找最优路径冗余点少，执行命令次数相应少；A∗算法最坏的情况接近Dijkstra算法，最好的情况为最短路径的距离。本文算法只取路径中关键节点进行指令的执行，其执行命令的次数少于最短路径的距离，与简化后的节点个数有关。Dijkstra算法执行命令的次数占可行节点的100%，A∗算法执行命令的次数在最优路径节点个数和总节点个数之间，取决于迷宫的复杂度。而本文算法执行命令的次数往往小于最优路径的节点个数，取决于保留的关键节点个数。

表3 执行命令次数

5.2 路径图

图8给出了10×10迷宫下的一个特例，黑色块表示障碍物，白色块表示可行路径，绿色块表示该算法从起始点到目标点需要遍历的节点。从图8可知，Dijkstra算法需遍历所有的可行节点，占可行节点的100%；A∗算法需要遍历23个可行节点，占可行节点的53%；而本文算法只需遍历6个节点，占总结点的12%。Dijkstra算法需要遍历所有的可行块才可以找到路径，A∗算法也需要遍历一些多余的块，而本文算法所遍历的可行块就是最短路径。

图8 三种算法遍历节点图

5.3 时间对比

前文通过一些具体的小型迷宫来说明本算法的有效性，为了验证本算法在随机的复杂大规模迷宫中也同样保持有效性，在Matlab中产生10×10，20×20，40×40，60×60，80×80，100×100，125×125，150×150，200×200，250×250，300×300 规格的随机迷宫矩阵，每个规格产生5个随机迷宫矩阵，并用3种算法对不同规格下的不同矩阵进行仿真。仿真结果如图9所示，横轴代表迷宫的规格，纵轴代表同一个规格下5个迷宫运行时间的平均值。由图9可见，Dijkstra算法随着迷宫规模的增大，搜索最优路径的时间呈指数级增长。A∗算法的搜索时间效率高于Dijkstra算法，但低于本文算法。计算300×300迷宫时，Dijkstra算法计算2 h仍没有结果，A∗算法时间需要1 723.415 32 s，而本文算法仅需602.541 161 s。通过多个随机产生的迷宫矩阵实验表明，本文算法总能找到最优路径，其平均时间优于Dijkstra算法及A∗算法。

图9 算法结果

6 结束语

本文以迷宫为研究对象，提出了基于自动机模型的迷宫最优路径求解算法。该算法是用新的工具进行建模和简化的，与以往最优求解思路截然不同。该算法首先建立迷宫的自动机模型，结合其结构性质进行节点简化，简化分为节点删除及节点优化两部分，简化后冗余点被删除且只留下路径的关键节点，使得内存开销、求解时间相应地减少，且优于其他算法。其次，用这些关键节点进行路径长度的计算，得到最优路径。仿真结果表明，求解路径中的冗余点被消除，内存开销减少且在处理大规模迷宫时效率显著提升。但该类算法针对的是全局环境已知且不变的情况。