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

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

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.

Key words: map complexity, Hamming complexity, relative Hamming complexity, pathfinding, HPA* algorithm

中图分类号: 

• TP391