期刊文献+

粗糙域Voronoi图离散生成算法研究 被引量:6

Research on discrete generation algorithm of Voronoi diagram based rough area
下载PDF
导出
摘要 Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A*算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A*算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A*算法估价函数权值与粗糙域粗糙特性正相关,并以此获得A*算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。 Voronoi diagram is an important branch of computational geometry and Voronoi diagrams based rough area are exten- sions of Voronoi diagrams. In this paper, a conception of Voronoi diagram based rough area is proposed and it is generated with the minimum distance between points of forming face and mother-points which is calculated out using A-star algorithm. For reducing the complexity of generating algorithm, a research on relation between weight of evaluation function of A-star algo- rithm and character of rough area is launched. Experimental results show that the optimal weight of evaluation function positively correlates with the roughness characteristics of rough area. Based on this, the optimal weight of A-star algorithm is obtained and the complexity of generating algorithm of Voronoi diagrams based rough area is remarkably reduced.
出处 《计算机工程与应用》 CSCD 2013年第23期191-194,214,共5页 Computer Engineering and Applications
基金 河北省科技型中小企业技术创新基金(No.11C1303111004)
关键词 VORONOI图 粗糙域 A'算法 估价函数 最优权 Voronoi diagram rough area A-star algorithm evaluation function optimal weight
  • 相关文献

参考文献9

二级参考文献80

  • 1张有会.线段加权的Voronoi图[J].计算机学报,1995,18(11):822-829. 被引量:30
  • 2王德春,陈利敏,张孝芳.基于A^*算法的舰船最佳航线选择[J].青岛大学学报(自然科学版),2005,18(4):10-13. 被引量:20
  • 3浅野哲夫.计算几何学[M].东京:朝仓书店,1990..
  • 4Preparata F P 庄心谷译.计算几何导论[M].北京:科学出版社,1990..
  • 5张有会.关于加权Voronoi图的研究.北京航空航天大学研究生院硕士学位论文[M].,1998..
  • 6T. H. Cormen, C. E. Leiserson, R. L. Rivest, et al. Introduction to Algorithms[ M ]. McGraw - Hill ,2001.
  • 7Steven M. LaVatle Planning Algorithms [ M ]. Cambridge University Press,2006.
  • 8Ismail Chabini,Shan Lan. Adaptations of the A* Algorithm for the Computation of Fastest Paths in Deterministic Discrete- Time Dynamic Networks[ C ]// IEEE Transactions on Intelligent Transportation Systems, 2004.
  • 9Taeg - Keun Whangbo. Efficient Modified Bidirectional A* Algorithm for Optimal Route - Finding [ J ]. lEA/ AIE2007, LNAI 4570, pp. 344 - 353,2007.
  • 10Elbeltagi E, Hegazy T, Hosny AD, et al. Schedule - dependent evolution of site layout planning[ J]. Constr Manage Econ 2003 ; 19:89 97.

共引文献194

同被引文献60

引证文献6

二级引证文献42

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部