三角形Packing问题中无损放置动作的研究  

Optimal Placements in Triangle Packing Problems

作　　者：陈传波[1] 何大华[1] 

机构地区：[1]华中科技大学计算机科学与技术学院

出　　处：《华中科技大学学报（自然科学版）》2001年第11期32-34,共3页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：高等学校博士学科点专项科研基金资助项目 ;中国科学院软件研究所计算机科学开放研究实验室课题基金资助项目

摘　　要：提出了三角形Packing问题中的两类放置动作———完全嵌入动作和孤立动作 ,证明了这两类放置动作是当前格局下的无损放置动作 ,并从可计算性角度提出了零自由度孤立动作的概念 。Two types of placements called right embedding placement and orphan placement are proposed and proved to be optimal placements under the current configuration. The concept called rigid orphan placement is also proposed from its computability. These discoveries provide a reliable criterion for local optimization in tackling with triangle packing problem.

关 键 词：计算机算法 NP难度 格局 完全嵌入动作 孤立动作 三角形PACKING问题 无损放置动作 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]