电脑鼠走迷宫的的算法研究与实现.doc

PAGE PAGE 1 电脑鼠走迷宫的的算法研究与实现 摘 要 电脑鼠的英文名称为Micromouse，实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。它可以在“迷宫”中自动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地。本文主要研究电脑鼠走迷宫时涉及的算法，主要包括迷宫生成算法以及用时最短的算法和路径最短的算法，其中用时最短的算法是指电脑鼠按照一定的规则探索迷宫，直到找到出口为止。路径最短算法是指从所有的可行路径中找出最短的那条路径。 关键词：电脑鼠，迷宫，迷宫生成算法，时间最短算法，路径最短算法  Algorithm and Implementation of Micromouse through the Maze Abstract The English name of Diannaoshu is Micromouse,In fact,its a small robot controlled by a Microproccesser with abilities to perceive、judge and walk,which can find the best way of destination automaticly.It can perceive and remember maze map automaticly and find a best way to destination by some certain algorithm making it to reach destination with the fastest speed.this paper is mainly on the algorithms when Micromouse goes through mazes.It mainly include Maze generation algorithm 、the shortest time algorithm and the shortest path algorithm.Among them,the shortest time algorithm means Micromouse follows some rules to explore mazes, until it find the exit.The shortest path algorithm means finding the shortest path from all the feasible paths. Keywords: Micromouse, Maze, Maze generation algorithm, the shortest time algorithm, the shortest path algorithm 目 录 TOC \h \z \t 标题 1,2,标题 2,3,Abstract,2,Key words,1,标题,1 HYPERLINK \l _Toc262246105 第一章 前 言 PAGEREF _Toc262246105 \h 1 HYPERLINK \l _Toc262246106 第二章 迷宫的发展与介绍 PAGEREF _Toc262246106 \h 2 HYPERLINK \l _Toc262246107 2.1迷宫的简介 PAGEREF _Toc262246107 \h 2 HYPERLINK \l _Toc262246108 2.2迷宫的历史 PAGEREF _Toc262246108 \h 2 HYPERLINK \l _Toc262246109 2.3迷宫的算法 PAGEREF _Toc262246109 \h 3 HYPERLINK \l _Toc262246110 第三章 需求分析和总体设计 PAGEREF _Toc262246110 \h 4 HYPERLINK \l _Toc262246111 3.1 需求分析 PAGEREF _Toc262246111 \h 4 HYPERLINK \l _Toc262246112 3.2 总体设计 PAGEREF _Toc262246112 \h 4 HYPERLINK \l _Toc262246113 第四章 系统开发环境与开发工具 PAGEREF _Toc262246113 \h 6 HYPERLINK \l _Toc262246114 4.1 JavaApplet介绍 PAGEREF _Toc262246114 \h 6 HYPERLINK \l _Toc262