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

Map Complexity Measurement Based on Relative Hamming Distance

作　　者：李艳[1] 李铁松[1] 陈彩[1] 苏兰明[1] 

机构地区：[1]河北大学数学与计算机学院机器学习与计算智能重点实验室,河北保定071002

出　　处：《计算机工程》2012年第7期10-12,共3页Computer Engineering

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

摘　　要：提出一种适用于分层路径搜索算法的地图复杂性度量方法。针对不同规模的地图,将其实际复杂度与可达到的最大复杂度之比作为相对复杂度,提出基于相对海明距离的度量方法,并引入地图区域间方差,从而更好地计算障碍物分布不均匀地图的复杂度。实验结果证明,该方法能准确地反映不同规模与障碍物分布不均的地图复杂程度,并与HPA*算法的搜索效率有较强关联性。This paper proposes a map complexity measuring method for hierarchical pathfinding algorithm.Aiming at maps with different size,it defines a relative Hamming distance to measure the complexity of maps by computing the ratio of the actual complexity and the maximum complexity of a map,and map region variance is introduced to compute complexity of maps with different obstacle distributions.Experimental results show that the method can reflect the complexity of maps with different sizes and different obstacle distributions better,and it has a strong correlation to the efficiency of HPA＊ algorithm.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]