布局问题是一种经典的组合优化问题,具有建模和求解上的双重复杂性。自从该问题问世以来,就被应用到许多工程领域,吸引了来自工程、数学、计算机等领域的学者对其进行研究,并取得了大量成果。由于布局问题在求解上具有NP完全性,且布局问题本身种类繁多,因此出现了大量算法对其进行研究和求解。1990年Dyckhoff发表的布局问题分类法论文和2007年Gerhard W(a|¨)scher等人发表的改进的布局问题分类法论文都对布局问题的分类进行了归类和编码。他们都对纷繁复杂的C&P问题进行了系统的组织和归类,并各自得到了一套关于布局问题分类的编码系统。这两套编码简单易懂,解决了C&P问题之间可参考性不足的问题,其影响力相当大。本文以近年出现的关于布局问题的文献为基础,研究这些文献所应用的算法、证明手段、达到的效果,把各种算法进行归类和总结,编制了针对布局问题求解算法的两类代码系统;同时,通过对典型文献所使用的算法进行研究和归类,给出求解方法的发展趋势和各种算法适合求解的问题类型。这样,我们在面对新问题的时候,就可以根据这套系统对算法进行合理选择或指导新算法的系统产生,克服手工设计新算法的缺点。本文首先,对求解布局问题的文献结构进行研究,找到各类求解文献的共同点,提出算法分类系统的总体结构。其次,提出分类系统的各分类标准并对各分类标准进行细化,按照分位原则对代码进行编写建立起第一类编码系统。再次,根据研究深度的不同,将算法分类系统进行分级建立起第二类编码系统并给出编码的文字表达形式;通过对典型算法分类实例的代码编写验证了该套编码系统的有效性和实用性。然后,对所编代码进行网上建立及运行,以方便研究者进行查询、研究和分析。最后,对全文进行了总结,同时展望了后续的研究方向。本文的工作为总结布局问题求解算法的体系以及理清不同算法之间纷繁复杂的关系提供了方法和工具。另外本文在分类研究的基础上,也将统计各类算法的使用频率以及它们与C&P问题的对应关系,从而掌握算法设计的总体趋势和原则,用于指导算法设计。