多边形填充问题的求解算法及计算复杂性研究-智能与分布计算实验室

多边形填充问题的求解算法及计算复杂性研究

姓名	何大华
论文答辩日期	2004.12.12
论文提交日期	2005.01.10
论文级别	博士
中文题名	多边形填充问题的求解算法及计算复杂性研究
英文题名	Algorithms for Solving Polygon Packing Problem and a Peek into Computational Complexity
导师1	卢正鼎
导师2	陈传波
中文关键词	计算复杂性;多边形填充问题;零自由度动作;最小损伤法;代数方法
英文关键词	computational complexity, polygon packing problem, rigid placement,least destruction algorithm, algebraic method
中文文摘	多边形填充问题是指给定一个长宽已知的矩形容器和若干个边数、形状和大小已知的多边形，问能否将这些多边形互不相交地放入矩形容器。若能放入，则给出各个多边形在矩形容器中的放置方位，否则回答不能放入。多边形填充问题在平面布局、皮革和制衣工业中有广泛的应用价值，许多实际的布局问题、覆盖问题和裁剪问题都可最终归结为多边形填充问题的求解。同时它又是计算理论中的重要问题，例如在算法设计和复杂性分析中占有重要地位。理论和实践的需要使该问题的算法设计变得十分迫切，但由于它具有NP难度，因此其实用快速算法常常是近似的，多数学者在处理该问题时对其进行简化，例如不允许多边形旋转或者仅允许多边形取有限的几个放置方向，这种处理方式有其应用意义，并且如此简化后的问题是NP完全的，称之为平移多边形填充问题。为了给多边形填充问题设计一个有效的近似算法，撇开具体的应用背景，从理论分析的角度，提出了零自由度动作的概念，将多边形填充问题简化为一个NP完全的组合优化问题，并采取将多边形逐个地放入矩形容器的策略。在如何选择放置动作的问题上，提出了最小损伤的思想，并在此基础上设计出了一个快速近似算法──最小损伤法，复杂性分析证明了该算法为多项式时间算法，大量的实验数据也表明最小损伤法是非常有效的。为改善算法的完整度，提出了相应的回溯算法，实验表明回溯算法可大大改善解的质量，并且计算速度也没有显著降低，具有很强的实用性。尽管零自由度动作模型对原始问题有损，即在此模型下最优解可能被忽略，但它有物理学方面的依据，直观上，一个零自由度动作可以有效地利用空间。提出了一个精确求解多边形填充问题的代数方法。由于多边形填充问题是一个连续问题，在计算过程中必然要涉及到实数的运算，而精确处理实数是Turing机无能为力的，因此分析了实数的可计算性，指出了实数运算带来的误差性质及其影响。并且深入分析了多边形填充问题解格局的拓扑结构，证明了零自由度原理，即多边形填充问题有解当且仅当它存在紧缩解，将多边形填充问题的解空间从无穷变为有穷且对原问题无损，为精确求解奠定了基础。在此基础上，提出了精确求解多边形填充问题的代数方法，若忽略实数运算的误差，则求得的解是精确的。尽管实数的运算在理论上不可能达到完全精确，但如果有需要，仍然可以获得任意的计算精度。在该代数方法下，只需求解一个多项式方程组就可以获得多边形填充问题的精确解，该多项式方程组的大小为问题规模的多项式量级，并且其计算复杂性仅仅依赖于求解该多项式方程组的复杂性。对多项式方程组的计算复杂性没有展开讨论，这需要进一步研究。研究了两种类型的计算复杂性，即与有穷性有关的计算复杂性和与无穷性有关的计算复杂性，通过具体的例子指出了它们各自的特点。在此基础上，研究了与多边形填充问题有关的一些基础问题。如证明了多边形填充问题的一个特例──矩形的三角形划分问题是NP完全的，同时给出了该问题存在解的一个必要非充分条件；以三角形填充问题为例，找到了两种全局无损的放置动作并证明了其正确性，该结果对设计快速近似算法具有启发意义；根据解格局拓扑结构的不同特点，给填充问题类进行了复杂性分层，其意义在于给近似算法的设计提供理论分析依据。
英文文摘	The decision form of polygon packing problem is defined as follows: Given a rectangle container with known length and width and a set of polygons with known number of sides, shapes and sizes, the research is asked whether these polygons can be placed into the rectangle container without overlapping. If there is a solution, then positions and orientations of all the polygons in the rectangle container are required, otherwise, the research may simply answer that no such solution exists. Polygon packing problem widely appears in many fields such as plane layout, leather and apparel industries and has important applications; many problems such as layout problems, most packing problems and cutting problems in practice can be reduced to polygon packing problem. At the same time it is also an important problem in theoretical computer science, e.g. in algorithm designing and complexity analysis. Demands in theory and practice on this problem make it necessary to develop efficient algorithms for it, but since it is NP-hard, it is more likely that approximate algorithms are developed other than exact algorithms, many researchers usually give restrictions to this problem before actually handling it, one example is that the polygons to be packed can only translate or take some finite orientations, rotation is not allowed. Such simplifications have practical significance and the corresponding problem is NP complete and called translational polygon packing problem. To develop an efficient algorithm to solve polygon packing problem, we ignore the practical significance of polygon packing problem and lie the emphasis on its theoretical aspect, the concept rigid placement is proposed in this paper and the problem is transformed from a continuous problem to a combinatory optimization problem, then we place the polygons into the rectangle container one by one. As to how to choose a polygon and place it at a good position, we propose the thought of least destruction strategy. Based on this, an efficient approximate algorithm called least destruction algorithm is developed for solving the problem. Complexity analysis of the algorithm proves that it is a polynomial time algorithm, and the computational results show that the algorithm is efficient. To improve the quality of solutions, the corresponding backtracking algorithm is also proposed, computational results show that it greatly improves the quality of solutions, and there is little loss of speed, that shows it is robust and practical. Although the rigid placement model may affect the quality of solutions, that is, the optimal solutions may be ignored, it has its physical origin, intuitively, a rigid placement may make good use of space. An algebraic method for exactly solving polygon packing problem is proposed. Since polygon packing problem is a continuous problem, real numbers are concerned during the course of problem solving, and Turing machine cannot handle real numbers precisely, so the computability of real numbers is analyzed, and the property and impact of real number computation deviations are pointed out. The topologies of solutions of polygon packing problem are also analyzed. The theorem of rigid placement is proposed and proved, that is, an instance has a solution if and only if it has a compact solution, this helps change the solution space of polygon packing problem from infinite to finite without hurting the original problem, the theorem forms the basis for exactly solving the problem. Based on this, an exact algebraic method is established. Under this algebraic method, we can get the optimal solution if deviations of real number computation are ignored. Though the real number computation cannot be exact theoretically, we can get arbitrary computational precision if required. Under this algebraic method, the exact solutions can be obtained via solving a multinomial equation set whose size is polynomial of the problem size. The computational complexity of polygon packing problem relies only on the complexity for solving the corresponding multinomial equation set of polynomial size. The computational complexity for solving a multinomial equation set is not discussed and it needs further consideration. Two types of computational complexity are proposed and analized, that is, the finity-relevant computational complexity and infinity-relevant computational complexity. Some instances are given to illustrate their characteristics. Based on this, some fundamental problems that are related to polygon packing problem are also considered, e.g. rectangle triangulation problem which is a special case of polygon packing problem is proved to be NP-complete, at the same time a necessary condition that makes the problem have a solution is also given; Taking triangle packing problem as an example, two types of placement of triangles are proved to be optimal under the current configuration, these discoveries may be helpful to develop efficient approximate algorithms for polygon packing problem; A complexity hierarchy for some packing problems is drawn according to the characteristics of the topologies of the solutions and this provides a theoretical basis for approximate algorithms designing.