启发式迷宫算法在虚拟实验系统中的应用

《启发式迷宫算法在虚拟实验系统中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、木文由4i3orb3eck贡献pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT,或下载源文件到木机杳看。笫3期微机发展205月年03MicmptrDeeomeIcouev1pnorV0・3No511・Ma03y20启发式迷宫算法在虚拟实验系统中的应用严晖，杨路明，晓华，段彭嘉杨（中南大学信息科学与工程学院，南长沙401）湖108摘要:出了一种启发式迷宫连线算法，法通过最短距离的启发式方法减少E—节点扩展数目来提高连线速度和连提该算线存储效率，通过方向记忆法确定搜索走向，而减少回找邻节点的搜索次数，其时间复杂度得到了极人的改

2、善。从使关键词：算法:发式搜索；向记忆法迷宫启方中III分类号：P0•T316文献标识码:A文章编号：0535(030--02——010—7120)5082App1ct0fIIers■1aeA10ihoMircmPciainL0uitcMzgrtmtC00utrVitapeiesSseru1Exr‘mntytmYANiHu,YANGumig9DUANa—u,L—nX■10haPENGi-ag,Jayn(et10tirt,hnsa401,hacnruhUnVsyCagh108Ci)aSeinAbIS喇：：knfhuitn2aotaoi

3、hirsneAido

4、KerS:2*1oim；ersisac1■9iet—m0yywodmaeartghhu■1terIrdrcmerc■1()引sMVI虚拟实验系统是用于<:型计算机原理及应S微用）程的实验教学的虚拟实验平台。在实验过程中需要课搜索下一节点。这样人人减少了连线拐弯的次数，提高了连线性能。3使用矢最数据存储连线数据，）在进行连线操作时才将矢量信息转换为网格数据，少网格数据的存储空间，减仿真虚拟集成电路芯片的连接，因此，系统采用双层迷宫布线算法生成虚拟计算机系统的连线网格。•迷宫布线算法的特点是：同时由于2的改进，）使连线的拐弯次数减少，也

5、进一步压缩连线矢量数据的数量。1连线区域分成网格存储障碍和连线数据，）使用“波扩法u”行E—节点（节点）J进活的扩展，即在以连线起点为原点，起点到目标点距离为半径的圆形区域中扩展E以节点。由于迷宫算法采取FFI0方式L获取下一个E—2J1启发式方法扩展E—节点节点扩展方法是向当询E—点的右、、、4个节下左上方向搜索冇无障碍标志的节点H,］若冇则该节点将成为下节点，所以扩展的节点数目大，搜索速度慢，存储效率低；2迷宫算法采取无选择绕障碍搜索策略，）使连线拐弯次数和通孔较多，影响连线的性能。•为此，者提岀了一种启发式双层迷宫布线算作法L

6、,原算法进行了改进:3对J1采取启发式搜索策略，）优先扩展距离冃标节点最近的节点作为E-节点，改变原算法逞波纹状的广泛圆形区域扩展方法，使扩展节点优先向口标节点逼近，这样大大减少了扩展节点的数目，提高搜索效率。2回找路径算法中，）采取方向状态记忆控制策略，即先按记忆方向节优记忆当前E—点的搜索方向状态信息，个E—点。扩展E—节点的公式：节nrrW=hr.b.0eemw+ostd.oo+oftd.soc1eec1fe()c1b.o=h具屮：b为hr节点的邻节点；nreehe当前活节点；re为oftfe函数为向右、、、4s下左上个方向扩

7、展的偏移值，d为方向状态值，，,,分别表示右、、、；0123下左上估价函数：f（）=g（）+h（）具屮：（是节点的估价函数；（为状态空间小，）g）从起始节点到路径长度为的节点的实际代价；（是h）从当前E—节点的扩展节点到目标节点的蝕短路径的估计代价，长度值为扩展节点到目标节点的网格数。路径由于“扩法”波屮扩展节点同半径圆环上的扩展距离相同，距离起始节点半径为，的节点的g,值相同，1（）1故评-）女湖南涟源人。屮南大学信息■科学工收稿日期：o2—1作奢筒介:严晖（95,,16程学院讲师，破士研究生。从事计算机控制管理方面的研究工作。严

8、晖等:启发式迷宫算法在虚拟实验系统中的应用2?9估函数的只要考虑hn的值。()原算法采取FFI0方法获取下一个E—点，用队节使列来存取已扩展的E—点符合FF的搜索策略。为了节I0优先获取路径最短的节点作为E—点，节以便尽快地逼近2记忆