下载文档原格式
组合优化问题的模型与算法分析在当今复杂多变的世界中，组合优化问题无处不在。
从物流运输的路径规划，到生产线上的任务分配，从通信网络的资源配置，到金融投资的组合选择，组合优化问题的身影贯穿于各个领域，影响着我们的生活和工作效率。
那么，究竟什么是组合优化问题？又有哪些模型和算法可以帮助我们有效地解决它们呢？组合优化问题，简单来说，就是在一个有限的集合中，寻找出满足特定条件的最优元素组合。
这里的“最优”通常是指在某个给定的目标函数下，能够取得最大值或最小值的组合。
目标函数可以是成本最小化、利润最大化、时间最短化等等，而满足的条件则可能包括资源限制、技术要求、法规约束等。
为了更好地理解和解决组合优化问题，人们提出了各种各样的模型。
其中，最常见的有整数规划模型、图论模型和动态规划模型。
整数规划模型是将问题中的变量限制为整数的一种数学规划模型。
比如，在决定是否要在某个地点建设工厂时，我们可以用 0 表示不建设，用 1 表示建设，这样就将问题转化为了一个整数规划问题。
整数规划模型能够精确地描述许多实际问题，但由于其求解难度较大，在处理大规模问题时往往会遇到计算瓶颈。
图论模型则是利用图的结构来表示问题。
例如，在交通网络中，城市可以看作图的节点，道路可以看作图的边，通过对图的分析来寻找最优的路径。
图论模型直观形象，对于一些具有明显网络结构的问题非常有效。
动态规划模型是将一个复杂的问题分解为一系列相互关联的子问题，并通过求解子问题来逐步得到原问题的解。
它适用于具有重叠子问题和最优子结构性质的问题。
有了模型，接下来就需要算法来求解。
常见的算法包括精确算法和启发式算法。
精确算法能够保证在有限的时间内找到问题的精确最优解。
其中，分支定界法是一种常用的精确算法。
它通过不断地将问题的解空间进行分支和界定，逐步缩小搜索范围，最终找到最优解。
但精确算法的计算时间往往随着问题规模的增大而呈指数增长，对于大规模问题往往难以在可接受的时间内得到结果。
组合优化问题的高效求解算法研究组合优化问题是运筹学中的重要问题之一，它在实际生活中具有广泛的应用。
由于该问题具有N P难度，因此，设计高效的算法是非常需要的。
本文将围绕组合优化问题的高效求解算法展开讨论。
一、组合优化问题的概念及其常见模型组合优化问题的基本定义是，在一定规则和约束下，在给定的一定集合选取或排列一些元素，使得选择或排列后的值最大或最小。
通常，组合优化问题包含以下几个要素：1.可选元素集合；2.可行解的集合（满足约束条件的元素组合）；3.目标函数（用来衡量解的优劣）；4.优化目标（最大还是最小化目标函数）。
常见的组合优化问题可分为以下几种：1.最大割问题：在一个无向图中，将顶点分为两个集合，使得交界面上的边数最大。
2.旅行商问题：给定一系列城市和每两个城市之间的距离，求解访问每个城市一次的最短路径。
3.最小斯坦纳树问题：给定一个有向图和一个集合，求解一个树，使得这个树包含所给集合中的所有点，且树上的所有边的权值之和最小。
4.最大团问题：在一个无向图中，找一个包含最多顶点的完全子图。
二、组合优化问题的高效算法由于组合优化问题通常为N P难问题，因此，一些已知算法只能在特定条件下运作。
例如，猜测与复杂性理论推论表明，除非P = N P，所有固定规模的完全选择问题都要在指数时间内求解。
下面介绍几种常见的高效求解算法。
1.贪心算法贪心算法是一种直观且快速的求解组合优化问题的方法。
它采用贪心策略，在每一步选择最符合当前条件的解，并根据目标函数进行评价。
贪心算法的时间复杂度通常为O(n)或O(m log m)，但并不保证一定得到最优解。
2.动态规划算法动态规划算法也是一种常见的组合优化问题求解方法。
它采用递推式，将大规模的问题分解成若干个子问题，并通过求解子问题的最优解来得到整体最优解。
动态规划算法的时间复杂度一般为O(n^2)或O(nm)。
3.分支定界算法分支定界算法是一种常见的高效求解组合优化问题的算法。
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。
在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。
这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。
求解这类组合最优化问题方法分为精确算法和近似算法两类。
常用的精确算法有动态规划、分支定界和枚举等。
精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。
当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。
利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。
近似算法是指在合理的计算时间内找到一个近似的最优解。
近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。
近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。
1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。
拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。
首先对于NP难的优化问题，其数学模型须具有可分离性。
通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。
利用乘子的迭代更新来实现子问题解的协调。
列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。
与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。
组合优化问题的随机算法研究随机算法是一种常见的算法，在许多问题的解决中都有广泛应用。
其中，组合优化问题的随机算法是一个热门的研究领域，这种算法可以应用于图论、网络流、线性规划等领域，涵盖了很多实际应用的问题。
本文将从组合优化问题的基本定义开始，系统地讨论随机算法在组合优化问题中的应用以及研究。
组合优化问题是什么？组合优化问题指的是在一个集合中选择一些元素，使得这些元素满足某种限制条件，同时又使得某个目标函数取得最值。
例如，在一组点的集合中选择若干点，使得这些点之间的距离和最小，或者在一组数列中选择若干个数，使得它们的和等于一个给定的数且最接近这个数。
这类问题可以归纳为三类：组合、求和、排列。
组合问题指的是从n个元素中选出k个元素，组成一个集合，且元素的顺序不重要。
这类问题的大小可以用C(n,k)=n!/(k!(n-k)!)来计算。
求和问题指的是从一组数列中选出一些数，使得它们的和等于一个给定的值。
这种问题可以用0-1背包问题作为代表。
排列问题指的是从n个元素中选出k个元素，组成一个集合，而元素的顺序是重要的。
这种问题的大小可以用P(n,k)=n!/(n-k)!来计算。
组合优化问题的求解方法组合优化问题的求解可以采用暴力破解和优化算法两种方法。
暴力破解法指的是枚举所有可能的解，然后选取最优的解。
这种方法在问题规模较小时，求解速度较快。
但是当问题规模较大时，暴力破解法的时间复杂度为指数级别，难以应用于实际问题中。
优化算法是一种更加高效的求解组合优化问题的方法。
其中最常用的优化算法是贪心算法、动态规划算法和随机算法。
贪心算法在每一步选择中，都采取在当前状态下最优（或最有利）的选择。
由于贪心算法具有时间复杂度低、易实现等优点，因此在实际问题中得到了广泛应用。
动态规划算法是适用于多阶段问题的一种动态计算方法。
该方法可以将一个问题分解为若干个阶段，每一个阶段都对应着一个决策，并且决策会影响下一阶段状态的转移。
组合优化问题的求解方法研究与应用随着计算机技术的发展和普及，各种组合优化问题的求解逐渐成为数学、计算机等领域的热点问题，广泛应用于运筹学、工程学、管理学、物理学等诸多领域。
本文将从问题的定义和特点、传统求解方法、近年新兴求解方法等多个方面进行讨论，希望对组合优化问题的求解方法有所启示和帮助。
一、问题的定义和特点组合优化问题的一般形式为：在有限集合中选取若干元素，使得这些元素满足某些限制条件，并在满足这些条件的基础上，使得某个目标函数最优。
具体而言，这个目标函数可以是最大化（最小化）某个值，比如利润、成本、效率等数值。
而限制条件则是我们需要遵守的约束条件，例如资源受限、时间限制、空间限制等。
组合优化问题的特点在于它是NP难问题，即它的求解难度随着问题规模的增大呈指数级增加，如果采用穷举法进行求解，则算法的时间复杂度将达到O(n!)，这是一种非常低效的算法。
二、传统求解方法在传统的求解方法中，最常用的是搜索算法。
搜索算法按照问题的性质构造出一个搜索树，通过深度优先搜索（或广度优先搜索）来遍历整个搜索树，找到最优解或次优解。
搜索算法的主要优势在于其能够找到问题的全局最优解，但由于组合优化问题的特殊性，搜索算法在时间和空间消耗方面都非常高，对于复杂的问题规模很难获得令人满意的解。
传统方法的另一个重要的问题就在于其缺乏对于实际实现的支持，为了解决这个问题，近年来涌现了一些新兴的求解方法。
三、近年新兴求解方法在数学和计算机领域中，近年来涌现了一些新兴的求解方法，例如基于模拟退火、遗传算法等的元启发式算法，以及甚至还有基于人工神经网络等机器学习技术的自适应求解方法。
这些方法基于现代计算机的强大计算能力，通过迭代求解的方式不断优化候选解，可以在处理组合优化问题的时候具有更好的速度和效率。
其中元启发式算法是一种非常常用的求解方法，这种方法是通过随机化的方式来探索问题空间，可以从复杂的搜索空间中找到近似最优解，在实际应用中表现出了非常好的效果。
组合优化问题与现代优化算法在当今这个充满挑战和竞争的时代，优化问题无处不在。
无论是在生产制造、物流配送、资源分配，还是在金融投资、网络通信、科学研究等领域，我们都面临着如何在有限的资源和条件下，找到最优的解决方案，以实现最大的效益或最小的成本。
这就是组合优化问题的核心所在，而解决这些问题的关键则在于现代优化算法的应用。
组合优化问题是一类在离散的解空间中寻找最优解的问题。
这些问题的特点是解的数量有限，但可能的组合数量非常庞大，使得通过穷举法找到最优解几乎是不可能的。
例如，旅行商问题（TSP）就是一个经典的组合优化问题。
假设有一个旅行商要访问 n 个城市，每个城市只能访问一次，最后回到出发城市，要求找到一条最短的路径。
对于 n 个城市，可能的路径数量是 n! ／ 2，当 n 较大时，这个数字会变得极其巨大。
另一个常见的组合优化问题是背包问题。
假设有一个容量有限的背包和一组物品，每个物品都有一定的价值和重量。
我们需要选择一些物品放入背包，使得背包中的物品总价值最大，同时总重量不超过背包的容量限制。
这看似简单，但由于物品的选择组合众多，要找到最优解并非易事。
为了解决这些复杂的组合优化问题，科学家们提出了各种各样的现代优化算法。
这些算法大致可以分为两类：确定性算法和随机性算法。
确定性算法通常基于精确的数学模型和严格的推理，能够在有限的时间内找到最优解或者证明问题的最优解不存在。
例如，线性规划算法就是一种常见的确定性算法。
它适用于目标函数和约束条件都是线性的组合优化问题，可以通过求解一系列线性方程组来找到最优解。
然而，确定性算法的应用范围往往受到问题性质的限制，对于许多复杂的非线性或非凸的组合优化问题，它们可能无能为力。
随机性算法则是通过随机的搜索过程来寻找最优解。
这类算法虽然不能保证一定能找到最优解，但在大多数情况下能够找到一个较好的近似解。
常见的随机性算法包括遗传算法、模拟退火算法、粒子群优化算法等。
遗传算法的灵感来源于生物进化的过程。
组合优化问题的解决算法研究在当今复杂多变的世界中，组合优化问题无处不在。
从物流配送的路径规划，到生产流程的优化安排，再到通信网络中的资源分配，这些问题都涉及到如何在众多可能的组合中找到最优的解决方案。
组合优化问题的求解不仅对于提高效率、降低成本具有重要意义，也是推动科学技术发展和社会进步的关键因素之一。
组合优化问题的特点在于其解空间通常是一个有限但极其庞大的集合，要从中找出最优解往往是一项极具挑战性的任务。
这类问题通常具有离散的决策变量、明确的约束条件和一个要优化的目标函数。
例如，在旅行商问题中，目标是找到一条经过所有城市且总路程最短的路径，决策变量就是城市之间的连接顺序，约束条件可能包括每个城市只能访问一次。
解决组合优化问题的算法众多，其中一些经典的算法包括精确算法和启发式算法。
精确算法能够保证在有限的时间内找到问题的最优解，但往往由于计算复杂度高，只能用于规模较小的问题。
分支定界法就是一种常见的精确算法。
它通过将问题不断分解为子问题，并为每个子问题设定上下界，逐步缩小搜索范围，最终找到最优解。
动态规划法也是一种精确算法，它将复杂问题分解为重叠的子问题，并通过保存子问题的解来避免重复计算。
然而，在面对大规模的组合优化问题时，精确算法往往力不从心，这时启发式算法就发挥了重要作用。
启发式算法不能保证找到最优解，但能够在可接受的时间内得到一个较好的近似解。
贪心算法是一种简单而常见的启发式算法，它在每一步都做出当前看起来最优的选择，不考虑对后续步骤的影响。
模拟退火算法则借鉴了物理中固体退火的过程，通过在搜索过程中引入一定的随机性，避免陷入局部最优解。
遗传算法模拟了生物进化的过程，通过选择、交叉和变异等操作来逐步优化解。
蚁群算法是一种受到蚂蚁觅食行为启发的算法。
蚂蚁在寻找食物的过程中会释放一种信息素，其他蚂蚁会根据信息素的浓度来选择路径。
在蚁群算法中，通过模拟这种信息素的释放和更新机制，来引导算法找到较好的解。
软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software,2011,22(9):1985−1993 [doi: 10.3724/SP.J.1001.2011.03948] +86-10-62562563 ©中国科学院软件研究所版权所有. Tel/Fax:∗组合优化问题简约与算法推演郑宇军1,2+, 薛锦云1,2, 凌海风31(中国科学院软件研究所计算机科学国家重点实验室,北京 100190)2(江西师范大学江西省高性能计算重点实验室,江西南昌 330027)3(南京大学管理工程学院,江苏南京 210093)Combinatorial Optimization Problem Reduction and Algorithm DerivationZHENG Yu-Jun1,2+, XUE Jin-Yun1,2, LING Hai-Feng31(The State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China)2(Provincial Key Laboratory of High Performance Computing, Jiangxi Normal University, Nanchang 330027, China)3(School of Management and Engineering, Nanjing University, Nanjing 210093, China)+ Corresponding author: E-mail: yujun.zheng@Zheng YJ, Xue JY, Ling HF. Combinatorial optimization problem reduction and algorithm derivation.Journal of Software, 2011,22(9):1985−1993. /1000-9825/3948.htmAbstract: A unified algebraic model is used to represent optimization problems, which uses a transformationalapproach that starts from an initial problem specification and reduces it into sub-problems with less complexity. Themodel then constructs the problem reduction graph (PRG) describing the recurrence relations between the problem,and derives an algorithm with its correctness proof hand-in-hand. A prototype system that implements the formalalgorithm development process mechanically is also designed. This approach significantly improves the automationof algorithmic program design and helps to understand inherent characteristics of the algorithms.Key words: combinatorial optimization problem; problem reduction; algorithm derivation; PAR (partition-and-recur); correctness proof摘要: 针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.关键词: 组合优化问题;问题简约;算法推演;PAR(partition-and-recur);正确性证明中图法分类号: TP301文献标识码: A组合优化问题是指在离散有限的数学结构中和给定的约束条件下寻找目标函数最优值的问题,它是组合数学、运筹学和理论计算机科学中长期研究的重要问题之一.传统的组合优化算法设计策略(如动态规划、贪心、回溯等)有着各自不同的适用范围,而且缺乏策略选择的有效标准[1],因而极大地限制了算法开发的形式化∗基金项目: 国家自然科学基金(61105073, 60773054); 科技部国际科学技术合作项目(2008DFA11940)收稿时间: 2009-09-25; 定稿时间: 2010-09-061986 Journal of Software软件学报 V ol.22, No.9, September 2011和自动化水平.20世纪80年代以来,人们提出了一些抽象代数模型来精确刻画组合优化问题的结构和求解过程,但复杂的表示法使其难以在计算机上进行有效实现.如Helman[2]的搜索模型将解空间视为一组连接子的集合,求解过程就是通过反复执行连接子的横向组合和纵向组合来对解空间进行隐式枚举搜索,组合过程中采用的不同计算辅助关系可以用于不同类型的算法设计[3,4].Kumar和Kanal等人[5−7]对与或图、游戏树等特定结构上的最优化问题进行了形式化的定义,通过抽象的分支限界和动态规划方法对这些结构上的多种具体算法进行了统一归纳,从而简化了算法的开发和证明,但其应用范围在很大程度上受到数据结构的限制,一些搜索算法还要求特殊的结构性质,适应性和可扩展性不强.Bird和Meertens提出的B-M公理表示法[8,9]同样提倡从问题规约出发,通过应用融合(fusion)和提升(promotion)等一系列定理逐步推导算法,但该方法需要在各种问题结构上定义大量的定理和规则,其表示法不易于使用[10],且推导结果很难直接转换为结构化程序.除了递归程序变换等较简单的功能,早期的算法生成系统[11−13]需要设计人员的干预较多.南京大学开发的NDADAS系统[14,15]基于函数分解树模型来将问题逐步分解成可直接求解的若干子函数,通过CASE结构形成、直接替换、递归节点生成等规则来支持许多算法的机械化设计,但并不保证这些规则和分解出的子函数能够满足求解需求,其后续研究也转向使用机器学习等技术简化人工设计[16].美国Kestrel研究所的KIDS系统[17]则通过演绎推理、有限差分、部分求值和类型求精等一系列技术生成算法程序,后续的Designware系统[18]进一步将设计知识分类存放在数据库中,并借助范畴论工具来提高自动化水平.不过,其最关键的设计策略在很大程度上仍需要手工选择,问题/算法的种类和范围也始终存在较大的限制.以我们前期的PAR(partition-and-recur)方法[1,19]研究为基础,同时借鉴相关研究中算法形式化开发和程序自动生成的思想,本文提出了一种新的组合优化算法设计方法.它从组合优化问题的代数规约出发,通过谓词和量词演算将问题逐步简约为更易求解的子问题,在此基础上得到正确高效的算法程序;开发的实验系统已成功应用于多个典型组合优化算法的自动生成.1 问题简约模型和方法使用结构化的代数规约,一个问题可由问题输入域以及从输入到输出的构造方式来刻画.给定问题输入域D和输出域R,那么一般组合优化问题的规约可定义为P(d)≡(Q z:c(z)∧z∈ζ(d):f(z)) (1) 其中:Q为二元运算符q的一般化量词,对于优化类问题,q一般取min或max;ζ:D→SET(Z)为解空间生成函数;c:Z→BOOLEAN为解的可行性约束函数;f:Z→REAL为解的目标函数.人们处理复杂问题的一个基本方法就是将其分解为更简单的子问题.采用穷举法求解问题(1)时,需要搜索的解空间为{z|c(z)∧z∈ζ(d)},那么我们对同一结构上问题间的关系作如下定义[20]:定义1. 问题P′(d′)=〈ζ′,c′,f〉称为问题P(d)=〈ζ,c,f〉的等价问题,当且仅当{z|c′(z)∧z∈ζ′(d′)}={z|c(z)∧z∈ζ(d)}.定义2. 问题P′(d′)=〈ζ,c′,f〉称为问题P(d)=〈ζ,c,f〉的子问题,当且仅当ζ′(d′)⊆ζ(d)并且∀z∈ζ(d′):c′(z)⇒c(z).定义2还可以细分为以下3种情况:定义3. 如果P′(d′)=〈ζ,c′,f〉为P(d)=〈ζ,c,f〉子问题,且c′≠c,那么称P′(d′)=〈ζ,c′,f〉为P(d)的派生子问题.定义4. 问题P(d′)=〈ζ,c,f〉称为问题P(d)=〈ζ,c,f〉的直接子问题,当且仅当ζ(d′)⊆ζ(d).定义5. 问题P′(d′)=〈ζ,c∧c1,f〉称为问题P(d)=〈ζ,c,f〉的强化约束子问题(简称为强化问题);相反,P(d)称为P′(d′)的放松约束问题(简称为放松问题).将函数分解关系代入初始问题规约,通过谓词和量词演算来对规约进行变换,不断地将问题简约为更易求解的子问题,最后根据简约过程和演算结果得出问题的求解算法.问题的简约过程可以通过问题简约图(problem reduction graph,简称PRG)形象地描述.PRG是一个有向无环图,其中每一个节点都代表一个问题;图中的一个无入边的特殊节点称为根节点,它表示要求解的原始问题;无出边的节点称为叶节点或终点,它们表示可直接求解的问题;设问题P(d)被简约为一组子问题P1(d1),郑宇军等:组合优化问题简约与算法推演1987P2(d2),…,P n(d n),那么从P(d)到每个P i(d i)绘制一条边,P i(d i)称为P(d)的子节点(0<i≤n).2 算法推演技术2.1 基本演算规则从问题的初始代数规约出发,通过不断应用数学定律、一阶谓词演算、量词性质等演算规则,能够对问题规约进行不断变化,从而进行问题简约和算法推演.除了常用的数学定律和谓词演算规则外,表1中的量词性质在组合优化算法推演中起到关键性的作用.Table 1Main quantifier rules for algorithm calculation表1主要的量词演算规则Rules Equations Remark Cartesian product (Q i,J: r(i)∧s(i,J): f(i,J)) ≡ (Q i:r(i): (Q J: s(i,J): f(i,J)))variable, and s(i,J) is a predicate of i and J Range splitting (Q i: r(i): f(i)) ≡ (Q i: r(i)∧b(i):f(i)) q (Q i: r(i)∧¬b(i): f(i))b(i) is a boolean expression of iSingle range (Q i: i=k: f(i)) ≡f(k) Range disjunction (Q i: r(i)∨s(i): f(i)) ≡ (Q i: r(i):f(i)) q (Q i: s(i): f(i)) q is an idempotent operator Functional associativity (Q i: r(i): f(i) Q g(i)) ≡(Q i: r(i):f(i)) q (Q i: r(i):g(i))Functional commutativity (Q i: r(i):(Q j:s(j):f(i,j))) ≡ (Q j:s(j):(Q i:r(i):f(i,j)))General distributivity (Q i: r(i): g⊗f(i)) ≡g⊗(Q i: r(i): f(i))ٔ is a commutative binary operator and isassociative with respect to q, and x is not afree variable of gFunctional distributivity g((Q i:r(i):f(i))) = (P i:r(i):g(f(i))) g(a q b)＝g(a)p g(b) where P is thegeneralized quantifiers of p ∀-rule (∀i: r(i)∧s(i): p(i)) ≡ (∀i: r(i): s(i) => p(i))∃-rule (∃i: r(i)∧s(i): p(i)) ≡ (∃i: r(i): s(i)∧p(i))Conditional separation (Q i: r(i)∨(s(i)∧t(i)): f(i)) ≡(Q i: r(i): f(i)) q (Q i: s(i): f(i)), if t(i) (Q i: r(i): f(i)), else基于抽象规约(1),对组合优化问题进行简约的出发点一般有两种:(1) 分解生成函数ζ(d)=ζ1(d)∪ζ2(d)∪…∪ζm(d);(2) 分解约束函数c(z) = c1(z)∪c2(z)∪…∪c m(z).将函数分解关系代入初始问题规约,之后就可以通过谓词和量词演算来对规约进行变换,不断将问题简约为更易求解的子问题,最后根据简约过程和演算结果得出问题的求解算法.2.2 算法推演与效率提升毋庸置疑,抽象规约(1)本身就蕴含了问题的求解算法,即遍历解空间ζ(d)中每一个满足可行性约束c(z)的解,找出其中目标函数值f(z)最优的一个.但这样的穷举算法在绝大多数情况下都是低效的,各种高效算法则往往需要设计人员去发现和证明.而使用逻辑推演来简约问题,能够自动确定问题与子问题最优解之间的关系,同时,自动发现并合并相同或等价的子问题(即在PRG中不能包含两个相同或等价的问题节点),从而提高了算法的求解效率.例1:最大子段和问题.给定一个整数序列A n={a1,a2,…,a n},要找出其元素之和最大的子序列.设ss为所有子序列的生成函数,那么该问题的规约为MS(A n)≡(MAX z:z∈ss(A n):sum(z)) (2) 该问题的生成函数可以划分为ss(A n)={a n}∪ss(A n−1)∪{z|z=z′↑a n∧z′∈ss(A n−1)∧last(z′)=a n−1},即A n的子序列要么是A n−1的子序列,要么以a n结尾(可以只含a n).将其代入问题规约并进行推演可得:MS(A n)1988 Journal of Software软件学报 V ol.22, No.9, September 2011≡(MAX z:z=a n∨z∈ss(A n−1)∨(z=z′↑a n∧z′∈ss(A n−1)∧last(z′)=a n−1):sum(z))≡[范围分裂]max((MAX z:z=a n:sum(z)),(MAX z:z∈ss(A n−1):sum(z)),(MAX z′:z′∈ss(A n−1)∧last(z′)=a n−1:sum(z′↑a n)))≡[单点范围和卷叠]max(a n,MS(A n−1),(MAX z′:z′∈ss(A n−1)∧last(z′)=a n−1:sum(z′)+a n))≡[令MS′(A n)≡(MAX z:z∈ss(A n)∧last(z)=a n:sum(z))]max(a n,MS(A n−1),MS′(A n−1)+a n)≡[a n≤MS′(A n−1)+a n]max(MS(A n−1),MS′(A n−1)+a n)其中,MS′(A n)为原问题的派生子问题,对其继续进行推演可得:MS′(A n)≡[等价问题](MAX i:0<i≤n:(Σj:i≤j≤n:a j))≡[范围分裂:(0<i≤n)≡(0<i≤n−1)∨(i=n)]max((MAX i:0<i≤n−1:(Σj:i≤j≤n:a j)),(MAX i:i=n:(Σj:i≤j≤n:a j))≡[单点范围和卷叠]max(MS′(A n−1)+a n,a n))将原问题与子问题的简约关系合并,就可以得到如下线性算法:Algorithm MS(A n).beginms←0; ms′←0;for i=1 to n doms′←max(ms′+a i,a i);ms←max(ms,ms′);return ms;end.例2:最小时间调度问题.给定要在某机器上完成的一组任务S n={1,2,…,n},其中,第i项任务需要的处理时间为t i.要确定这些任务的一个调度,使得所有任务的完成时间之和最小.设z为S n的一个排列,那么其中第z i项t).令ps返回一个序列的所有排列,那么该问题的规约任务的完成时间就是(Σj:0<j≤i:j zMTS(S n)≡(MIN z:z∈ps(S n):(Σi:0<i≤n:(Σj:0<j≤i:t))) (3)j z该问题的生成函数可以划分为ps(S n)=(∪i:0<i≤n:s i↑ps(S n\{s i})),将其代入问题规约并进行推演可得:MTS(S n)t))≡(MIN z:z∈(∪k:0<k≤n:k↑perms(S n\{k})):(Σi:0<i≤n:(n+1−i)i z≡[交叉积](MIN k:0<k≤n:(◊z:z∈perms(S n\{k}):nt k+(Σi:0<i≤n−1:(n−i)t)))i z≡[范围分裂和单点范围](MIN k:0<k≤n:nt k+(◊z:z∈perms(S n\{k}):(Σi:0<i≤n−1:(n−i)t)))i z≡[卷叠](MIN k:0<k≤n:nt k+MST(S n\{k}))这样得到的是原问题与其多个子问题的简约关系,其蕴含的算法效率并不高.不过,对此还可以做进一步简约:易证MST(S n\{i})−MST(S n\{j})≤n(t j−t i),故i≤j⇒nt i+MST(S n\{i})≤nt j+MST(S n\{j}),那么令k*=(MIN k:0<k≤n:t k),简约关系中其他子问题就都可以消去,最后得到:郑宇军 等:组合优化问题简约与算法推演1989MTS (S n )≡*k nt +MST (S n \{k *}) (4)从简约关系(4)中很容易得到求解该问题的线性算法,即按t k 由小到大的顺序安排任务调度.例1和例2推演得到的都是线性算法,但它们既有相同点又有不同点.相同点是二者都存在最优子结构性质,这是动态规划法的基本特征[21];基于最优结构的贪心算法则可视为是动态规划法的精化[22].例1推演得到的算法属于动态规划算法;而例2还满足特殊的性质,故进一步得到了贪心算法.许多可应用贪心算法的问题都具有如下性质:在将原问题简约到多个子问题时,如果这些子问题满足某些附加的单调性质,使得只有一个或少数几个子问题需要保留,而其他的子问题可以被舍去.我们称此简约为“贪心简约”.形式化地,设问题P (d )与其子问题之间的简约关系为(以最小值问题为例)P (d )≡min(P 1(d ⊙e 1)⊕w (e 1),P 2(d ⊙e 2)⊕w (e 2),…,P n (d ⊙e n )⊕w (e n )) (5) 其中,e 1,e 2,…,e n ∈E 称为问题的单点域,⊙:D ×E →D 称为单点函数,⊕为目标函数值域上的二元算子.如果能够找到E 上的某个单调函数v ,使得v (e i )≤v (e j )⇒P i (d ⊙e i )⊕w (e i )≤P j (d ⊙e j )⊕w (e j ),那么可以选取各单点对象中v 值最小的e k ,这样就得到了对于P (d )的贪心简约:P (d )≡P k (d ⊙e k )⊕w (e k ) (6) 这种方式不仅适用于推演符合拟阵结构[23]的贪心选择算法,也同样适用于不符合拟阵结构的其他贪心算法(如以上最小时间调度算法、Huffman 编码算法等).2.3 分支限界、近似和参数化策略动态规划和贪心法是寻求多项式时间算法的两种基本方法,难以有效应用对于大量NP 难题.分支限界法是为复杂问题设计确定性算法的主要手段,通过问题简约过程来生成分支限界算法的基本步骤为:(1) 将原始问题标记为活节点,其目标函数收益为0;(2) 选取一个活节点,对其进行简约得到一组子问题;(3) 对于可直接求解的子问题,计算其目标函数值,并对当前最优解进行更新;(4) 舍去那些无解或不能导致最优解的子问题,而将其余的子问题标记为活节点,其目标函数收益由父节点及其到当前节点的简约关系确定;(5) 重复第(2)步,直至不再有未处理过的活节点.设某个子问题的目标函数值上界为x ,而该节点的当前收益为y ,如果x +y 不优于当前最优解,那么可以判断其不能导致最优解,该节点可以被舍弃.问题的上界可由其放松问题的解来确定,而活节点的选取方式则决定了分支限界法是按照广度优先、深度优先还是效益优先的方式执行.以0-1背包问题为例,给定背包容量W 和一组物品A n ={a 1,a 2,…,a n },其中,a i 的重量和价值分别为w (a i )和v (a i ),那么问题规约为KS (A n ,W )≡(MAX z :w (z )≤W ∧z ∈P (A n ):v (z )) (7) 其生成函数为幂集函数,分解形式为P (A n )=P (A n −1)∪{z |z =z ′∪{a n }∧z ′∈P (A n −1)},那么推演过程为: KS (A n )≡(MAX z :w (z )≤W ∧(z ∈P (A n −1)∨(z =z ′∪{a n }∧z ′∈P (A n −1))):v (z ))≡[范围分裂]max((MAX z :w (z )≤W ∧(z ∈P (A n −1):v (z )),(MAX z ′:w (z ′∪{a n })≤W ∧z ′∈P (A n −1):v (z ′∪{a n })))≡[卷叠]max(KS (A n −1),(MAX z ′:w (z ′)∧z ′≤W −w (a n )∧z ′∈P (A n −1)=v (z ′)+v (a n )))≡[条件分离和卷叠]111max((,),(,())()), if ()((,), elsen n n n n n KS A W KS A W w a v a w a W KS A W −−−−+⎧⎨⎩≤ 问题的简约可一直持续到KS (Φ,W ′)=0,采用深度优先的策略就得到了问题的回溯算法.再通过上界限制能1990 Journal of Software软件学报 V ol.22, No.9, September 2011够显著减小搜索范围,其上界可为无约束问题MAX z:z∈P(A n):v(z)的解v(A n),也可为放松约束的连续背包问题的解(由贪心算法求得).许多NP难题在实际应用中只需要找到一个近似最优解.在算法推演的过程中,可以舍弃一些复杂的问题节点来提高算法效率,并根据问题的简约关系来估算解的近似程度.仍以0-1背包问题为例,不失一般性,令w(a i)≤W,那么在前述推演的基础上可得:KS(A n,W)≡(MAX i:0<i≤n:KS(A n\a i,W−w(a i))+v(a i)).如果对各个子问题KS(A n\a i,W−w(a i))不再进行完整的推演,而只是分别进行贪心简约,那么就得到了近似比为2的多项式算法.进一步地,如果贪心简约是从PRG的第k层开始进行,那么算法的近似比将为1+1/k,即0-1背包问题具有多项式时间的近似框架[24].NP完全问题并不意味着该问题的所有实例都是难以求解的.参数复杂性理论[25]就将问题的部分输入视为参数,那么在特定的参数范围内,问题也很可能是容易求解的.以最小顶点覆盖问题为例,给定图G=(V m,E n),要找出V中的一个最小顶点集,使得对于E中的每一条边x,左端点x.a和右端点x.b至少有一个属于该顶点集,那么问题的规约为MVC(V m,E n)≡(MIN z:(∀x:x∈E n:x.a∈z∨x.b∈z)∧z∈P(V m):|z|) (8) 令N(a)表示与顶点a相邻的所有边集,那么约束条件可分解为(e n.a∈z∧(∀x:x∈E n\N(e n.a):x.a∈z∨x.b∈z))∨(e n.b∈z∧(∀x:x∈\N(e n.b):x.a∈z∨x.b∈z)).在此基础上,可对问题作如下推演:MVC(V m,E n)≡(MIN z:((e n.a∈z∧(∀x:x∈E n\N(e n.a):x.a∈z∨x.b∈z))∨(e n.b∈z∧(∀x:x∈\N(e n.b):x.a∈z∨x.b∈z)))∧z∈P(V m)):|z|)≡[范围分裂]min((MIN z:e n.a∈z∧(∀x:x∈E n\N(e n.a):x.a∈z∨x.b∈z)∧z∈P(V m):|z|),(MIN z:e n.b∈z∧(∀x:x∈\N(e n.b):x.a∈z∨x.b∈z)∧z∈P(V m):|z|))≡[拆分V m]min((MIN z′:(∀x:x∈E n\N(e n.a):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.a}):|z′∪{e n.a}|),(MIN z′:(∀x:x∈\N(e n.b):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.b}):|z′∪{e n.b}|))≡[单点范围和范围分裂]min((MIN z′:(∀x:x∈E n\N(e n.a):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.a}):|z′|)+1,(MIN z′:(∀x:x∈\N(e n.b):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.b}):|z′|)+1)≡[卷叠]min(MVC(V m\{e n.a},E n\N(e n.a))+1,MVC(V m\{e n.b},E n\N(e n.b))+1)而对于判断图G=(V m,E n)是否有度数小于k的最小顶点覆盖的参数化问题MVC(V m,E n,k),基于上述推演过程可得MVC(V m,E n,k)≡min(MVC(V m\{e n.a},E n\N(e n.a),k−1),MVC(V m\{e n.b},E n\N(e n.b),k−1)).这样就得到了该问题的固定参数算法,由于问题简约至多只需要执行k层,得到的参数化算法的时间复杂度为O(2k|V|).由于参数化算法可以方便地进行组合,对原始问题规约还可以再次基于生成函数的分解关系P(V m)=P(V m−1)∪{z|z=z′∪{v m}∧z′∈P(V m−1)进行如下推演:MVC(V m,E n)≡(MIN z:z:(∀x:x∈E n:x.a∈z∨x.b∈z)∧(z∈P(V m−1)∨(z=z′∪{v m}∧z′∈P(V m−1))):|z|)≡[范围分裂]min((MIN z:(∀x:x∈E n:x.a∈z∨x.b∈z)∧z∈P(V m−1):v(z)),(MIN z′:(∀x:x∈E n\N(v m):x.a∈z′∨x.b∈z′)∧z′∈P(V m−1):|z′∪{v m}|))≡[卷叠和单点范围]郑宇军 等:组合优化问题简约与算法推演1991min(MVC (V m −1,E n ),(MIN z ′:(∀x :x ∈E n \N (v m ):x .a ∈z ′∨x .b ∈z ′)∧z ′∈P (V m −1):|z ′|+1))≡[卷叠]min(MVC (V m −1,E n ),MVC (V m −1,E n \N (v m ))+1) 将上述两步组合得到的算法效率为O (k |V |+2k k 2);基于问题核心推演,还可以进一步提高算法效率至O (k |V |+1.32k k 2)乃至更高[26,27].3 算法生成系统我们设计了基于问题简约的组合优化算法生成系统,其主要由以下5个部件组成,结构如图1所示.(1) 算法设计器:系统的核心部件,运用演算规则进行问题简约和算法生成;(2) 知识库:有关问题基础结构的知识库,包括各种基本数据类型(如集合、序列、树、图等)的代数规约,其上的典型生成函数(如幂集函数、排列函数、子序列函数、子树/图函数等)及其分解关系等;(3) 算法模式库:存放典型的问题简约模式及泛型算法;如果新问题的简约模式与库中某个模式同态,那么可以直接通过泛型实例化来得到其求解算法.表2中列出了系统预定义的主要抽象算法模式;(4) 定理证明器:如果生成函数或约束函数的分解关系、贪心简约中的单调函数等是由用户自行指定的,那么定理证明器将对有关结果的正确性进行证明;(5) 程序生成器:将抽象算法自动转换为可执行语言(如C++,C#,Java 等)的算法程序,并针对特定目标平台进行代码优化. Algorithm pattern library Algorithm designerKnowledge base Program generator Theorem prover User interfaceFig.1 Basic structure of combinatorial optimization algorithm generation system图1 组合优化算法生成系统的基本结构Table 2 Reduction-Based algorithm patterns and their application problems表2 简约算法模式及应用问题Algorithm patternsApplication problems Single singleton greedy reductiondeadlines and penalties for a single processor Multiple singleton greedy reductionSingle machine scheduling, Huffman coding tree, single-source shortest path, shuttle transportation Sequencial reductiondecomposition Binary reductionmaximum-flow/minimum-cut General reduction Integer knapsack, traveling salesman, set covering, multiple vechile routing4 结束语算法问题是计算机科学中最为核心的问题之一.本文提出了一种基于代数规约的组合优化算法推演技术,它通过一组算法演算规则对问题进行简约,并基于简约关系构造正确高效的问题求解算法.该方法综合了动态规划、贪心、分支限界多种传统算法设计策略,并在传统方法与近似算法、参数化算法等NP 难题的有效处理方法之间建立了联系,更加有利于人们对算法本质特征的理解.实验系统证明,该方法能够有效支持大量算法程序的自动生成,后续研究的重点将放在对并行算法自动生成的支持上.我们相信,随着最关键的算法设计形式化和自动化程度的不断提高,整个软件工程自动化的研究将有望取得新进展.1992 Journal of Software软件学报 V ol.22, No.9, September 2011References:[1] Xue JY. A unified approach for developing efficient algorithmic programs. Journal of Computer Science & Technology, 1997,12(4):103−118.[2] Helman P. An algebra for search problems and their solutions. In: Kanal L, Kumar V, eds. Proc. of the Search in ArtificialIntelligence. Berlin: Springer-Verlag, 1988. 28−90.[3] Helman P. A common schema for dynamic programming and branch and bound algorithms. Journal of the ACM, 1989,36(1):97−128. [doi: 10.1145/58562.59304][4] Luan SM, Li W, Ma SH. Algorithm framework: An operational approach to algorithm relocation. Journal of Software, 1999,10(7):679−684 (in Chinese with English abstract). /1000-9825/10/679.htm[5] Kumar V. A unified approach to problem solving search procedures [Ph.D. Thesis]. Department of Computer Science, Universityof Maryland, 1982.[6] Kumar V, Kanal LN. A general branch and bound formulation for understanding and synthesizing and/or tree search. ArtificialIntelligence, 1983,21(1-2):179−198. [doi: 10.1016/S0004-3702(83)80009-5][7] Kumar V. A general heuristic bottom-up procedure for searching and/or graphs. Information Science, 1991,56(1-3):39−57.[8] Bird RS. An introduction to the theory of lists. NATO ASI Series F, 1987,36:5−42.[9] Meertens L. Algorithmics towards programming as a mathematical activity. In: Bakker JW, Vliet JC, eds. Proc. of the CWI Symp.on Mathematics and Computer Science. 1986. 289−334.[10] Backhouse RC. An exploration of the bird-meertens formalism. Technical Report, CS 8810, Department of Computing Science,Groningen University, 1988.[11] Burstall RM, Darlington J. A transformation system for developing recursive programs. Journal of the ACM, 1977,24(1):44−67.[doi: 10.1145/321992.321996][12] Bibel W, Hornig KM. LOPS—A system based on a strategical approach to program synthesis. In: Biermann AW, Guiho G,Kodratoff Y, eds. Proc. of the Automatic Program Construction Techniques. New York: MacMillan, 1984. 69−89.[13] Neugebauer G, Fronhöfer, B, Kreitz C. XPRTS—An implementation tool for program synthesis. In: Metzing D, ed. Proc. of the13th German Workshop on Artificial Intelligence, Vol.216. Informatik-Fachberichte, 1989. 348−357.[14] Xu JF, Dai M, Lü J. Algorithm design automation system NDADAS. Journal of Computer Research and Development,1990,27(2):1−5 (in Chinese with English abstract).[15] Lü J. Framework of algorithm correctness in NDADAS. Science in China, Series F, 1991,34(7):875−884.[16] Zhang JZ, Fei ZM. Automatic generation of software based on scheme. Journal of Computer Research and Development,1992,29(6):1−6 (in Chinese with English abstract).[17] Smith DR. KIDS: A knowledge-based software development system. In: Lowry M, McCartney R, eds. Proc. of the AutomatingSoftware Design. Cambridge: The MIT Press, 1991. 483−514.[18] Smith DR. Designware: Software development by refinement, high integrity software. IEEE Computer, 2001,20(4):10−19.[19] Xue JY. PAR method and its supporting platform. In: Proc. of the 1st Asian Working Conf. on Verified Software (AWCVS 2006).2006. 29−31.[20] Zheng YJ, Xue JY. A problem reduction based approach to discrete optimization algorithm design. Computing, 2010,88(1-2):31−54. [doi: 10.1007/s00607-010-0085-0][21] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithm. 2nd ed., New York: McGraw-Hill, 2001. 339−341.[22] Bird RS, de Moor O. From dynamic programming to greedy algorithms. In: Proc. of the IFIP TC2/WG 2.1 State-of-the-Art Reporton Formal Program Development. LNCS 755, 1993. 43−61.[23] Edmonds J. Matroids and the greedy algorithm. Mathematical Programming, 1971,1(1):171−236. [doi: 10.1007/BF01584082][24] Sahni S. Approximate algorithms for the 0/1 knapsack problem. Journal of the ACM, 1975,22(1):115−124. [doi: 10.1145/321864.321873][25] Downey RG, Fellows MR. Fixed-Parameter tractability and completeness I: Basic theory. SIAM Journal of Computing, 1995,24(4):873−921. [doi: 10.1137/S0097539792228228]郑宇军等:组合优化问题简约与算法推演1993[26] Chen JE, Huang ZX, Kanjd IA, Xia G. Polynomial time approximation schemes and parameterized complexity. Discrete AppliedMathematics, 2007,15(2):180−193. [doi: 10.1016/j.dam.2006.04.040][27] Li SH, Wang JX, Chen JE. Kernelization techniques and its applications to parameterized computation. Journal of Software, 2009,20(9):2307−2319 (in Chinese with English abstract). /1000-9825/3593.htm [doi: 10.3724/SP.J.1001.2009.03593]附中文参考文献:[4] 栾尚敏,李未,马绍汉.算法框架:算法重定位的一种可操作的方法.软件学报,1999,10(7):679−684. /1000-9825/10/679.htm[14] 徐家福,戴敏,吕建.算法自动化系统NDADAS.计算机研究与发展,1990,27(2):1−5.[16] 张家重,费宗铭.基于算法构架的软件自动产生.计算机研究与发展,1992,29(6):1−6.[27] 李绍华,王建新,陈建二.参数计算中核心化技术及其应用.软件学报,2009,20(9):2307−2319. /1000-9825/3593.htm [doi: 10.3724/SP.J.1001.2009.03593]郑宇军(1979－),男,福建莆田人,博士,高级工程师,主要研究领域为运筹学,自动化软件工程.凌海风(1975－),女,博士,副教授,主要研究领域为软件工程方法学.薛锦云(1947－),男,教授,博士生导师,主要研究领域为软件形式化和自动化.。
