寻径算法在实际工程中的改进  

IMPROVING A^ ＊ PATHFINDING ALGORITHM IN REAL PROJECT

作　　者：许开平[1] 张冬茉[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200240

出　　处：《计算机应用与软件》2008年第6期237-238,274,共3页Computer Applications and Software

摘　　要：Dijkstra算法和A*算法是被采用得非常普遍的算法,虽然它们的基本思想很容易被理解,但在实际工程的运用中,由于对地图信息的计算量很大,导致程序运行得没有想象中的效率高。通过阐述分层、分块地图以及连接点的应用,来提高寻径算法在实际工程中的效率。The algorithms of Dijkstra and A^＊ are widely used. Though their basic thoughts are easy to be understood, but to realize them in real project could lead to inefficiency in the operation of the program because of the huge computation on maps information. This paper introduces some improvements, such as layered and blocked map description and the use of the joint nodes, to make the application of pathfinding algorithm more efficient in real project.

关 键 词：DIJKSTRA A^＊ 地图分层 地图导航 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TU723.3[自动化与计算机技术—计算机科学与技术]