Packing问题的计算复杂性

被引：6

作者：

陈传波

何大华

机构：

[1] 华中科技大学计算机科学与技术学院

[2] 华中科技大学计算机科学与技术学院湖北武汉

[3] 湖北武汉

来源：

关键词：

NP完全; Packing问题; 可计算性; 图灵机; 拓扑;

D O I：

暂无

中图分类号：

TP311.12 [];

学科分类号：

081202 ; 0835 ;

摘要：

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及 NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形 Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。

引用

页码：46 / 48

页数：3

共 6 条

[1] 关于实数的可计算性 [J].

陈传波 ;

何大华 .

[2] 求解单位等边三角形Packing问题的近似算法 [J].

陈传波 ;

何大华 ;

黄文奇 .

[3] 支持求解圆形packing问题的两个拟人策略 [J].

黄文奇 ;

许如初 .

[4]

皇帝新脑.[M].(英)罗杰·彭罗斯(RogerPenrose)著;许明贤;吴忠超译;.湖南科学技术出版社.2002,

[5]

计算机数学.[M].陈志平;徐宗本编著;.科学出版社.2001,

[6]

计算机、逻辑和集合论.[M].徐书润;胡国定编著;.科学出版社.1998,