一种求解一维装箱问题的拟人算法毕业论文.doc

摘 要一维装箱问题来源于人们的长期以来的生产实践，是一种组合优化问题。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限是一个已知的正实数。一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问题是一个NP难度问题，因此一维装箱问题具有很高的理论价值。另一方面，一维装箱问题出现在实际生产的一些领域，因此也具有很高的实际价值。迄今为止，国内外学者提出了许多用来求解一维装箱问题的严格算法和近似算法。一方面，严格的最优算法所花时间太长，实际部门无法忍受。另一方面，近似算法由于可能快速地生成最优解或者接近最优解而为实际生产部门所广泛采用。人类把物体往容器中装，已有几千年以上的经验。这些生活经验可引导出高效率的算法。本文提出了一种拟人算法。算法由三个部分组成。第一部分是降序最佳适合算法，用于生成初始解。第二部分是邻域搜索算法。给定一个解，用邻域搜索算法可以通过迭代改进这个解。本文的邻域定义的思想来源于“天之道损有余而补不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最优解，将搜索引向有希望的区域，从而提高算法的效率。跳坑策略的思想来源是“三十六计走为上”。本文的程序计算了一组共17个国际公认的问题实例。这组问题实例分为两类。第一类为8个问题实例，目前尚未确定其客观最优解。第二类为9个问题实例，目前已经确定了其客观最优解。拟人算法对第一类问题实例中的6个问题实例找出了与当前已知最好解质量相同的解。拟人算法还证明了TEST0068这个问题实例的目前已知最好解正是客观最优解。拟人算法快速地找出了第二类问题实例中全部9个问题实例的客观最优解。计算结果表明，拟人算法是一种有效的求解一维装箱问题的近似算法。关键词： NP难度； 拟人； 邻域搜索； 跳坑； 装箱AbstractThe one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin packing problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all items into the bins with the objective of minimizing the number of occupied bins, subject to two following constraints. (1) Each item is packed into exact one bin. Each item cannot be divided into several parts and put into different bins. (2) The sum of weight of all items of each bin cannot exceed its capacity. The one dimensional bin packing problem is of both highly theoretical and practical values. On one hand, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one dimensional bin packing problem appears in some real world factories.So far, many exact algorithms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, approximation algorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.Mankind have more than several thousands of years of experience to pack items into containers. The experience can induce efficient algorithm. A quasi-human algorithm is presented in this paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborhood comes from a Chinese motto “It is the Way of Heaven to diminish superabundance, and to supplement deficiency”. The third part is off-trap strategy, which is used to jump off local optimum and guide the search into promising areas, so as to improve the algorithm. The idea of the off-trap strategy comes from a Chinese motto “decamping being the best”.Computational experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The second class consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algorithm proves that the best known solution for benchmark instance named as TEST0068 up to now is optimal. For all 9 instances of the second class, our algorithm finds out optimal solutions quickly.The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.Keywords: NP-hard; Quasi-human; Local search; Off-trap; Bin packing目 录1 绪论11.1 引言11.2 问题描述11.3 研究现状21.4 本论文的主要结构52 算法描述62.1 拟人算法的大致框架62.2 生成初始解72.3 邻域搜索72.4 跳坑策略93 程序设计113.1 程序流程113.1.1 读取文本文件中的数据133.1.2 生成初始解133.1.3 邻域搜索143.1.4 释放内存153.2 调试程序154 计算结果165 结论18参考文献19致谢211 绪论1.1 引言当前世界经济高速发展，人口日益增加，资源日渐紧张。人们在生产生活中希望提高效率，节约资源，以实现可持续发展。在运筹学领域有一类所谓最优化问题。最优化问题的一般形式是：在满足约束条件的前提下，给出自变量的值，使得目标函数值最优 (通常是使得目标函数值最小或者最大)。一维装箱问题1来源于人们的长期以来的生产实践，是一种最优化问题，一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问题是一个NP难度问题，因此一维装箱问题具有很高的理论价值。在现实的工业、商业、交通、通信、军事等领域出现了大量的所谓NP难度问题，例如车间调度问题、货郎担问题等等。人们虽然目前不能证明，但是强烈相信NP难度问题不存在时间复杂度为多项式的完整算法。所谓完整算法，对于优化问题来说就是能保证找到最优解的算法，对于判定问题来说就是能够保证正确判定的算法。另一方面，一维装箱问题出现在实际生产的一些领域，因此也具有很高的实际价值。世界各国学者已经对一维装箱调度问题做了数十年的研究，人们还提出了许多种算法来求解一维装箱调度问题。另外，在现实中存在二维、三维、多维的装箱问题。本文仅讨论一维装箱问题。1.2 问题描述本文研究的这种一维装箱问题的描述如下。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限是一个已知的正实数。为了将问题描述得确切，本文提出一种形式化描述。表示物体的集合。表示物体的重量。表示每个箱子所能容纳的物体的重量之和的上限。表示所用箱子的集合。，是已知的。和是变量。问题是要在满足如下两个约束条件的前提下，使得所用箱子的个数尽可能地小。 (1.1) (1.2)其中，。1.3 研究现状 当前求解NP难度问题的算法分为两类：完整算法和近似算法。以一维装箱问题为例，本文介绍这两类算法。完整算法2也称为严格算法，其本质是毫无遗漏的穷举，因此能保证找到问题的最优解，这是完整算法的优点。完整算法的缺点是计算时间太长，实际部门无法忍受，因此只能用于计算较小规模的问题实例。近似算法是当前研究的主要方向。当今时代，在纯粹科学研究，通信、交通运输、工程设计和企事业管理部门，在社会的军事、政治和商业的斗争中涌现出大量NP难度的问题。若按经典的纯粹数学家们所熟悉的穷举方法来求解，则计算时间动辄达到天文数字，根本没有实用价值。学术界许多有经验的人认为对于这些问题根本上就不存在完整、精确而不是太慢的求解算法。于是人们寄希望于非完整的启发式算法。启发式算法属于近似算法。这种算法对于很刁钻古怪的例子可能会失败，但在通常面临的实际情况下却能算得既精确又相当地快。到哪里去寻求启发？这是一个根本的难点。中国古代的画论有“外师造化内得心源”的说法，即认为智慧应源于大自然与自身的心灵。事实上，自然界中的各种现象以及人类共同生活中的社会经验，尤其是处理相互关系中许多矛盾的各种公关手腕都是很好的源泉。许多数学中的概念方法与策略事实上都是来源于人类对大自然的观察，来源于他们在社会中生存奋斗的社会经验。拟物拟人的途径，本来就是科学的正统，而不是邪门歪道。随着新的有意义的困难问题例如NP难度问题的涌现，公理化符号化的方法会逐渐显出自己的不足，朴素的拟物拟人的途径会逐渐被人们所选用。特别值得指出的是，对于所得的启发式算法，在遇到刁钻的实例而表现出疲软失败的时候，人们可以十分自然地通过分析算法在该次失败中的表现而对它有针对性地加以改善和强化。经过若干次自然的改善和强化之后，一个从实用角度看来叫人很是满意的算法就会呈现在我们的面前3。人们或者运用自身的智慧，或者从大自然得到启发，同时运用良好的编程技术，经常能设计出很好的近似算法，有可能在较短时间内求解大规模问题实例，并达到令人满意的精确度。这种方法被实际部门广泛的使用。这是一条现实的路线。近似算法主要分为以下几种类型：拟物算法和拟人算法。拟物算法和拟人算法是黄文奇提出的用于求解NP-hard难度问题的近似算法。拟物方法4是一个许多人会感到有趣有用的方法。其工作路径是，到物理世界中去寻找出与原始数学问题等价的自然现象，然后观察其中物质运动的演化规律，从中受到启发以得出形式化的、对于数学问题的求解算法。单纯的拟物方法就已能解决许多问题56。在遇到刁钻的问题时还可以将拟物方法和拟人方法联合使用形成所谓拟物拟人方法7。对其工作的方式可作如下解释、描叙和评论。由于物理状态的演化天然地是按照使其Lagange函数的时间积分达到最小值的方式进行，这就决定了拟物算法最终在数学上落实为优化问题。然而用数学方法求解优化问题，常常会碰到计算落入局部极小值陷阱的困难境地，对于如何跳出局部极小值陷阱，让计算走向前景更好的区域中去的问题，拟物方法已无能为力。但是，人类在最近几千年的共同生活中形成了丰富的社会经验，利用这些经验往往可以启发出好的“跳出陷阱”的策略。我们可以将这种把人类的社会经验形式化为算法用以求解某些特殊困难问题的数学问题的方式称为拟人途径8。拟物拟人算法的效率通常比生物遗传算法、神经网络算法、淬火算法要高，其原因是它有针对性地为具体问题找到了非常贴切的物理世界，而不是像在遗传、神经网络、淬火方法中那样依赖于一个惟一的始终不变的因而往往是不太贴切的物理体系。另外，拟人方法是向人学习，而人比遗传、神经网络、淬火世界里的那些蛋白质、单个的神经元及晶体显然有高得多的智慧。当然，这里的关键在于合适的数学形式化前夜的艺术和手段，要得到它们也不是一件很容易的事情，需要长期艰苦细心的工作。这种得出算法的过程的艰苦性，可以说是拟物拟人途径的一个缺点。另外，生物遗传算法、神经网络法、淬火法虽然针对性较差，但其适应性较强，并且亦有其深刻的思想根源和自然背景。在肯动脑筋并且机遇好的时候，拟物拟人与生物遗传算法、神经网络法、淬火法能结合得很好，能产生新的效能更高的算法。至于纯粹的拟人方法910，其途径是将人类在最近几千年的生存斗争中所形成的某些经验某些作法说完整说清楚，然后加以抽象化形式化，最后形成算法以求解NP难度问题。此方法的关键难点在于为给定的NP难度问题找到相应的有悠久历史的人类活动。但是一旦找到，必然能很顺利地发展为高效能的求解算法。优先分配规则算法。人们最早提出的求解一维装箱问题的近似算法是优先分配规则算法。优先分配规则算法以某种优先序依次给定将所有物体装入某个箱子。优先分配规则算法的速度非常快，但是其生成解的质量仍有改进的余地。因为优先分配规则算法速度很快，所以很多学者采用优先分配规则算法来生成初始解。本文介绍降序首次适合算法（first fit decreasing）和降序最佳适合（best fit decreasing）算法。降序首次适合算法是将所有物体按照重量从大到小的顺序排成一个物体序列，然后依次取出序列中的一个物体，在所有能放下这个物体的箱子中，选取序号最小的箱子，把物体放进去。降序最佳适合算法是将所有物体按照重量从大到小的顺序排成一个物体序列，然后依次取出序列中的一个物体，在所有能放下这个物体的箱子中，选取空余最小的箱子，把物体放进去。局部搜索(local search)算法。局部搜索算法给出的解的质量比优先分配规则算法高。局部搜索算法的工作过程是一个迭代的过程：从初始给定的解开始，所有物体装在有穷个箱子中。取出第一个箱子中的所有物体，装入其他箱子。此时某些箱子可能会超重，这是一个格局，称为一个点。然后在与当前格局相近的格局集合(即当前点的邻域)中搜索比当前格局更好的格局。如果在邻域中找到了比当前格局更好的格局，那么接受这个更好的格局，然后继续做迭代。如果当前格局的邻域中没有比当前格局更好的格局，也就是说，当前格局是局部最优解，那么算法停机。具体来说，有两种搜索策略。第一种搜索策略叫做 “见好就收”：检查当前格局的邻域，一旦找到比当前格局好的格局，就接受这个格局，这样就做完了一次迭代，然后继续做迭代；如果当前格局的邻域中没有比当前格局更好的格局，那么邻域搜索停止。第二种搜索策略是找到邻域中最好的格局，如果比当前格局好，就接受这个格局，这样就做完了一次迭代，然后继续做迭代；如果当前格局的邻域中没有比当前格局更好的格局，那么邻域搜索停止。当邻域搜索停止时，如果对应一个解，则接受这个解，继续从新解开始做邻域搜索。如果不对应一个解，则回到当前解，取出第二个箱子中的所有物体，装入其他箱子。此时得到一个格局，从这个格局开始做邻域搜索。依次类推。如果在当前解取出最后的箱子中的所有物体，装入其他箱子。从这个格局开始做邻域搜索，无法得到比当前解更好的解，则算法停机。禁忌搜索(tabu search)算法。禁忌搜索算法是基于局部搜索的一种算法，它可以看作是局部搜索算法的一种改进算法。禁忌搜索算法由Glover11提出。禁忌搜索算法可用于求解各种组合优化问题人们已经提出了多种求解一维装箱问题的禁忌搜索算法12。禁忌搜索算法生成解的质量较高。禁忌搜索算法的工作过程是一个迭代的过程。从初始给定的解开始，所有物体装在有穷个箱子中。取出第一个箱子中的所有物体，装入其他箱子。此时某些箱子可能会超重，这是一个格局，称为一个点。然后在与当前格局相近的格局集合(即当前点的邻域)中搜索比当前格局更好的格局。算法找到当前格局的邻域中目标函数值最小的格局，不论这个格局的目标函数值是否比当前格局小，都接受这个格局。这样就做了一次迭代。然后继续做迭代。像这样做迭代，很容易陷入循环。为了防止循环，禁忌搜索算法设置一个名为禁忌表的数据结构。禁忌表中记录着在最近若干次迭代中访问过的格局，如果这些格局在当前格局的邻域中，那么就把它们从邻域中清除掉。这样就能够在一定程度上避免循环，从而提高搜索效率。因为禁忌搜索会接受比当前格局差的格局，所以它能够跳出局部最优点。当禁忌搜索因为搜索限定时间到而停止时，如果找到了一个解，则接受这个解，将这个解作为当前解，继续做禁忌搜索。如果没有找到一个解，则回到当前解，取出第二个箱子中的所有物体，装入其他箱子。此时得到一个格局，从这个格局开始做禁忌搜索。依次类推。如果在当前解取出最后的箱子中的所有物体，装入其他箱子。从这个格局开始做禁忌搜索，无法得到比当前解更好的解，则算法停机。模拟退火算法。模拟退火算法也是基于局部搜索的一种算法。模拟退火算法也可用于求解各种组合优化问题，包括一维装箱问题13。模拟退火算法检查当前格局的邻域中的格局，如果邻域中的这个格局比当前格局好，则一定接受这个格局；否则以一个大于0 同时小于1 的概率接受这个格局。与禁忌搜索算法一样，模拟退火算法也能跳出局部最优点。遗传算法。遗传算法可用于求解一维装箱问题14。遗传算法的工作过程也是迭代的过程。与局部搜索算法、禁忌搜索算法和模拟退火算法不同的是，遗传算法是将当前一组格局更新为另外一组格局，而不是将当前一个格局更新为另外一个格局。遗传算法首先随机生成一组格局做为所谓初始种群，然后对种群做迭代：从当前种群(当前这组格局)中选择一些格局，对这些格局做遗传操作(交叉、变异等)，从而得到一组新的格局(即一个新的种群)。1.4 本论文的主要结构本学位论文主要由五个部分组成，其内容具体安排如下：第一部分是绪论。主要介绍了本课题的来源、选题背景、问题描述和论文的主要结构。第二部分介绍算法描述。第三部分介绍程序设计。第四部分介绍程序运行的结果。第五部分是本课题研究的结论。2 算法描述人类把物体往容器中装，已有几千年以上的经验。我们可以利用这些生活经验来发展出高效率的算法。本文提出的这种算法是一种拟人算法。算法由三个部分组成。第一部分是降序最佳适合算法（best fit decreasing）用于生成初始解。第二部分是邻域搜索算法。给定一个解，用邻域搜索算法可以通过迭代改进这个解。第三部分是跳坑策略。跳坑用于跳出局部最优解，将搜索引向有希望的区域，从而提高算法的效率。算法三个部分的思想来源均为人类的生产和生活经验，本算法是由拟人途径得到的。定义2.1 某些物体在箱子里，其余物体在箱子外，这称为一个格局。初始格局是所有物体均在箱子外，所有箱子均为空。与初始格局对称的终止格局是所有物体均在箱子里。终止格局的形式化描述为：整数变元，的一组指派表示一个终止格局，其中表示物体放在箱子中，。把对整数变元，的一组指派看成空间中的一个点，将与点在一个、两个或更多个变元上取值不同的点的集合称为的邻域。考虑一个终止格局，如果每个箱子中所装的物体的重量之和均不超过上限，则此终止格局对应着一个解。2.1 拟人算法的大致框架步骤一（初始解的生成）：调用一种简单好想的构造型算法生成初始解。该构造型算法见2.2节。转步骤二。步骤二（判断停机条件）：判断停机条件是否满足，若满足则停机，输出本次计算过程中所找到的最好的解。若不满足停机条件，则转步骤三。停机条件恰有两个：第一，客观最优解已经找到。第二，跳坑次数已经达到上限。只要满足其中一个条件，则算法停机。步骤三（邻域搜索）：从当前解出发，调用邻域搜索算法进行计算，试图寻找一个比当前解更好的解。该邻域搜索算法见2.3节和2.4节。邻域搜索算法执行完毕后，转步骤二。2.2 生成初始解步骤一：开局。将所有物体按照重量从大到小的顺序排好序。这个物体序列记为。所有物体均在箱子外面。将物体放在箱子中。转步骤二。步骤二：考虑当前格局。如果所有物体均在箱子里面，则生成了初始解。如果至少有一个物体在箱子外面，则按照如下手法将一个物体放入箱子。在当前格局中，物体在箱子里，物体在箱子外。如果箱子中的每一个均不能容纳，则将放入箱子。如果箱子中的若干个箱子能容纳，则选取在当前格局空余最小的箱子（如果空余最小的箱子不止一个，则选取其中编号最小的箱子），将放入，从而演化到新格局。转步骤二。2.3 邻域搜索本文提出的邻域搜索的思路来源于人们用箱子装物体的实际经验。当个物体装在个箱子中，首先任意取一个装了物体的箱子，取出其中全部物体，装到其它已装有物体的箱子中去。此时很可能有某些箱子中的物体重量超过上限。然后根据某种方法进行调整，试图使得每个箱子中的物体重量均不超过上限。最终邻域搜索的结果恰有两种：或者成功，或者失败。步骤一：考虑当前解。将当前解的格局记录下来，记为。物体放在箱子中。令。转步骤二。步骤二：如果，则邻域搜索结束。如果，则取出箱子中的所有物体，将的编号改为，将的编号改为。按照从重量大到小的顺序，依次将物体放入已装物体重量之和最小的箱子（如果已装物体重量之和最小的箱子不止一个，则选取序号小的箱子），从而演化到新格局。如果无超重的箱子，则新格局是一个解。将这个解作为当前解，邻域搜索结束。如果有超重的箱子，无不满的箱子，则当前解是客观上的最优解，停机。如果既有超重的箱子，又有不满的箱子，则转步骤三。步骤三：进行调整。如果经过调整后，得到了一个比当前解更好的解，则接受这个解，邻域搜索结束。如果没有找到一个比当前解更好的解，则返回到当前解的格局。转步骤二。所谓调整，是一个迭代的过程。已知一个终止格局，用一个新的终止格局取代老的终止格局，这是迭代的一步。在叙述如何进行迭代之前，要给出邻域的定义。取一个超重的箱子，记为。取一个不满的箱子，记为。现在要将中的若干物体放入中，将中的若干物体放入中。目的是要减轻中物体的重量，增加中物体的重量。中国人有句格言“天之道损有余而补不足15”。我们所设计的邻域是基于这句格言的。我们采用的目标函数是由Fleszar和Hindi16提出的目标函数。给定一个终止格局，目标函数值等于所有箱子中的物体重量的平方的和。调整的目的是要在所用箱子数不变的前提使得目标函数值尽可能地小。形式化描述如下：minimize (2.1)其中是所用箱子数，是箱子中所装物体重量。对于点，是的一个邻点。若，则称为的邻域中的下降点。第一种邻域记为。将超重的箱子中的一个物体取出放入不满的箱子。第二种邻域记为。将超重的箱子中的一个物体与不满的箱子中的一个物体交换。第三种邻域记为。将超重的箱子中的一个物体与不满的箱子中的两个物体交换。第四种邻域记为。将超重的箱子中的一个物体与不满的箱子中的三个物体交换。可以推广到,.,，其中是箱子中所装的物体个数。因为有了，则不必考虑。可以用两次取代。第五种邻域记为。将超重的箱子中的两个物体与不满的箱子中的一个物体交换。第六种邻域记为。将超重的箱子中的两个物体与不满的箱子中的两个物体交换。可以推广到,.,，其中是箱子中所装的物体个数。Loh，Golden和Wasil1提出了两种邻域和。Fleszar和Hindi16提出了两种邻域和。本文提出的邻域与这些邻域类似。差别在于本文考虑一个超重的箱子和一个不满的箱子。文献116考虑任意两个箱子。已知一个点，考虑其邻域，若一个邻点对应的目标函数值严格小于当前点对应的目标函数值，则这个点称为下降点。微调的思路如下所述。第一，从一个给定的终止格局开始，这是初始点。第二，设在任一时刻的值已算出，首先按照某种自然的顺序依次考虑当前点的邻点。若下降点集非空，则用第一个下降点作为在时刻的值。我们将这种从到的过渡称为下降步骤。若下降点集为空，则已知点为函数的局部最小值点，于是按照某种基于拟人思路的“跳坑”策略将计算从点跳到其邻域中的一个确定的新点。我们可将这种从到的过渡称为逃出步骤。以上思路虽然是本质的，但有一个小漏洞需要补平。即在逃出步骤中，若点按照跳坑策略逃出到，则很可能从的角度来看，老点是的邻域中的下降点，于是很有可能从出发的下降步骤是回到。即计算走了回头路。为补平这一漏洞，我们可以设置变元禁集。这样，我们的寻优搜索的思路框架被发展为如下步骤：步骤一：从一个给定的终止格局开始，这是初始点。将变元禁集之初始集赋为空集。转步骤二。步骤二：考虑当前点的邻域。有些邻点是由对禁集中的变元赋值而得到的。除去这样的邻点不考虑。按照某种自然的顺序考察邻域，如果找到了一个下降点，则见好就收，接受此下降点。如果对邻域搜索完毕，没有找到下降点，则按跳坑策略跳到一个点。转步骤三。步骤三：若当前点对应一个解，则停止。若计算时间已超限，则停止。否则更新变元禁集。以下我们描述跳坑策略和更新变元禁集的步骤。2.4 跳坑策略当前点为局部最小值点，在所有超重的箱子中均匀地随机选取一个箱子，在这个箱子中的所有物体中均匀地随机选取一个物体，在所有不满的箱子中均匀地随机选取一个箱子，将从中取出，放入。这个跳坑策略的思想来源依然是“天之道损有余而补不足”。变元禁集的演化规则如下：第一，如果从老点到是按下降步骤操作的，则置变元禁集为空。第二，如果从老点到是按逃出步骤操作的，则将对应的变元加入变元禁集。3 程序设计本文的程序设计采用已故卓越美籍荷兰裔计算机科学家Edsger Wybe Dijkstra提出的结构化程序设计思想。Edsger Wybe Dijkstra早在1951年就学习了计算机程序设计，然后参与了一些荷兰的大工程例如Fokker友谊飞机的开发，其中机翼震动的计算需要编写程序。因为编写庞大程序的需要，Edsger Wybe Dijkstra提出了结构化程序设计思想。结构化程序设计可归纳为“自顶向下，逐步求精”。结构化程序设计由计算机科学家提出，但是其思想根源并不是纯粹科学，而是人类在长期生存斗争中的经验。军事家提出“分而治之”，“集中优势兵力，各个歼灭敌人”。这些说法是结构化程序设计思想的来源。在军事上，如果敌人多而且强，则设法将敌人分割，集中兵力和火力将敌人各个歼灭。作者在写程序时，如果程序难而且复杂，不好写，则首先将程序分成一些模块，然后集中思维和时间去写每一个模块的程序。所谓“自顶向下”是指首先将程序分割为几个大模块，从而写出主函数main()的程序，然后对复杂的大模块，再分割成若干小模块，如果小模块仍然较复杂，则依此类推，继续分割，直到小模块容易被编程者写出程序为止。所谓“逐步求精”是指在分割程序的过程中，程序的面貌越来越清晰，针对每个小模块，写出清晰的程序。最终将所有模块合并，成为所需要的完整的程序。作者对面向对象的程序设计也曾经浅尝。结构化程序设计思想与面向对象的程序设计思想并无实质性矛盾，在需要引入对象概念的场合，这两者可以很好地结合。例如可以采用结构化程序设计来写底层的核心的程序，采用面向对象的程序设计来设计外表的吸引人的界面。3.1 程序流程整个程序的流程如图3.1所示。整个程序可分为四个模块。第一个模块是读取文本文件中问题实例的数据，调用库函数malloc()为各种数据结构分配内存。这个模块的程序简单，无需再分解。第二个模块是生成初始解。这个模块的程序较简单，无需再分解。第三个模块是邻域搜索。这个模块是重点，程序复杂，本身需分成一些更小的模块。第四个模块是释放内存。这个模块的程序最简单，只需调用库函数free()就可以，无需再分解。图3.1 整个程序的流程作者写程序时遵循如下四条原则。第一，要有整块的时间来写程序，不要烦，不要急。第二，要有好的草稿纸，举个例子，画图辅助自己写程序。第三，草稿纸要写得干净，不要折，写上页码，作为原始文档好好保存。第四，自顶向下，逐步求精。3.1.1 读取文本文件中的数据一个benchmark问题实例存储在一个文本文件中，以名为TEST0005的问题实例为例，存储在名为TEST0005.txt的磁盘文件中，其格式如下。第1行：57表示物体的重量总共恰有57种不同的重量。第2行：10000表示箱子的容量是10000。第3行：49643表示重量为4964的物体恰有3个。依此类推。第59行：402表示重量为40的物体恰有2个。在C语言中，要读取文本文件中的数据，首先定义一个FILE类型的指针FP，然后利用库函数fopen()来打开文件，例如FP = fopen("e:TEST0005.txt","r")，其中e:TEST0005.txt是文本文件所在目录以及文件名，r表示以只读方式打开文件，最后利用库函数fscanf()文件指针,格式字符串，变量地址)来读取文本文件中的数据，例如fscanf(FP,"%d",&numberOfDifferentItemWeights)表示读取FP指针指向的文本文件中一个符号串，将其转化为十进制整数，存储在变量numberOfDifferentItemWeights中。本文的程序采用库函数malloc()来给数据分配内存。与之对称地，当程序运行结束的前夕，调用库函数free()来释放用malloc()分配的内存。本模块中使用的主要数据结构如下。int NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS表示物体总共有多少种不同的重量。int CAPACITY_C_OF_THE_BINS表示箱子容量。int * ITEM_WEIGHTS是整型数组名，此数组记录所有不同的重量的值。int * NUMBER_OF_ITEMS_OF_WEIGHTS是整型数组名，此数组记录每种重量的物体有多少个。int NUMBER_OF_ITEMS表示物体总数。int * WEIGHT_OF_ITEMS是整型数组名，此数组记录每个物体的重量。NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS，CAPACITY_C_OF_THE_BINS，ITEM_WEIGHTS，NUMBER_OF_ITEMS_OF_WEIGHTS是题目给定的，可以直接从文本文件中读取。NUMBER_OF_ITEMS，WEIGHT_OF_ITEMS可以根据已知的信息算出。3.1.2 生成初始解生成初始解的函数命名为generate_initial_solution()。此模块中所使用的主要数据结构如下。int * BIN_NUMBER_OF_ITEMS记录在初始解中，每个物体放在哪个箱子中。int * SPARE_SPACE_OF_BINS记录每个箱子的剩余空间。int NUMBER_OF_OCCUPIED_BINS表示使用的箱子数。int * ITEMS_NUMBER_IN_EACH_BIN是二维整型数组名，其中记录每个箱子中放了哪些物体。程序生成初始解后，将初始解作为当前解。有_IN_CURRENT_SOLUTION_PATTERN后缀的变量是属于对应当前解的终止格局的。int * BIN_NUMBER_OF_ITEMS_IN_CURRENT_SOLUTION_PATTERN表示在对应当前解的终止