基于决策树划分的分层路径搜索

论文摘要

路径搜索是计算机游戏中的一个基本问题,它的效率主要取决于需要探测的节点数目。A*算法探测的节点数目随着搜索空间的增大而增大,难以在游戏的实时性、计算机资源有限等诸多限制下快速寻路。HPA*算法采用分层的方法显著地提高了路径搜索的效率可以快速地找到近似最优的路径。HPA*将一个复杂的路径搜索问题分解为多个简单的小问题。地形信息是路径搜索需要考虑的重要因素。本文发现A*算法的效率对地形比较敏感,尤其是目标点附近的地形。在一定程度上,HPA*对地图进行均等划分可以降低地形因素对算法效率的影响。在充分考虑地形因素的影响下,本文提出了基于决策树划分的分层路径搜索算法,该算法视地图上的每个点为一个样例,依据决策树的割点对地图进行划分。决策树划分的结果是将地图划分成若干矩形区域,每个矩形区域内的地形都比较单一。实验结果表明该方法可以高效的寻找到较好的路径,同HPA*相比使用该算法寻找到的路径更优,而且探测的节点数更少。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 路径搜索现状
• 1.3 本文的主要工作
• 1.4 本文的组织方式
• 第2章 人工智能路径搜索算法
• 2.1 搜索空间表示
• 2.1.1 网格表示
• 2.1.2 节点表示
• 2.1.3 三角形表示
• 2.2 典型的搜索算法
• 2.2.1 A*算法
• 2.2.2 HPA*算法
• 2.2.3 基于遗传算法的路径搜索
• 2.3 障碍物对A*算法效率的影响
• 第3章 连续值属性决策树
• 3.1 决策树
• 3.2 连续值属性决策树
• 3.2.1 割点选择
• 3.2.2 启发式函数
• 3.2.3 广义的启发式函数
• 第4章 基于决策树分割的分层路径搜索
• 4.1 问题描述
• 4.2 基于决策树划分的分层路径搜索
• 4.2.1 构建决策树
• 4.2.2 构造抽象图
• 4.2.3 在线路径搜索
• 4.3 启发式对划分的影响
• 第5章 仿真实验
• 5.1 HPA经典地图上的寻路
• 5.2 仿真地图上的寻路
• 第6章 结论和展望
• 参考文献
• 致谢
• 攻读学位期间取得的科研成果