作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (7): 10-12. doi: 10.3969/j.issn.1000-3428.2012.07.004

• 博士论文 • 上一篇    下一篇

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

李 艳,李铁松,陈 彩,苏兰明   

  1. (河北大学数学与计算机学院机器学习与计算智能重点实验室,河北 保定 071002)
  • 收稿日期:2011-10-18 出版日期:2012-04-05 发布日期:2012-04-05
  • 作者简介:李 艳(1976-),女,副教授、博士、CCF会员,主研方向:机器学习,粗糙集理论,游戏智能;李铁松、陈 彩、 苏兰明,硕士研究生
  • 基金资助:
    国家自然科学基金资助项目(60903088);河北省自然科学基金资助项目(F2009000227, A2010000188);河北省第二批百名优秀人才支持计划基金资助项目(CPRC002);河北大学自然科学研究计划基金资助项目(2010Q23)

Map Complexity Measurement Based on Relative Hamming Distance

LI Yan, LI Tie-song, CHEN Cai, SU Lan-ming   

  1. (Key Lab of Machine Learning and Computational Intelligence, College of Mathematics and Computer Science, Hebei University, Baoding 071002, China)
  • Received:2011-10-18 Online:2012-04-05 Published:2012-04-05

摘要: 提出一种适用于分层路径搜索算法的地图复杂性度量方法。针对不同规模的地图,将其实际复杂度与可达到的最大复杂度之比作为相对复杂度,提出基于相对海明距离的度量方法,并引入地图区域间方差,从而更好地计算障碍物分布不均匀地图的复杂度。实验结果证明,该方法能准确地反映不同规模与障碍物分布不均的地图复杂程度,并与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

中图分类号: