计算机工程2012，Vol.38Issue(7)：10-12,3.DOI:10.3969/j.issn.1000-3428.2012.07.004
一种基于相对海明距离的地图复杂性度量
Map Complexity Measurement Based on Relative Hamming Distance
摘要
Abstract
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*算法Key words
map complexity/ Hamming complexity/ relative Hamming complexity/ pathfinding/ HPA algorithm分类
信息技术与安全科学引用本文复制引用
李艳,李铁松,陈彩,苏兰明..一种基于相对海明距离的地图复杂性度量[J].计算机工程,2012,38(7):10-12,3.基金项目
国家自然科学基金资助项目(60903088) （60903088）
河北省自然科学基金资助项目(F2009000227,A2010000188) （F2009000227,A2010000188）
河北省第二批百名优秀人才支持计划基金资助项目(CPRC002) （CPRC002）
河北大学自然科学研究计划基金资助项目(2010Q23) （2010Q23）
