一种基于相对海明距离的地图复杂性度量

摘要：

提出一种适用于分层路径搜索算法的地图复杂性度量方法.针对不同规模的地图,将其实际复杂度与可达到的最大复杂度之比作为相对复杂度,提出基于相对海明距离的度量方法,并引入地图区域间方差,从而更好地计算障碍物分布不均匀地图的复杂度.实验结果证明,该方法能准确地反映不同规模与障碍物分布不均的地图复杂程度,并与HPA*算法的搜索效率有较强关联性.

关键词：地图复杂性、海明复杂度、相对海明复杂度、路径搜索、HPA*算法

所属期刊栏目：38

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目60903088;河北省自然科学基金资助项目F2009000227,A2010000188;河北省第二批百名优秀人才支持计划基金资助项目CPRC002;河北大学自然科学研究计划基金资助项目2010Q23

在线出版日期：2012-06-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：10-12