汤 伟，赵 静，古 婵

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

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