当前位置：文档之家 › 电脑鼠算法

电脑鼠算法

  • 格式：ppt
  • 大小：1.49 MB
  • 文档页数：59

下载文档原格式

  / 59

合集下载

电脑鼠走迷宫介绍

电脑鼠走迷宫介绍

什么是电脑鼠
电脑鼠集多学科于一身： 是个实实在 在的机器人 电脑鼠需要有众多 信息的反馈，如墙 壁信息等。 控制电脑鼠在迷宫中 快速而准确的行走属 于自动控制技术范畴。
机械 工程 传感 测试 人工 智能 自动 控制 程序 设计 电子 工程
电脑鼠还是一个 嵌入式系统，需 要广泛的涉及信 号处理、通信、 微处理器应用和 电机控制等
电脑鼠走迷宫
1 2
什么是软件操作
4
5
解析智能算法 电脑鼠走迷宫竞赛
第一部分：什么是电脑鼠
什么是电脑鼠？
电脑鼠，英文名micromouse，电脑鼠是使用微控制器﹑传感器 和机电运动部件构成的一种嵌入式微型机器人。它可以在“迷宫” 中自动记忆和选择路径，寻找出口，最终到达所设定的目的地。
电脑鼠走迷宫
电脑鼠可以在不同“迷宫”中自动记忆和选择路径，采用相应的算 法，快速的达到所设定目的地。 早在1956年，美国数学家申龙发明了一个能自动穿越迷宫的“电脑 鼠”，以此证明计算机可以通过学习提高智能。（人工智能初步体 现） 1979年比赛开始正规化，由IEEE与APEC共同主办，诞生了国际上 最有影响力的美国APEC 国际电脑鼠竞赛。号称电脑鼠世界三大赛 事之一。至今已经举办30届。
电脑鼠走迷宫
1980年欧洲、日本相继引入电脑鼠走迷宫竞赛， 1987年新加坡南洋理工第一届IES电脑鼠大赛。 2004年英国伯明翰城市大学主办 UK 大赛 2006年台湾教育部开始重视电脑鼠比赛，欲通过参赛 争夺台湾在国际人工智能领域的地位。 现在电脑鼠比赛发展非常好，实力很强的国家和地区 有美国，日本，新加坡，台湾，英国，韩国和印度等国 家。世界上每年都有高水平的电脑鼠大赛相继举办。为 此有很多大学还开设了“电脑鼠原理与制作”的选修课 程。

一种新颖的电脑鼠走迷宫算法研究

一种新颖的电脑鼠走迷宫算法研究

是 最 优 解 且 搜 索 效 率 低 。 很 多 情 况 下 需 要 遍 历 整 个 迷 宫 才
能 够 找 到 终 点 ，针 对 以 上 算 法 所 存 在 的 问 题 ，本 文 提 出 一 种
经 过 改 善 和 优 化 后 的 融 合 算 法 — — 向 洪 算 法 ，此 算 法 建 立
在 向心 算 法 和 洪 水 算 法 的基 础 上 ，对 墙 壁 信 息 进 一 步 拓 展 ， 减 少 了 搜 索 过 程 中 的 盲 目性 ，有 效 地 判 别 无 效 路 径 。向洪 算
间 ，在 每 次 运 行 结 束 后 都 会 获 得 一 个 数 值 ，最 终 成 绩 为 数 值 最 小 的Ｔ 竞 赛 的最 终 成 绩 由运 行 速
度 、迷 宫 求 解 效 率 和稳 定 性 三 个 方 面 确 定 。搜 索 阶段 获 取 的迷 宫 信 息 量 越 充 分 ，进 行 路 径 的预 判 越 精 准 。选 取 的路 径 越 有 效 ，对 冲 刺 阶段 最 优 路 径 的 选 择 就 越 有 利 。前 提 是 电 脑 鼠 足 够 稳 定 。因 此 迷 宫 搜 索 算 法 的设 计 和优 化 目标 是 使 电脑 鼠稳 定 的 在 短 时 间 内 探 寻 到 尽 可 能 全 面 的迷 宫 墙 壁 资 料 ．利 用 搜 索 的迷 宫 信 息 做 出准 确 的决 策 分 析 和最 优 路 径 判 断 。 向洪 法则 就 是 针 对 以 上 目标 的 一 种迷 宫搜 索 优 化 和 实 现 算 法 。
时 间 。
１．电脑 鼠走 迷 宫 的理 论 基 础 与 迷 宫 建 模
１．１电脑 鼠走 迷 宫 的 理 论基 础 “电脑 鼠”走迷 宫竞 赛 的 任 务 是 电脑 鼠在 千 变 万化 的 未 知

电脑鼠的原理分析及算法研究

电脑鼠的原理分析及算法研究

电脑鼠的原理分析及算法研究摘要：本文阐述了电脑鼠的定义和意义，并对电脑鼠的工作原理及硬件、软件设备进行一定的分析，研究了一些传统和经典的算法。

关键词：电脑鼠，模块，算法，蚂蚁算法Analysis of the Principle and Study of Algorithm ofMicroMouseWang Huinan 04010515(Southeast University, Nanjing, 211189)Abstract:This paper describes the definition and significance of MicroMouse. And analyzing the work principle of MicroMouse’s hardware and software equipment. Studying a number of traditional and classical algorithms.Key words: MicroMouse; Module; Algorithms; Ant algorithm本学期，我选修了机电一体化——电脑鼠。

通过学习和查找资料，我对电脑鼠的运行原理有了一定的了解，并产生了一些新的想法。

1电脑鼠的基本知识1.1电脑鼠的定义所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称，它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设定的目的地。

实际上电脑鼠就是一个电力驱动小车，而这个电动小车是由一个或多个为控制器来控制，通过传感器和其他各功能器件的配合，具备一定的智能。

同时，电脑鼠拥有探测障碍物、行走、转弯、加减速好制动等基本功能。

1.2电脑鼠的意义电脑鼠可谓是一种具有人工智能的小型机器人，结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。

电脑鼠走迷宫转弯算法的改进与实现

电脑鼠走迷宫转弯算法的改进与实现

源、传感 器 、电机 、微控 制 单元 等功 能模 块 组成 ，电脑 鼠走 迷 宫的过程 主要 是通 过对迷 宫搜
索 算 法 的 研 究 以及 电 机 控 制 、传 感 器 的相 互 配 合 来 实现 。 关 键 词 ：Ａ Ｍ； 电 脑 鼠 ；迷 宫 搜 索 算 法 ； 中心 法 则 ； 运 动 控 制 Ｒ
图 １ １ ｘ ６ 准 迷 宫 示 意 图 ６ １标
◇ 预 留有 ６ Ｇ Ｉ 个 ＰＯ口 、 一 个 串 口 和 一 个 Ｓ Ｉ Ｐ
接 口：
收 稿 日期 ：０ ０ ０ — ７ ２ １ — ７ ２
◇ 带有矩 阵键 盘和七段 数码 管显示 。
５ 电 子 元 器 件 焘 用 ２ １ ． Ｗ Ｗｅｄ ｃ ４ ０ １ Ｗ ． ｃ ｎ １ ｃ￣
第 １卷 ３
第１ 期
电子元 器 件 焘用
Ｅｌ ｃｒ ｎ ｃＣｏ ｅ ｔｏ ｉ ｍｐｏ ｎ ｎｅ ｔ＆ Ｄｅ ｉ ｖｃｅＡｐｐ ｉａｉ ｎ ｌｃ ｔｏ ｓ
Ｖｏ ． ３ １ １ ＮＯ １ ．
２ １年 １ ０１ 月
Ｊｎ ０ １ ａ ．２ １
ｄ ｉ Ｏ３ ６ ￣ｉ ｎ１６ － ７ ５２ １ ．１ １ ｏ： ．９ ９ ．ｓ ． ３ ４ ９ ． １ ． ８ ｌ ｓ ５ ０ Ｏ ０
行 出 栈 入 栈 ， 以 找 到 目标 最 短 的 路 径 ，从 而 实 现
制 以及转 弯算 法等 。
２１ 底 层 驱 动 中 步 进 电 机 的 加 减 速 控 制 ．
智 能 老 鼠快 速 高效 的 到达 迷宫 的终 点 。文 中的 电 脑 鼠采 用 的迷 宫搜 索算 法 为 中心法 则 。中心 法则 是 指在 遇 到有 交叉 路 口且 没有 走过 时 ，智 能 老 鼠 优 先选 择 向迷 宫 中心 的方 向为前 进 方 向 。如 果 电 脑 鼠可 供选 择 前进 的方 向包 含 了两 个都 有 可 能是 离迷 宫 中心 最 近 的方 向时 ，它将 优 先选 择 可 以直

电脑鼠的迷宫演算法

电脑鼠的迷宫演算法
電腦鼠的迷宮演算法
班級：四技系統三甲 組員：49839033葉家宏 49839056黃致中 指導老師：黎靖
摘要
•如果把電腦鼠比喻成人來看，那硬體就是四肢， 而軟體就相當於電腦鼠的大腦。在此報告中討論 兩種路徑演算，兩種皆可再細分很多種演算法。
• 區域性演算法
又分為右手法則、左手法則、中左法則、中右法則、 向心法則。
• 演算法則有洪水填充法(Flood-Fill algorithm)及A*演算法與 其諸多的變形演算法等。
選擇你想搜尋的演算法
右手法則
區域性演算法
左手法則 中左法則 中右法則 向心法則
全域性演算法
洪水填充法 A*演算法
右手法則
• 電腦鼠遇到岔路時，以右手為優先，其次直線、左手。
右手法則-迷宮範例
圖11
選擇F值較小的E6為下一步
A*演算法(13/15)
• 全域性演算法
又分為洪水演算法、A*演算法。
區域性演算法
• 應用在探索迷宮的階段。 • 由於迷宮狀態未知，因此只能根據目前電腦鼠週遭的環境， 試著尋找到達終點的路徑。 • 演算法有左手法則、右手法則、中左法則、中右法則及向 心法則等。
全域性演算法
• 應用在已經部份或完全探索迷宮後，此時可以根據已探索 的迷宮資料找到起點至終點的最短路徑。
• 將E2設定為父節點(如圖8)， 並將D2從開啟列表中刪除且 加入關閉列表中。計算E2相 鄰節點的F值。 E3 → G=54 H=4*10 F=94 F1 → G=58 H=7*10 F=128 F2 → G=54 H=6*10 F=114 F3 → G=58 H=5*10 F=108 並將其指向父節點。 選擇F值較小的E3為下一步
A*演算法(3/15)

IEEE电脑鼠迷宫路径选择及死区决策

IEEE电脑鼠迷宫路径选择及死区决策

IEEE电脑鼠路径选择及死区决策一、引言（一）IEEE电脑鼠走迷宫竞赛背景嵌入式系统融合了微电子、计算机软\硬件、通信和电子工程等多种技术，广泛应用于航空、航天、仪器仪表、工业控制和3C（Computer、Communication、Consumer）等领域，是科技集成创新的主要手段。

为了培养科技创性意识和动手能力，全国各地在近几年纷纷举办“电脑鼠走迷宫“邀请赛。

电脑鼠英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置（微型机器人）。

电脑鼠要在指定的迷宫中比赛，在迷宫中探索以找出通往终点的路径，并随时掌握自身的位置信息，准确获取墙壁信息并做记录，最终依靠记忆找出走出迷宫的最佳路径，以最短的时间解开迷宫，赢得比赛。

国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举办以来参加国踊跃，为此许多大学还开设了“电脑鼠原理和制作”选修课程。

2007 年和2008 年，上海市计算机学会率先在国内主办了两次IEEE 标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加。

2009 年广州致远电子有限公司赞助了全国“IEEE 标准电脑鼠走迷宫”邀请赛，共邀请全国9 个赛区的52所高校参赛，反响强烈。

图1 所示为电脑鼠图2 所示为比赛迷宫本文主要以MicroMouse615为平台，介绍电脑鼠参赛的实现，对有些方面的基本算法提出改进，并在此基础上加上了一些自己的算法思想，比如说：用数学模型的方法提出了用改进后的数字PID算法对行进中的电脑鼠进行状态调整，进入死区的电脑鼠的人工智能决策，参赛时迷宫搜索的易于实现的算法以及植入操作系统的思想。

（二）竞赛平台简介MicroMouse615平台包含了微控制器、电机、红外线传感器、控制平台。

其中最重要的微控制器是LM3S615微控制器，如下图3为LM3S615的系统结构图。

其中内核用的是ARM Cortex-M3,外围还有存储器、系统时钟、定时器、输入输出端口、数模转换器等等。

电脑鼠算法

电脑老鼠走迷宫竞赛
算法简介
08计算机（1）班 龚若皓
软件算法所需要实现的功能
最基本的功能： 最基本的功能： 1.正确记录迷宫的信息 1.正确记录迷宫的信息 2.正录小车的状态（当前的方向，四周的挡板情况等） 正确记录小车的状态 3.确保小车的移动， 3.确保小车的移动，停止和转弯的可控性 确保小车的移动
需要实现的核心功能 1.实现基本的从起点到终点的寻路过程。 1.实现基本的从起点到终点的寻路过程。 实现基本的从起点到终点的寻路过程 2.实现等高表的生成算法。 2.实现等高表的生成算法。 实现等高表的生成算法 3.实现从当前的位置通过最有效的路径移动到指定的任意位置。 3.实现从当前的位置通过最有效的路径移动到指定的任意位置。 实现从当前的位置通过最有效的路径移动到指定的任意位置 （通过建立等高表来实现） 通过建立等高表来实现） 4.根据已经得到的迷宫地图信息实现起点到终点的最短路径分析。 4.根据已经得到的迷宫地图信息实现起点到终点的最短路径分析。 根据已经得到的迷宫地图信息实现起点到终点的最短路径分析 （通过建立等高表来实现） 通过建立等高表来实现）
寻路算法简介
正确使用堆栈， 2. 正确使用堆栈，整个选路算法的运行过程中会大量地使用堆栈 的入栈和出栈操作，如果对入栈和出栈的条件判断不正确， 的入栈和出栈操作，如果对入栈和出栈的条件判断不正确，有 可能造成数据紊乱，整个算法就崩溃了， 可能造成数据紊乱，整个算法就崩溃了，最好使用调试版上的 数码管实时显示堆栈栈顶的数据，发现有错误就在程序中寻找 数码管实时显示堆栈栈顶的数据， 错误，直到整个寻路算法稳定为止。 错误，直到整个寻路算法稳定为止。
数据的存储方式
绝对方向和相对方向的变换： 绝对方向和相对方向的变换： 假设数值0 假设数值0，1，2，3分别表示绝对方向的上，右，下，左，那 分别表示绝对方向的上， 么就用0 么就用0，1，2，3中的其中一个数值来表示当前小车车头朝向的方 向，当然这个数值是动态变化的，每转弯一次该数值应当变化一 当然这个数值是动态变化的， 次，例如当前方向的数值为3（左方），那么经过一次右转操作后 例如当前方向的数值为3 左方），那么经过一次右转操作后 ）， 该数值就应该变化为0 该数值就应该变化为0了（上方）。其实转化的规则相当简单，只 上方）。其实转化的规则相当简单， ）。其实转化的规则相当简单 要右转方向数值就加1 只要左转方向数值就加3 要右转方向数值就加1，只要左转方向数值就加3，只要后转方向数 值就加2 当然可能有越界的情况， 值就加2，当然可能有越界的情况，所以得出的方向数值再进行模 运算对4 运算对4取余数得出的结果就是转弯后小车的车头所面向的方向的 数值了。 数值了。

基于向心法则的电脑鼠走迷宫算法设计与优化


ｌ 引 言
迷 宫电脑 鼠的概念最早 由 ＩＥ ｐ ｃ ｕ 杂志在 Ｅ Ｅ Ｓ ｅｔ ｍ ｒ
传统 算法最 基本 的是深度搜 索和广度 搜索【， 统算 ７传 】 法存在搜 索效率 不高的 问题， 很多情况下 都有可能 在 会遍历 整个迷 宫才 能找到解， 以许多人在传 统算法 所 的基础 上，进 一步改善 这些算法，经过 改进后 的算法 有 Ｆｏ ｄ ｉ 算法【、 ｉ ｓ ａ 【等， ｌ ｌ ｏ Ｆｌ ８ Ｄ ｉ ｔ ’’ 这些算法在搜索效 １ ｋ ｒ ｓ】
２１ ０ ２年 第 ２ 卷 第 ９期 １
ｈｔ：ｗ ． ｓ ．ｒ． ｔ ／ ｗｗｃ － ｏｇｃ ｖ／ －ａ ｎ
计 算 机 系 统 应 用
基于 向心法则的 电脑 鼠走迷宫算法设计与优化①
贺 少波，孙克
（ 南 大 学 物 理 与 电 子学 院，长 沙 ４ ０ ８ ） 中 １０ ３ Nhomakorabea摘
要：电脑 鼠是一个集 自主迷宫搜索 、搜索完后最短路冲刺 、传感与控制于一体 的 自主移动机器 人系统． 具体
７ Ｏ年 代提 出，就是使用嵌入式微控制器 、传 感器 和机 电运 动部件 构成 的一种 智能行走 装置，可 以在” 宫” 迷
中 自动记 忆和选 择路径 ， 找 出 口，最终达 到所 设的 寻
目的地川．目前 电脑 鼠走迷 宫 比赛在许 多 国家都很 受
关注，迷宫 电脑 鼠在我国起 步较晚， 到 ２ ０ 直 ０ ７年才在
ｗｅｆ ｕ ｄｔ ａ ｅ ｔａ ｅｈ ｄ ｉ ｅ ｙｅ ｃ ｅ ｔｍ ａ ｅｓ ａ ｃ ｌ ｏ ｉｈ ｏ ｎ ｈ ｔｔ ｃ ｎ ｒ ｌ ｔ ｏ ｓａｖ ｒ ｆ ｉｎ ｚ ｅ ｒ ｈ ａｇ ｒｔ ｍ ｈｅ ｍ ｉ
Ｋｅ ｙ ｗｏｒ ｓ ｍｉｒ － ｕ ｅ ｍａ ｅｓ ａ ｃ ａ ｔ ｎ ｍｏ ｓｍｏ ｉｅｒ ｂ ｔ ｃ ｎ ｌ ｔ ｏ ｄ ： ｃ ｏ ｍｏ ｓ ； ｚ ｅ ｒｈ； ｕ ｏ ｏ ｕ ｂ ｌ ｏ ｏ ； ｅ ￣ａ ｈ ｄ ｍｅ

基于IEEE标准的电脑鼠走迷宫的智能算法研究


Ｉ ｔ ｌｉ ｅ ｌ ｏ ｉｈｍ ｅ ｅ ｒ ｈ ｏ ｉｒ ｍ ｏ ｅ ｍ ａ ｅ ｂａ ｅ ｏ ＥＥＥ ｔ ｎｄ ｒ ｎ ｅ ｌ ｎｔａ ｇ ｒｔ ｇ ｒ ｓ ａ ｃ ｆｍ ｃ ｏ ｕｓ ｚ ｓ ｄ ｎ Ｉ ｓａ ａ ｄ
Ｗ ＡＮＧ Ｂ ｎ，Ｚ ｉ ＨＡＮＧ ｅ— ａ ｇ Ｗ ｉ ｎ ｇ
最优 路 径 。此 外 ， 电 脑 鼠 转 弯 算 法也 进 行 了相 关探 讨 。 实验 结 果 显 示 ， 智 能 算 法很 好 的 实现 了在 ＩＥ 对 该 Ｅ Ｅ标 准 迷 宫
中快 速搜 索 最优 路 径 。 关键 词 ：电脑 鼠 ； 度 优 先 ；洪 水填 充 ；智 能 算 法 深 中图分类号 ： Ｐ ６． Ｔ ３ ８１ 文 献标 识 码 ： Ａ 文章 编 号 ：１ ７ — ２ ６ ２ １ ） ２ ０ ４ — ４ ６ ４ ６ ３ （０ １ １ —０ ２ ０
（ 安大学 信息工程学院， 西 西安 长 陕 ７０６ ） １０ ４
摘 要 ：通 过 对基 于 Ｉ Ｅ Ｅ Ｅ标 准 的 电脑 鼠 走 迷 宫 的 软 件控 制部 分进 行 分 析 和 研 究 ，提 出 了一 种 基 于 向心 法 则 和 向 点 法 则 的 深 度优 先 法 和 洪 水 填 充 法相 结合 的 智 能搜 索 算 法 ， 算 法 第 一 次 搜 索 时采 用 基 于 向 心 法 则 的 深 度 优 先 法 ， 二 该 第 次搜 索 时 采 用 基 于 向点 法 则 的深 度 优 先 法 ． 并且 设 计 “ 区” 定 返 回起 点 时机 ． 溯 和 冲刺 时采 用 洪 水 填 充 法 寻 找 热 确 回
第 １ ９卷 第 １ ２期
Ｖｏ ． ９ １１
Ｎｏ １ ．２
电 子 设 计 工 程
Ｅｌｃ ｒ ｎ ｃ Ｄｅ ｉｎ Ｅｎｇｎ ｅ ｔｏ ｉ ｓｇ ｉ

电脑鼠走迷宫算法仿真设计


１ 迷宫算法 的设计
１ ． １ 算法 设计 思想— — 泛洪 算法 本 文的算法 思想 ： 想 象你 站 在一 个 迷 宫里 ， 迷 宫格 之 间的隔板 由不透水 的材料制 成． 你 手 中有 一 个 带开关 的水 管． 当你想找 出通往迷 宫 出 口的最 短 路径 时 ， 你可 以打 开水 管 开关 ， 此 时水 便 从你 所 在 的迷 宫格 向四周 漫 出 ， 第一 支到达 出 口的水 流所 代 表 的路径便是你 想找 的最 佳路径． 由此引 出泛洪 算 法 ， 也称 为 Ｆ ｌ ｏ ｏ ｄ算法或是 洪水填充 法． １ ． ２ 原 始算 法—— 全 迷 宫搜 索算 法 原 始算 法 ， 即全迷 宫 搜 索 算 法 ， 也被称为“ 深 度 优先 ” 算法． 利 用 的原 理 是 对 整 个 迷 宫 进 行 全 部搜 索 ， 通过 建立 等高 表 ， 在所 有 由起点 达 到终点 的可行路 径 中找 到 最 短 路 径 ． 电脑 鼠最 初从 入 口 出发 ， 按 搜索 法则 顺着 某一 方 向 向前 探索 ， 若 能走 通， 则 继续 往 前 走 ； 否 则在 遇到 死 区 时 ， 将 沿原 路 返 回至上 一节 点 ， 换 一 个方 向再 继续 探索 ， 直 至所
２ 迷宫算法 的实现
２ ． １ 迷 宫算 法的 总体设 计 系统 算法 结 构如 图 １所 示 ， 主 要 由以 下几 个 模块 组成 ：
电脑 鼠走迷 宫 的算法
迷 宫 的 随机生 成 算法
搜索 迷
宫路 径 的算 法
迷宫 过 程 的动 态实 现
搜 全 索算 迷宫 ｌ ｌ 修正的 ｌ
冲刺状 态 ．
生 成迷宫 的算 法 主要 是 通过 Ｖ Ｂ编 程 在 Ｐ ｉ ｃ － ｔ ｕ ｒ ｅ 控件 上建 立迷 宫 ， 该迷宫是以 Ｐ ｉ ｃ ｔ ｕ ｒ ｅ控 件 上 的左下 角 为 原 点建 立 的 Ｘ Ｙ 平 面直 角 坐 标 系 ， 主
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
迷宫的规范
1） 迷宫由16×16个﹑18cm×18cm大小的正方形单 元所组成。
2）迷宫的起始单元可选设在迷宫四个角落之中的任 何一个。起始单元必须三面有隔墙，只留一个出口。 5
竞赛主要规则
电脑鼠的基本功能是从起点开始走到终点，这个 过程称为一次“运行”，所花费的时间称为“运行时间 ”。从终点回到起点所花费的时间不计算在运行时间内 。从电脑鼠的第一次激活到每次运行开始，这段期间所 花费的时间称为“迷宫时间”。如果电脑鼠在比赛时需 要手动辅助，这个动作称为“碰触”。竞赛使用这三个 参数，从速度﹑求解迷宫的效率和电脑鼠的可靠性三个 方面来进行评分。
货车类，上渡船有如下规定：
• 客车先于货车上渡船，且每上4辆客车，才允许放一辆货车； • 若等待客车不足4辆，则以货车代替； • 若无货车等待，允许客车都上船。
• 试设计一个算法模拟渡口管理。
16
各阶段所用的算法
17
3） 回溯
• 算法思想：深度优先遍历
• 步骤一：先将根结点作为活结点； • 步骤二：向活结点的子结点扩展，若其存在，子结点作
迷宫电脑鼠算法
重庆理工大学 计算机科学与技术系
1
五大内容:
2
一、电脑鼠简介
电脑鼠是一种具有人工智能的轮式机器人
它是多个学科交叉结合的结晶
3
电脑鼠走迷宫的关键技术
4
二、电脑鼠迷宫竞赛
目的
电脑鼠走迷宫竞赛的目的是制作一个微型机器人， 它能在最短的时间内穿越迷宫到达终点。参赛的机器人 称为“电脑鼠”，将电脑鼠放入迷宫并启动操作的人称 为“操作员”。
6
三、电脑鼠走迷宫演示
7
四、电脑鼠迷宫的设计与算法
电脑鼠走迷宫三个阶段
8
各阶段所用数据结构
9
1） 栈
• 操作特点：先进后出(Last In First Out, LIFO) • 结构特点：只允许一端插入、查看和删除，不允许对另
一端的操作 • 概念：
• 栈顶(入栈、出栈) • 栈底(固定，无操作) • 空栈
20
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
21
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
22
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
23
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
24
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
25
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
26
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
27
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
28
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
29
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
30
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
31
3） 回溯
将所有子结点加入队列； • 步骤三：重复步骤二，直至找到所求结点，或者队列为
空。
35
4） 广度优先 1

2
5
3
4
6
7
2
3
4
5
4
7
5
6
6
5
6
36
4） 广度优先 1
1
2
5
3
4
6
7
2
3
4
5
4
7
5
6
6
5
6
37
4） 广度优先 1
1
2
5
3
4
6
7
2
3
4
5
4
7
5
6
6
5
6
38
4） 广度优先 1
1
2
5
3
4
6
7
2
为新的活结点，若不存在可扩展子结点，将当前活结点 设为不可扩展结点，其父节点作为当前的活结点； • 步骤三：重复步骤二，直至找到所求结点，输出路径， 或者到没有可扩展结点时结束，输出null。
18
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
19
3） 回溯
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
• c)假设一个算术表达式中包含括号、方括号和花括号3 种类型的括号，编写一个算法来判别表达式中的括号是 否配对，以字符“\0”作为算术表达式的结束符。
12
2） 队列
• 操作特性：先进先出(First In First Out, FIFO)
• 结构特点：只允许一端入队，另一端查看和删除
• 概念：
• 队头(出队) • 队尾(入队) • 空队列
43
3）电脑鼠寻路
• While(当前结点不是终点){
• 记录电脑鼠所在点迷宫信 息,电脑鼠方向
3
4
5
4
7
5
6
6
5
6
39
4） 广度优先 1
1
2
5
3
4
6
7
2
3
4
5
4
7
5
6
6
5
6
40
4） 回溯思考题
• 用java代码实现前面查找的例子(找7)。
41
五、电脑鼠走迷宫的具体实现过程
1）电脑鼠每一步记录的数据
42
2）电脑鼠初始化
• 迷宫二维数组，每个结点定义为FFFF表示上右下左都有 墙。
• 迷宫鼠方向：电脑鼠放入方向，一般默认为向上(1000) • 栈，加入起点坐标 • 下面以起点为(0,0)，终点为(7,7)为例讲解
• 顺序队列(队列、循环队列)
• 链式队列
• 两端队列
13
2） JAVA中队列的实现
• 接口Queue实现 • 继承了Collection接口 • LinkedList实现了Queue接口 • Queue接口窄化了对LinkedList的方法的访问权限（即在方法
中的参数类型如果是Queue时，就完全只能访问Queue接口 所定义的方法 了，而不能直接访问 LinkedList的非Queue的方 法）
14
2） JAVA中队列的实现
• remove、element、offer 、poll、peek 其实是属于Queue 接口
• 异常---提示---阻塞 • 队列演示
15
2） 队列思考题
• a) 入队顺序1、2、3、4，那么出队顺序是？ • b)某汽车轮渡口，过江渡船每次能载10辆车。车分客车类和
1
2
5
3
4
6
7
1
2
3
4
5
4
7
5
6
6
5
6
32
3） 回溯思考题——N皇后问题
• 在一个N*N的棋盘上 放置N个皇后，且使 得每两个之间不能 互相攻击，也就是 使得每两个不在同 一行，同一列和同 一斜角线上。
33
各阶段所用的算法
34
4） 广度优先
• 特点：横向优先遍历
• 步骤一：先将跟结点入队列； • 步骤二：取队头元素，遍历队头元素的所有子结点，并
10
1） JAVA中栈的实现
• 类 Stack<E>实现 • 继承于Vector<E>, Object • 构造方法：Stack() 创建一个空堆栈 • 方法：
11
• 演示栈
1） 栈思考题
• a)若栈的输入序列是a、b、c、d，则可能的输出序列 有哪几种类？