第1页共20页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共20页第五章蚁群算法在迷宫电脑鼠中的应用5.1引言许多智能问题，如下棋游戏、战略决策、机器人路径规划等都可以转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法通常会随着迷宫规模的增大、复杂性的增加，算法的空间和时间复杂性呈指数增加，从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发，并利用该过程与著名的旅行商问题(TravelingSalesmanProblem,TSP)之间的相似性，意大利学者M.Dorigo等人提出了一种新型的模拟进化算法---蚁群算法[1,2]。对TSP问题的求解结果显示，蚁群算法具有极强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等[2]。目前，蚁群算法已在组合优化、计算机网络路由、连续函数优化、机器人路径规划、数据挖掘、电网优化等领域取得了突出的成就[2-5]，实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2迷宫的基本信息及常用迷宫搜寻策略5.2.1迷宫的基本信息从比赛规则中得知，迷宫是由一个个18cm×18cm大小的方格组成的，迷宫大小为16×16，即行列各有16个方格。若将三维迷宫转化成二维图形,迷宫可用图5.1表示.第2页共20页第1页共20页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共20页图5.1迷宫行列与坐标对应关系5.2.2常用搜寻法则和策略5.2.2.1迷宫搜寻法则设定搜寻法则和策略是为了电脑鼠可以以最快的方式找到终点，到达目标后随即从所走过的路径中找出一条可行路径返回起点，然后再做冲刺，直达目的；法则的设定很重要，它可以使电脑鼠不多走冤枉路，可节省很多时间而制胜。每一只电脑鼠到达一方格时它最多有三个方向可前进，最少则因为三面都有墙，没有可以前进的方向；当遇到二个以上的可选择方向时，由于不同场合需要而有不同优先搜寻的方向顺序，常见的法则有以下几种：①右手法则：遇叉路时，以右边为优先前进方向，然后直线方向，左边方向；②左手法则：遇叉路时，以左边为优先前进方向，然后直线方向，右边方向；③中左法则：与右手法则相似，不过方向选择顺序改为直线优先，然后左边，右边；④中右法则：遇叉路时，以直线为优先前进方向，然后右边方向，左边方向；第3页共20页第2页共20页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共20页⑤求心法则：遇叉路时，以距中心最短的那个方向优先，然后依次选择。⑥乱数法则：以电脑鼠的随机值作为下一前进方向。5.2.2.2迷宫搜寻策略迷宫搜寻模式有全迷宫搜寻策略和部分迷宫搜寻策略两种：①全迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠会反身继续前进，然后以原设定的搜寻法则，时时检查未走过的路，直到每一方格都搜寻过后，才回起点。②部分迷宫搜寻策略：电脑鼠以任一搜寻法则前进到达终点后，电脑鼠将沿原路线返回起点，不再进行其它搜寻。如果比赛规则不计算搜寻时间，可采用全迷宫搜寻策略，待地毯式的搜寻过所有方格后，再计算最佳路径，作最后的冲刺，冲刺成绩一定相当不错。由于新制国际比赛规则加入搜寻时间的成绩计量，因此我们必须考虑部分迷宫搜寻策略，甚至还可能须考虑加入求心法则，截路径功能等更智慧的法则来协助；此时找到的路径可能不是最佳路径，但保证花的时间最短。5.2.3迷宫问题经典算法求解迷宫问题，经典算法有深度优先搜索和广度优先搜索两种。①深度优先搜索(DFS)：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。②广度优先搜索(BFS)：从入口出发，离开入口后依次访问与当前位置邻接...
