电脑鼠算法课件.ppt

《电脑鼠算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、迷宫电脑鼠算法重庆理工大学计算机科学与技术系五大内容:一、电脑鼠简介电脑鼠是一种具有人工智能的轮式机器人它是多个学科交叉结合的结晶电脑鼠走迷宫的关键技术二、电脑鼠迷宫竞赛目的电脑鼠走迷宫竞赛的目的是制作一个微型机器人，它能在最短的时间内穿越迷宫到达终点。参赛的机器人称为“电脑鼠”，将电脑鼠放入迷宫并启动操作的人称为“操作员”。迷宫的规范1）迷宫由16×16个﹑18cm×18cm大小的正方形单元所组成。2）迷宫的起始单元可选设在迷宫四个角落之中的任何一个。起始单元必须三面有隔墙，只留一个出口。竞赛主要规则电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间称为

2、“运行时间”。从终点回到起点所花费的时间不计算在运行时间内。从电脑鼠的第一次激活到每次运行开始，这段期间所花费的时间称为“迷宫时间”。如果电脑鼠在比赛时需要手动辅助，这个动作称为“碰触”。竞赛使用这三个参数，从速度﹑求解迷宫的效率和电脑鼠的可靠性三个方面来进行评分。三、电脑鼠走迷宫演示四、电脑鼠迷宫的设计与算法电脑鼠走迷宫三个阶段各阶段所用数据结构1）栈操作特点：先进后出(LastInFirstOut,LIFO)结构特点：只允许一端插入、查看和删除，不允许对另一端的操作概念：栈顶(入栈、出栈)栈底(固定，无操作)空栈1）JAVA中栈的实现类Stack实现继承于Vector

3、>,Object构造方法：Stack()创建一个空堆栈方法：演示栈1）栈思考题a)若栈的输入序列是a、b、c、d，则可能的输出序列有哪几种类？b)判断一个输入字符串是否为中心对称。例如xyx、xyyx都是中心对称。c)假设一个算术表达式中包含括号、方括号和花括号3种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符“”作为算术表达式的结束符。2）队列操作特性：先进先出(FirstInFirstOut,FIFO)结构特点：只允许一端入队，另一端查看和删除概念：队头(出队)队尾(入队)空队列顺序队列(队列、循环队列)链式队列两端队列2）JAVA中队列的实现接口Queue实

4、现继承了Collection接口LinkedList实现了Queue接口Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问LinkedList的非Queue的方法）2）JAVA中队列的实现remove、element、offer、poll、peek其实是属于Queue接口异常---提示---阻塞队列演示2）队列思考题a)入队顺序1、2、3、4，那么出队顺序是？b)某汽车轮渡口，过江渡船每次能载10辆车。车分客车类和货车类，上渡船有如下规定：客车先于货车上渡船，且每上4辆客车，

5、才允许放一辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理。各阶段所用的算法3）回溯算法思想：深度优先遍历步骤一：先将根结点作为活结点；步骤二：向活结点的子结点扩展，若其存在，子结点作为新的活结点，若不存在可扩展子结点，将当前活结点设为不可扩展结点，其父节点作为当前的活结点；步骤三：重复步骤二，直至找到所求结点，输出路径，或者到没有可扩展结点时结束，输出null。3）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯1326544661324

6、5655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯13265446613245655773）回溯思考题——N皇后问题在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一

7、行，同一列和同一斜角线上。各阶段所用的算法4）广度优先特点：横向优先遍历步骤一：先将跟结点入队列；步骤二：取队头元素，遍历队头元素的所有子结点，并将所有子结点加入队列；步骤三：重复步骤二，直至找到所求结点，或者队列为空。4）广度优先13265446613245655774）广度优先13265446613245655774）广度优先13265446613245655774）广度优先13265446613245655774）广度优先13265446613245655774