下载后可任意编辑电脑鼠控制策略与算法讨论1下载后可任意编辑第五章 蚁群算法在迷宫电脑鼠中的应用5.1 引言许多智能问题, 如下棋游戏、 战略决策、 机器人路径规划等都能够转化为寻找迷宫最优路径问题。传统解决迷宫最优路径问题的算法一般会随着迷宫规模的增大、 复杂性的增加, 算法的空间和时间复杂性呈指数增加, 从而很难用于求解大规模的问题实例。从蚁群觅食过程中能够发现蚁巢与食物源之间的最短路径受到启发, 并利用该过程与著名的旅行商问题( Traveling Salesman Problem, TSP)之间的相似性, 意大利学者 M. Dorigo等人提出了一种新型的模拟进化算法---蚁群算法[1,2]。对 TSP问题的求解结果显示, 蚁群算法具有极强的鲁棒性和发现较好解的能力, 但同时也存在一些缺陷, 如收敛速度慢、 易出现停滞现象等[2]。当前, 蚁群算法已在组合优化、 计算机网络路由、 连续函数优化、 机器人路径规划、 数据挖掘、 电网优化等领域取得了突出的成就[2-5], 实践证明该算法是一种解决优化问题特别是组合优化问题的有力工具。5.2 迷宫的基本信息及常见迷宫搜寻策略5.2.1 迷宫的基本信息从竞赛规则中得知, 迷宫是由一个个 18cm×18cm 大小的方格组成的, 迷宫大小为 16×16, 即行列各有 16 个方格。若将三维迷宫转化成二维图形,迷宫可用图 5.1 表示.2下载后可任意编辑图 5.1 迷宫行列与坐标对应关系5.2.2 常见搜寻法则和策略5.2.2.1 迷宫搜寻法则设定搜寻法则和策略是为了电脑鼠能够以最快的方式找到终点, 到达目标后随即从所走过的路径中找出一条可行路径返回起点, 然后再做冲刺, 直达目的; 法则的设定很重要, 它能够使电脑鼠不多走冤枉路, 可节约很多时间而制胜。每一只电脑鼠到达一方格时它最多有三个方向可前进, 最少则因为三面都有墙, 没有能够前进的方向; 当遇到二个以上的可选择方向时, 由于不同场合需要而有不同优先搜寻的方向顺序, 常见的法则有以下几种: ① 右手法则: 遇叉路时, 以右边为优先前进方向, 然后直线方向, 左边方向; ② 左手法则: 遇叉路时, 以左边为优先前进方向, 然后直线方向, 右边方向; ③ 中左法则: 与右手法则相似, 不过方向选择顺序改为直线3下载后可任意编辑优先, 然后左边, 右边; ④ 中右法则: 遇叉路时, 以直线为优先前进方向, 然后右边方向, 左边方向; ⑤ 求心法则: 遇叉路时, 以距中心最短的那个方向优先, 然后依次选择。⑥ 乱数法则...
