单位等边三角形Packing问题算法研究

单位等边三角形Packing问题算法研究 华 中 科 技 大 学 学 报第 29 卷 第 11 期Vol . 29 No . 11 2001 年 11 月Nov. 2001 J . Huazho ng U niv. of Sci . & Tech. 单位等边三角形 Packing 问题算法研究 何大华 陈传波 () 华中科技大学计算机科学与技术学院 摘要 : 提出了三角形的两种放置动作 ———贴合动作和粘靠动作 ,在此基础上按照最小损伤策略设计了求解单 位等边三角形 Packing 问题的最小损伤法. 计算结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明 ,该算法具有较高的速度和完整度 ,以此算法为基 础 ,可能为更具现实意义的多边形 Packing 问题找到一个高效的求解算法. 关 键 词 : 计算机 ; 算法 ; 三角形 Packing 问题 ; 贴合动作 ; 粘靠动作 ; 损伤度 ; 最小损伤法 () 文章编号 : 100028616 20011120029203 中图分类号 : TP301 . 6文献标识码 : A 1 求解 N P 难度问题是当今计算机科学算法的方位用 P表示. i 中的瓶颈问题 ,迄今的研究表明 ,对这类问题根本 不存在既快速又完整的经典高效算法 ,因此人们 把注意力集中在相对精确又不是太慢的启发式方 2 ,4 法上 ,并在这方面取得了较大进展. 单位等 边三角形 Packing 问题是 N P 难度问题 ,它是一类 特殊的 Packing 问题 ,各类 Packing 问题的综述可 参阅文献 5 . 本文以贴合动作和粘靠动作为基 础 ,以损伤度为启发信息 ,设计了求解单位等边三 图 1 边框三角形角形 Packing 问题的一个近似算法 ———最小损伤 在当前格局下 , 称 4 个边框三角形和已放入? 法. Erich 等人也对该问题进行了研究 . 正方形内的k 个单位等边三角形为固定三角形 ; 称未放入的 n - k 个单位等边三角形为活动三角 1 问题与约定 形. 正方形 A B CD 如图 1 放置 , 以它的左下角顶 点 A 为坐标原点 o , 水平向右为 x 轴正向 , 竖直 单位等边三角形 Packing 问题 : 给定一正整向上为 y 轴正向. 建立直角坐标系 x oy , 设 d 为 数 n 和待定边长的正方形 , 求该正方形边长的最 正方形边长 , k 为已放入正方形的三角形个数 , 则 小值 , 使得可以把 n 个单位等边三角形互不相交 当前格局记为 { d , n , k , S , S , S , S , P, P, 1 2 3 4 1 2 地放入这个正方形内. 单位等边三角形指边长为 , P} , k = 0 时为初始格局.k 1 的等边三角形. 如果一个三角形的三个顶点都在正方形内 2 贴合动作和粘靠动作( ) 包括在边界上, 则称这个三角形在正方形内. 在 单位等边三角形 Packing 问题中 , 正方形被看作 由 4 个向外展开的等边三角形围成的区域 , 如图 由于三角形在平面上可以任意平移和旋转 ,1 ,这 4 个等边三角形称为边框三角形. 三角形的 这给计算带来不便 , 本研究采用现实的简化策略 , 方位用它的三个顶点坐标表示 , 第 i 个边框三角 对三角形的放置动作进行了若干限制 , 规定贴合 形的方位用 S 表示 , 第 i 个放入正方形的三角形 动作和粘靠动作才是实际考虑的放置动作 , 并以 i 收稿日期 : 2001205217 . () () 作者简介 : 何大华 19732,男 ,博士研究生 ;武汉 ,华中科技大学计算机科学与技术学院 430074. 在贴合动作和粘靠动作的基础上 , 两步策此为基础设计了求解单位等边三角形 Packing 问[ 6 ]略具体化为最小损伤策略 :a . 在当前格局下 , 题的最小损伤法.找到活动三角形 M 与 k + 4 个固定三角形形成 2 . 1 贴合动作的所有合理的贴合动作和粘靠动作 ; b. 将损伤度 如图 2 所示 , ?A B C 是活动三角形 , 灰色三 最小的放置动作放入正方形内. 角形和 ?1, ?4 都是固定三角形. 灰色三角形加 以上过程将从 k = 0 到 k = n 依次进行 , 直 上 ?1, ?4 中的任一个就可以约束 ?A B C 的 3 到算法成功或失败. 根据定义 , 活度反应了当前格 个自由度 , 这时 ?A B C 的方位就是它被这两个固 局容纳三角形的能力 , 显然 , 格局的活度越大 , 直 定三角形约束形成的一个贴合动作. 可以形象地 观上能放入的三角形就越多. 在当前格局下 , 合理 认为 , ?A B C 的一边贴在某个固定三角形的一边 的放置动作之间可能相交 , 任何一个合理的放置 上滑动 , 当它的任何部位与另一个固定三角形相 动作都可能导致其他某些合理的放置动作在下一 碰时 , 它的方位就是它的一个贴合动作. 格局成为不合理的放置动作 , 这表明每个放置动 作对格局的活度都有不同程度的损伤 , 损伤度越 大 , 越不利于以后放入更多的三角形. 因此 , 选择 损伤度较小的放置动作有利于问题的解决 , 本研 究把这一考虑称为最小损伤策略. 3 . 2 算法描述 给正方形指定一个较大的边长值 d , 使得最 图 2 贴合动作小损伤法可以把这 n 个单位等边三角形全部互 2 . 2 粘靠动作( ) 不相交地放入正方形内 这显然是可能的, 然后 如图 3 所示 , ?A B C 是活动三角形 , 灰色三 逐渐减小 d 重试 , 直至 d 不能再减小 , 这时 d 就 角形和 ?1, ?5 都是固定三角形. 灰色三角形加 是最小损伤法能找到的边长最小值 , 下面是给定 上 ?1, ?5 中的任一个就可以约束 ?A B C 的 3 边长 d 和单位等边三角形个数 n 时的最小损伤 个自由度 , 这时 ?A B C 的方位就是它被这两个固 法的算法描述. 定三角形约束形成的一个粘靠动作. 可以形象地 a . 初始化 d 和 n , 按前面约定建立坐标系并 认为 , ?A B C 的一个顶点被约束在某个固定三角 按图 1 初始化 4 个边框三角形作为初始格局. k 形的一个顶点上进行转动 , 当它的任何部位与另 为已放入正方形的单位等边三角形的个数 , 令 一个固定三角形相碰时 , ?A B C 的方位就是它的 k = 0 . 一个粘靠动作.b. 计算当前格局下所有合理的贴合动作和 粘靠动作. c . 若当前格局下无合理的贴合动作或粘靠 动作 , 则失败停机 ; 否则计算每个合理的贴合动作 和粘靠动作的损伤度. d. 把损伤度最小的那个合理的贴合动作或 粘靠动作放入正方形内 , 令 k = k + 1 . 图 3 粘靠动作 e. 若 k = n , 则成功停机 ; 否则转 b. 3 最小损伤策略及算法描述 4 计算结果与讨论 3 . 1 最小损伤策略 , 用 Visual C + + 编写了程序 ,根据以上思路 定义 1 活动三角形 M 的活度是指它在当 并在 Pentium ?333 上进行了计算. 图 4 是 n =前格局中合理的放置动作的个数. 在单位等边三 1,8 时最小损伤法计算得到的 Packing 图像 , 正 角形 Packing 问题中 , M 的活度也称为当前格局 方形下面的数字为最小边长值 , 表 1 是 n = 1,8 的活度. ( ) 定义 2 活动三角形 M 的某个合理的放置时最小损伤法的实验结果 t 为执行时间. 第 11 期何大华等 : 单位等边三角形 Packing 问题算法研究31 图 4 最小损伤法的实验图像 表 1 最小损伤法的实验结果 定义更多类型的放置动作 , 这与计算速度却是一 个矛盾 , 逐步解决这个矛盾是本文的后续工作. 规模 1 2 3 4 5 6 7 8 参考文献 粘靠 粘靠 动作 粘靠 贴合 贴合 贴合 贴合 贴合 1 Davis M D , Weyuker E J . 可计算性 、复杂性与语言. 贴合 贴合 张立昂 ,耿素云译. 北京 :清华大学出版社 ,1989 . t / s 0 . 00 0 . 00 0 . 00 0 . 05 1 . 76 1 . 38 0 . 05 0 . 05 2 Hochbaum D S , Maass W. A pp ro ximatio n Schemes for Friedman E. 的结果 ,而且速度很快. 此外 , Fried2 Covering and Packing Problems in Image Processing and man E. 并没有给出一个求解算法 , 在 n 很大时 , () VL SI. Journal of t he ACM , 1985 , 321: 130,136 要构造较好的结果就很吃力 , 而最小损伤法能快 3 黄文奇 ,朱 虹 ,许向阳等. 求解方格 Packing 问题的速地给出 n 值很大时的近似解 , 本文对此是一个 () 启发式算法. 计算机学报 , 1993 , 16 11: 829,836 黄文奇 ,许如初. 支持求解圆形 Packing 问题的两个拟 有益的补充. 4 ( ) () 人策略. 中国科学 E, 1999 , 29 4: 347,353 贴合动作和粘靠动作的定义尽管给出了一个 5 Dowsland K A , Dowsland W B . Packin g Problems. Eu2 现实的求解基础 , 但这种限制措施损害了原始问 () ropean Journal of Operatio nal Research , 1992 , 56 1: 题的完整性 , 以此为基础的计算结果常常不是客 2,14 观最优解 , 因此对三角形放置动作的限制应该尽 6 陈传波 ,何大华. 三角形 Packing 问题中无损放置动作 量少 , 这样才有可能得到完整度更高的解 , 即还要 () 的研究. 华中科技大学学报 , 2001 , 29 11: 32,34 Algorithm f or Solving Dense Packings of Un it Equilateral Triangles in a Square He D ah u a Chen Ch u a nbo Abstract : Based o n t wo t ypes of placement s called sticking placement and leaning placement and t he least dest roying st rategy , an app ro ximate algo rit hm called t he least dest roying algo rit hm fo r solving dense pack2 ings of unit equilateral t riangles in a square is developed. The co mp uting result s show t hat t he least dest roy2 ing algo rit hm is of high perfo r mance and integrit y. Based o n t his , an efficient algo rit hm fo r solving polygo n packing p ro blem can be developed. Key words : co mp uter ; algo rit hm ; t riangle packing p ro blem ; sticking placement ; leaning placement ; de2 st roying degree ; least dest roying algo rit hm He Da hua Docto ral Candidate ; College of Co mp uter Sci . & Tech . , HU S T , Wuhan 430074 , China .