基于决策树划分的分层路径搜索-计算机应用技术专业论文.docx

摘 要 摘 要 路径搜索是计算机游戏中的一个基本问题，它的效率主要取决于需要探测的节点数 目。A*算法探测的节点数目随着搜索空间的增大而增大，难以在游戏的实时性、计算机 资源有限等诸多限制下快速寻路。HPA*算法采用分层的方法显著地提高了路径搜索的 效率可以快速地找到近似最优的路径。HPA*将一个复杂的路径搜索问题分解为多个简 单的小问题。 地形信息是路径搜索需要考虑的重要因素。本文发现 A*算法的效率对地形比较敏 感，尤其是目标点附近的地形。在一定程度上，HPA*对地图进行均等划分可以降低地 形因素对算法效率的影响。在充分考虑地形因素的影响下，本文提出了基于决策树划分 的分层路径搜索算法，该算法视地图上的每个点为一个样例，依据决策树的割点对地图 进行划分。决策树划分的结果是将地图划分成若干矩形区域，每个矩形区域内的地形都 比较单一。实验结果表明该方法可以高效的寻找到较好的路径，同 HPA*相比使用该算 法寻找到的路径更优，而且探测的节点数更少。 关键词 信息熵 决策树 路径搜索 I Abstract Abstract Path-finding is a fundamental problem in computer games, and its efficiency is mainly determined by the number of nodes it will expand. A* algorithm isn’t suit for path-finding on large map under restrictions of limited computer sources and Real-time demand, because the number of nodes it will expand grows fast with the size of the search space. HPA* can promote the efficient of path finding using a hierarchical approach and find near optimal paths. HPA* divides a complex path-finding problem into many very simple problems. Terrain is one of the most important factors should be considered. In this paper we find that the efficient of A* is sensitive to the terrains, especially the terrain around the target point in grid-based environment. To a certain degree, the equal division of HPA* reduces the influence form terrain factor. We present DT-HPA* (Hierarchical Path-Finding A* based on Decision Tree), a hierarchical path-finding approach on the map which has been divided by decision tree. This approach views each point on the map as an instance, divides the map according to cut points of continuous valued decision tree. The result of division is that the map is cut into some rectangular regions, and retains the regions contain a kind of terrain. The experimental results show that this technique can find better paths effectively. Compared to HPA*, DT-HPA* can find more optimal paths with fewer nodes to be detected. Keywords Information entropy Decision tree Path finding II 保护知识产权声明 本人为申请河北大学学位所 提交的题目为《基于决策树划分的分