资源描述：
《用人工智能中的搜索原理解决迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、用人工智能中的搜索原理解决迷宫问题人工智能用人工智能中的搜索原理解决迷宫问题SolvetheMazeProblemwiththesearchprincipleintheartificialintellig『ence(西南科技大学信息T程学院,西南科技大学网络技术中心)陈春梅杨世恩Chen,ChunmeiYang,Shien摘要:迷宫问题是一个经典的程序设计问题.它要求用计算机编程的方法求解出从迷宫的入口到出口的所有路径.本文采用人工智能中的搜索原理.介绍了求解迷宫问题的基本思想以度实现方法.分析了用C
2、语言编程的思路并给出了详细的程序设计语句,通过调试和运行总结出了一种极为简便,易于理解,易于编程的新方法.关键字:迷宫问题:人工智能:搜索原理;程序设计中国分类号:TP851文献标识码:AAbstract:Themazeproblemisaclassicalprogramingquestion,Itsaimisthattobesolvedoutallroutesfromentrytoexitofthemazebywayofcomputerprogramming.Thispaperexplicatest
3、hesearchprincipleintheartificialintelligenceandthemethodtosolvemazeproblem,andanalysesthethinkingofCprogramandprovidesthedetailedprogramsentences.Throughdebuggingandrunning,amethodwhichisverysimple,easytObeunderstood,andeasytobeprogrammedissummarized.Ke
4、ywords:mazeproblem,arUficialintelligence,searchprinciple,programing1引言曾经在《数据结构》中学过一个古老而又经典的迷宫问题.这个问题是:有一个二维迷宫,由二维数组Maze[ml[nl来存储,对任意的第i行第j列记为Maze『i]i【j】,若Maze【il[j]=O则有通路,Maze[i]【j]=1则是墙,没有通路.从某个人口出发,可沿四个方向前进(上,下,左,右).如遇0则可前进,遇1则受阻.按此规则求人口到某一确定出口的所有路径.图
5、1所示为10"10的迷宫简图,其中,0表示通路,1表示墙,Maze【ll[1l为人13,Maze『81181为出13.0l23456789lll1lllllll001000l0ll00l000l0ll0000ll00ll0lll0000ll000l0000ll0l000l00ll0ll10ll0lll0000000lllllllll1l图110"10迷宫2算法分析一般在求解迷宫问题时大多采用与人思维类似陈春梅:本科资助项目:虚拟生物——用人工生命方法模拟蜜蜂行为的研究(03ZQ026-035),四川省
6、青年科技基金的"穷举求解"方法或称"回溯"法,即从人口出发,顺着某一方向向前探索,若能走通,则继续向前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的路径都探索到为止.分析这一方法,其主要问题在于怎样探索才不会紊乱且结果详尽,用程序设计语言来实现时又该如何表示?要解决这个迷宫问题,则必须弄清楚这个迷宫的结构.分析以上迷宫,可行的通路并不规则,探索可行的每一步的过程,实与图的遍历思想是一致的.这样,要找迷宫可行路径就可利用图的一些算法来实现.上述方法实际上可以归结为典型的搜索问题——即搜索每一步
7、要出去的路.在人工智能很多常用的搜索原理中.盲目搜索的广度优先和深度优先算法便可行,这也是针对图形结构或网状结构所设计的两种遍历方法.为此.需设置以下参数作为编程前提,具体操作是:设置四个方向坐标FangXiang[4][2】:上:{0,-1}下:f0,1l左:{一1,Ol右:{1,0}设置四种步伐状态Maze[il[j】:1:墒2:曾走过但不通的路3:沿途走过的畅通的路0:原本就可行的路设置一个可行标志Flag:0:不可行1:可行@m啊邮局订82枷360~/_267—人工智能中文核心期刊<微计
8、算机信息>(嵌入式与S0C)2006年第22卷第4-2期从迷宫入口点出发,依次向四周搜索,查看每个方向是否可行,如果可行,则得到新的坐标并前进,记下这一步的状态为3,然后又以这新的坐标为出发点,继续搜索,这样依次进行下去,直至到达迷宫出口点m.n)为止.3程序设计3.1迷宫变量定义C语言是一种运用广泛的计算机高级语言.用它设计程序易读易写.该迷宫问题从结构上可分三个模块来实现.即可行性判定模块,前进模块和打印模块.为了运行和演示的方便,可将迷宫数组
