约束条件下联盟生成研究进展（烟台大学：任子仪、童向荣）.pdf

第14卷第3期智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804054 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展任子仪，童向荣 (姻台大学计算机与控制工程学院，山东烟台264005)】摘要：联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个Agt都具有理性和自利性的特性，为了追求自身的利益最大化而选择和其他的Agεt进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述，主要包括4部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解联盟生成求近似最优解和约束条件下联盟生成求最优解。关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图：联盟博弈；动态规划中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0413-10 中文引用格式：任子仪，童向荣.约束条件下联盟生成研究进展机.智能系统学报，2019,14(3)：413-422 英文引用格式：REN Ziyi,TONG Xiangrong.Research progress of constrained coalition formation.CAAI transactions on intelli- gent systems,2019,14(3:413-422. Research progress of constrained coalition formation REN Ziyi,TONG Xiangrong (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:Coalition formation is one of the most important challenges in the research of multiagent systems.Currently, our main problem is how to divide Agent to maximize the social welfare.We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests.An Agent integrates with another Agent, which also maximizes the interest of the whole system.At present,the coalition formation problem presents notable computational challenges.If constraints are added during the coalition process,new algorithms are needed to solve the problem more rapidly and effectively.This paper mainly summarizes the study of coalition structure generation under constraint conditions.This paper comprises four parts:the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution,the near-optimal solution after formation of the coalition structure,and the optimal solution to the constrained coalition formation. Keywords:coalition structure;social welfare;coalition formation;constraint;characteristic function;coalition structure graph;coalition game;dynamic programming 联盟生成是多Agent系统(multi--agent system, 中的其他Agent合作，共同合作活动的目的是达 MAS)研究基本问题之一a,主要将Agent进行合到最佳的标准。当Agent通过组建联盟共同工作作或协商，使其效用增加。Agent联盟基本上被时，联盟结构生成就会发生。目标就是求一种认为在MAS的框架内的一组Agent,.愿意与这组最优的联盟结构，使得所求的社会福利最大，并返回其值4。收稿日期：2018-04-26.网络出版日期：2018-06-20 Agent在联盟生成时达到最优方案不一定是基金项目：国家自然科学基金项目(61572418)：山东省科技发展计划项目(2016GGX109004) 全局最优解，但是应该是Nash最优解6-或者次优通信作者：童向荣.E-mail:twr@ytu.edu.cn 解，因此联盟生成主要包括以下活动：

DOI: 10.11992/tis.201804054 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展任子仪，童向荣（烟台大学计算机与控制工程学院，山东烟台 264005）摘要：联盟生成是在多 Agent 系统的研究中最为重要的挑战之一。如何对 Agent 进行划分使所得社会福利最大化是当前面临的主要问题。假设每个 Agent 都具有理性和自利性的特性，为了追求自身的利益最大化而选择和其他的 Agent 进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述，主要包括 4 部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图；联盟博弈；动态规划中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0413−10 中文引用格式：任子仪, 童向荣. 约束条件下联盟生成研究进展[J]. 智能系统学报, 2019, 14(3): 413–422. 英文引用格式：REN Ziyi, TONG Xiangrong. Research progress of constrained coalition formation[J]. CAAI transactions on intelligent systems, 2019, 14(3): 413–422. Research progress of constrained coalition formation REN Ziyi，TONG Xiangrong (School of Computer and Control Engineering, Yantai University, Yantai 264005, China) Abstract: Coalition formation is one of the most important challenges in the research of multiagent systems. Currently, our main problem is how to divide Agent to maximize the social welfare. We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests. An Agent integrates with another Agent, which also maximizes the interest of the whole system. At present, the coalition formation problem presents notable computational challenges. If constraints are added during the coalition process, new algorithms are needed to solve the problem more rapidly and effectively. This paper mainly summarizes the study of coalition structure generation under constraint conditions. This paper comprises four parts: the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution, the near-optimal solution after formation of the coalition structure, and the optimal solution to the constrained coalition formation. Keywords: coalition structure; social welfare; coalition formation; constraint; characteristic function; coalition structure graph; coalition game; dynamic programming 联盟生成是多 Agent 系统 (multi-agent system， MAS) 研究基本问题之一[1-2] ，主要将 Agent 进行合作或协商，使其效用增加。Agent 联盟基本上被认为在 MAS 的框架内的一组 Agent，愿意与这组中的其他 Agent 合作，共同合作活动的目的是达到最佳的标准。当 Agent 通过组建联盟共同工作时，联盟结构生成就会发生[3]。目标就是求一种最优的联盟结构，使得所求的社会福利最大，并返回其值[4-5]。 Agent 在联盟生成时达到最优方案不一定是全局最优解，但是应该是 Nash 最优解[6-7]或者次优解，因此联盟生成主要包括以下活动：收稿日期：2018−04−26. 网络出版日期：2018−06−20. 基金项目：国家自然科学基金项目 (61572418)；山东省科技发展计划项目 (2016GGX109004). 通信作者：童向荣. E-mail：txr@ytu.edu.cn. 第 14 卷第 3 期智能系统学报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019

·414· 智能系统学报第14卷 l)联盟结构生成：Agent之间进行协商生成共有7种情况，分别是{a}、{a2、{a3}、{a,a2}、联盟，但不考虑各个联盟之间的协商。 {a1,a、{a2,a3}、{a1,2,a3l,联盟结构一共存在5种 2)解决每个联盟优化问题：将Agent的任务情况，分别是{a,{a2,{a从、{a,{a2,a从{a2l,{a1,a从和资源集中在一起，共同解决问题。Agent之间 {a3h,{a1,2}和{a1,a2,a3o 进行协商使联盟的社会福利尽可能最大化，即寻定义2社会福利。社会福利即为联盟结构找最优的方法使得联盟本身的效用最大化。 CS中所有的联盟C,ie1,2,,k的收益之和，将 3)划分值：在进行收益分配的时候，常用的联盟的值记为v(C),并且要求(C)≥0，联盟结构方法有两种，即公平（每个Agent所得到的收益是的社会福利记为V(CS),将具有最大的社会福利 Agent在博弈中的贡献的体现)和稳定（存在没联盟结构称为最优联盟结构，记为CS,其最优社有和其他Agent协商而单独形成自己的自私利益会福利记为V(CS),则联盟)。同样，存在很多方法寻找和创建一个最优的 'CS)=∑C 联盟一协商或搜索以及用于找出解决问题的几定义3次加性。对于任意的不相交的联盟种潜在的方法，例如：遗传算法、博弈论、粒子群 S,T∈N,都存在v(SUT)≤v(S)+v(T)。换言之，算法等。但是，随着研究的不断深入，在现实世 a,{a2小，，{an}为最大社会福利的联盟结构。界的应用中有一些联盟结构是不允许生成的⑧。定义4特征函数。给定一个n个Agent的目前，联盟研究的热点问题主要是约束条件下博弈，C是一个联盟，v(C)是指C和N-C两个联盟生成。在现有研究中，很多文献已经考虑 Agent博弈中C的最大效用，(C)称为联盟C特将联盟进行广泛应用，例如：通过形成联盟，自主征函数(characteristic function),规定v(O)=0。传感器可以改善某些区域的监控情况；认识无 1.2博弈类型线电网络可以增加它们的吞吐量；购买者可以在常用的联盟博弈模型中，通常用货币来表通过批量购买而获得较低的价格，自主连接车示联盟的价值（或奖励）。在进行博弈的过程辆进行护航工作2)；形成联盟促进社交网络关中，假设存在一个在Agent之间可以自由流动的系B1等。交换媒介（如货币），每个Agent可以根据自己的在Agent联盟研究发展中，Sandholm等u最绩效得到相应的货币，这种博弈被称为“单边支先提出最坏情况有限界联盟结构生成；Ych等6 付”博弈或可转移效用(transferable utility,TU)博首次使用动态规划算法联盟生成并求得精确最优弈。相反，联盟的绩效是用向量表示的，直接指解；随着研究的不断深入，Agent数量的增加，先定每个成员的绩效，Agent只能服从这种分配方前的算法越来越不能满足当前的需求，Dang等叨案，不能对分配方案进行修改，这种博弈被称为首次提出建立次优联盟结构并求得次优解；不可转移效用(non-transferable utility,NTU)博 Greco等u经过进一步研究，提出了一种新的联盟弈。在多Agent系统中，可转移效用博弈受到了结构生成的方式—约束联盟结构，即在生成联很大的关注。盟的过程对联盟添加约束。 1)特征函数博弈 1基本定义特征函数博弈(characteristic function games,. CFGs)是联盟的价值完全取决于它所包含的 1.1主要定义 Agent的值。将特征函数博弈定义为(N,v),其中假设所有的Agent都是理性的，并使用合作 N表示Agent数据集，v是一个函数，称为特征函博弈建模进行Agent之间的合作和协商。在博弈数，对于每个联盟C映射到函数中的值v(C)记为中，令N是一个Agent集，其中n=W表示N中 v:2w→R。 Agent的个数，则N=(a1,a2,,an,联盟即N中非 2)分区博弈空的子集。在分区博弈(partition function games,.PFGs)中定义1联盟结构。对于任意联盟C,在C上联盟的价值不仅仅取决于所包含的Agent的值，形成的联盟结构CS={C,C2,,Ck,其中UCS=C, 也会受非成员分区的影响。将分区博弈定义为并且对于任意i,j∈L,2,…,,i≠j都需要满足 (N,w),其中N表示Agent数据集，w是一个分区 C:∩C,=0。函数，每个嵌入式联盟(C,CS)映射到函数中的值例1一个集合N={a,a2,a,N上的联盟一是w(C,CS)或w(C,CS)

·416· 智能系统学报第14卷 2联盟生成的复杂度命题1表明，在联盟结构图上找到最优的联盟结构是不可行的。所以，在进行联盟结构图的 2.1输入值的大小搜索的时候设定一个限界。对于具有n个Agent的数据集，会产生2n-1 对联盟结构的子集N进行搜索，目的在于寻个非空的子集，生成2”-1个联盟，在进行运算时找搜索中的最优联盟结构，即局部最优联盟结需要输人2”-1个值。联盟结构生成算法的输入构，记值和Agent的个数之间呈指数关系。理论上，在进行输入操作时即可排除一些不 CS=arg V(CS) 合理的联盟，或者在进行联盟结构生成的时候就同时，为了保证设定的联盟结构在最佳范围可以忽略一部分的输入。但是在接下来进行的操内，即存在一个有限的但是尽可能小的值k,k被作过程中无法保证存在单一的联盟与其他的联盟称为搜索的解的界限，也是衡量局部最优解进行合作之后的社会福利不是最佳社会福利，这 V(CSw)的标准。能够建立起界限的最小的k记为 V(CS) 是因为：被排除在外的联盟中可能存在比其他的 k=min),K≥vcS 联盟社会福利更大的联盟。通常，如果没有对联盟结构进行完全搜索，设 2.2联盟结构的数量定一个正确的界限是很难的。这是因为：在剪枝随着联盟结构不断发展，Agent数量的增多，的过程中虽然可以减少一些联盟结构的搜索，但新问题也随之产生。联盟结构的个数表示为是很难保证没有剪掉的比剪掉的具有更优性。在立2 进行社会福利的定义的时候，令任意一个联盟C: 的值v(C)≥0，并且一个联盟结构的社会福利其中：n代表数据集中的Agent个数；Zn,)表示具 V(CS)=∑v(C),这两点就保证了上述假设是不存有i个联盟组成的联盟结构的个数；Zm,)满足第 2类Striling数的特征，即在的，即在没有对联盟结构进行搜索的前提下设 Z(n,i)=iZ(n-1.)+Z(n-1,i-1) 置一个界限来缩小搜索联盟结构的数量。式中：Zm,)=Zm,1)=1;Zn-1,)表示在现有存在 3.1建立界限的联盟中增加一个新的Agent形成的联盟结构的本节主要讨论如何尽可能地减少对图的搜索个数；Zn-1,i-1)表示将一个新的Agent加入到的前提下，建立一个界限k。已有的联盟中，因为现在的联盟结构中只有定理1对于界限k,可以只搜索联盟结构图 i-1个联盟被计算。有以下基本结果m2: 的最低的两级（图1中第7、5层）。在这个搜命题1对于具有n个Agent的集合，具有索中，界限=n,需要搜索的联盟结构节点的数量 2-1个联盟，O(n)和w2)个联盟结构（即联盟结是2-1，这也是能够建立起界限的最小的搜索，即构的个数的阶介于？n之间)。 nm=2-l。并且，没有其他的算法对于联盟结构命题2寻找最优联盟结构是NP难问题。的搜索的数量会比2-1少。随着Agent数量的增加，联盟结构的数量也最底层具有1个联盟结构，第二最底层中具随之增加。经过实验的证明，当数据集中Agent 有2"-2个联盟(N中的所有子集，除掉全集和空个数超过15时，使用穷举法列举出所有联盟结构集)。在这一层中，每个联盟结构都有2个联盟，是不可行的。所以一共有2”-2)个联盟结构。只搜索最底下 3最坏情况有限界联盟结构生成两层，一共搜索1+2-2)=2个联盟结果。 Dean和Boddy在时间依赖规划((time depend- 3.2算法描述 ent planning)的基础上提出了Anytime算法，其本算法1最坏情况有保证联盟结构生成算法质是一种反复求解使得结果更加精确的算法。在 1)搜索联盟结构图的最底二层；算法的运行过程中，能够很快得到一个不精确的 2)从联盟结构图的顶层（第n层）开始，作宽解，然后进行若干次的重复过程，经过重复后逐度优先搜索，一直搜索到时间不允许为止或搜索步提高解的质量，Anytime算法一个最显著的优完整个联盟结构图；点就是能够很好地权衡计算时间和解的质量。 3)返回迄今为止所得到的最优的联盟结构。 Sandholm等Is使用Anytime算法开创性地提出了先前使用特征函数的方式2s2进行联盟结构种最坏情况有限界联盟结构生成。生成，算法1是一种任意时间算法，可以在任何时

2 联盟生成的复杂度 2.1 输入值的大小 2 n −1 2 n −1 2 n −1 对于具有 n 个 Agent 的数据集，会产生个非空的子集，生成个联盟，在进行运算时需要输入个值。联盟结构生成算法的输入值和 Agent 的个数之间呈指数关系。理论上，在进行输入操作时即可排除一些不合理的联盟，或者在进行联盟结构生成的时候就可以忽略一部分的输入。但是在接下来进行的操作过程中无法保证存在单一的联盟与其他的联盟进行合作之后的社会福利不是最佳社会福利，这是因为：被排除在外的联盟中可能存在比其他的联盟社会福利更大的联盟。 2.2 联盟结构的数量随着联盟结构不断发展，Agent 数量的增多，新问题也随之产生。联盟结构的个数表示为 ∑N i=1 Z(n,i) Z(n,i) Z(n,i) 其中：n 代表数据集中的 Agent 个数；表示具有 i 个联盟组成的联盟结构的个数；满足第 2 类 Striling 数的特征，即 Z(n,i) = iZ(n−1,i)+Z(n−1,i−1) Z(n,i) = Z(n,1) = 1 iZ(n−1,i) Z(n−1,i−1) 式中：；表示在现有存在的联盟中增加一个新的 Agent 形成的联盟结构的个数；表示将一个新的 Agent 加入到已有的联盟中，因为现在的联盟结构中只有 i－1 个联盟被计算。有以下基本结果[22-24] ： 2 n−1 O(n n ) ω(n n/2 ) n 2 命题 1 对于具有 n 个 Agent 的集合，具有个联盟，和个联盟结构 (即联盟结构的个数的阶介于 ~n 之间)。命题 2 寻找最优联盟结构是 NP 难问题。随着 Agent 数量的增加，联盟结构的数量也随之增加。经过实验的证明，当数据集中 Agent 个数超过 15 时，使用穷举法列举出所有联盟结构是不可行的。 3 最坏情况有限界联盟结构生成 Dean 和 Boddy 在时间依赖规划 (time dependent planning) 的基础上提出了 Anytime 算法，其本质是一种反复求解使得结果更加精确的算法。在算法的运行过程中，能够很快得到一个不精确的解，然后进行若干次的重复过程，经过重复后逐步提高解的质量，Anytime 算法一个最显著的优点就是能够很好地权衡计算时间和解的质量。 Sandholm 等 [15]使用 Anytime 算法开创性地提出了一种最坏情况有限界联盟结构生成。命题 1 表明，在联盟结构图上找到最优的联盟结构是不可行的。所以，在进行联盟结构图的搜索的时候设定一个限界。对联盟结构的子集 N 进行搜索，目的在于寻找搜索中的最优联盟结构，即局部最优联盟结构，记： CS ∗ N = argmax CS ∈N V(CS ) V(CS ∗ N ) 同时，为了保证设定的联盟结构在最佳范围内，即存在一个有限的但是尽可能小的值 k，k 被称为搜索的解的界限，也是衡量局部最优解的标准。能够建立起界限的最小的 k 记为 k = min{κ}, κ ⩾ V(CS ∗ ) V(CS ∗ N ) Ci v(Ci) ⩾ 0 V(CS ) = ∑k i=1 v(Ci) 通常，如果没有对联盟结构进行完全搜索，设定一个正确的界限是很难的。这是因为：在剪枝的过程中虽然可以减少一些联盟结构的搜索，但是很难保证没有剪掉的比剪掉的具有更优性。在进行社会福利的定义的时候，令任意一个联盟的值，并且一个联盟结构的社会福利，这两点就保证了上述假设是不存在的，即在没有对联盟结构进行搜索的前提下设置一个界限来缩小搜索联盟结构的数量。 3.1 建立界限本节主要讨论如何尽可能地减少对图的搜索的前提下，建立一个界限 k。 Π C 1 、Π C 2 2 n−1 nmin = 2 n−1 2 n−1 定理 1 对于界限 k，可以只搜索联盟结构图的最低的两级 (图 1 中第层)。在这个搜索中，界限 k=n，需要搜索的联盟结构节点的数量是，这也是能够建立起界限的最小的搜索，即。并且，没有其他的算法对于联盟结构的搜索的数量会比少。 2 n −2 1 2 (2n −2) 1+ 1 2 (2n −2) = 2 n−1 最底层具有 1 个联盟结构，第二最底层中具有个联盟 (N 中的所有子集，除掉全集和空集)。在这一层中，每个联盟结构都有 2 个联盟，所以一共有个联盟结构。只搜索最底下两层，一共搜索个联盟结果。 3.2 算法描述算法 1 最坏情况有保证联盟结构生成算法 1) 搜索联盟结构图的最底二层； 2) 从联盟结构图的顶层 (第 n 层) 开始，作宽度优先搜索，一直搜索到时间不允许为止或搜索完整个联盟结构图； 3) 返回迄今为止所得到的最优的联盟结构。先前使用特征函数的方式[25-26]进行联盟结构生成，算法 1 是一种任意时间算法，可以在任何时 ·416· 智能系统学报第 14 卷

第3期任子仪，等：约束条件下联盟生成研究进展 ·417· 间中断。如果将第1、2层搜索完成后，还存在剩的答案。将动态规划算法应用于最优化的问题，余时间，则可进一步地搜索缩小界限。般分为4个步骤来完成：定理2如果联盟结构图的第1、2层已经被 1)找出最优解的性质，并刻画其结构特征；搜索完成并且第1层以及以上的层也被搜索完成 2)递归定义的最优值：亿引当n=-nd且n三mad)时，k=[ 3)以自顶向下的方式计算出最优值；是紧的，否则k=月是紧的，其中归= n-l 4)根据计算最优值所得到的信息，构造最优解。 +2 2 将动态规划算法应用于联盟中的想法是在2-1个节点被搜索完之前，无法建立一个 Yeh在1986年首次提出的I;Rothkopf0及刘惊界限。当搜索到2-1+1个节点时，可以建立界限雷等B使用DP算法对求解最优联盟结构的算法 k=;搜索到2-l+1个节点的时候，界限变成进行了改进，主要解决存在大量重复子问题计算 k=”。通过更多实验验证：当界限k变成” 的问题；Rahwan等2提出了IDP(improved dynam- 时，搜索的层数就会增加2层。当搜索的层数每 itic programming))算法；张新良等在2007年提出增加2层，界限k前面的除数就会加1，若只多搜了一种快速动态生成(search of coalition structure, 索一层时，没有明显效果。 SCS)算法，主要降低搜索次数。本文中，DP算法总之，最坏情况有限界联盟结构生成算法中主要基于定理3。第2步具有很强的理性，即界限k能够迅速地下定理3任意给定一个联盟C∈N,V(CS)是降，同时该算法的收益递减，如图3所示。最优联盟结构的社会福利，即V(CS)=maxV(CS), 则 (C),IC=1 V(CS*)= maxv(C),ma(vC)+v(C"),其他 ●， (1) 使用定理3进行动态规划，先计算只有一个 Agent的联盟，接着迭代具有2个Agent的联盟，然后是具有3个Agent的联盟，一直迭代到具有 n个Agent的联盟。对于每个联盟C都需要使用式(1)计算。从式(1)中易知：当1C≠1时，需要 ×104 2.5 50 7.5 10.0 搜索节点数分别计算aC)+C和C)的值，然后将两个值进行比较，得到具有较大社会福利的联图3界限k作为10个Agent博奔中搜索的函数盟。在此过程中，将所产生的暂存结果保存在变 Fig.3 Ratio bound k as a function of search in a 10-Agents 量t(C)中。 game 通过上述操作，计算出来的最大(C)就是我界限k=n的建立与输入的Agct联盟的个们最终要求的V(CS)。计算CS的迭代过程具体数之间呈线性关系，这是因为输入2-1个数据，而操作如例2所示。当界限k=”时能够建立21个联盟结构，就是例2令数据集N={a,a2,a3,aal,假设特征函数为所说的第1、2层和第n层上面的节点。胡山立等22对算法1深入研究并进行改进， (a1)=30,v({a2)=40 v({a3)=25,v({a4)=45 给出了解决问题的一种任一时间联盟结构生成算 v{a1,a2})=50,v(《a1,a3)=60. 法和给定界限要求的联盟结构生成。Dang v{a1,aa)=80,v({a2,a3)=55 等提出不以层为单位最坏情况有限界的联盟结 v({a2,aa})=70,v({a3,aa})=80 构生成。 v({a1,a2,a3）=90,v({a1,a2,a4)=120 vla1,a3,a4l)=100,v({a2,a3,aul）=115 v({a1,a2,a3,a4)=140 4动态规划联盟生成求精确最优解表1表示算法的具体运算过程。由表1知，动态规划(dynamic programming,DP)算法和 tW=({a1,a2,{a3,au),能够将N分裂成{a1,2}和分治法类似，其基本思想是将待求解的问题分解 {a,aa},而t({as,a4)={a3,a},这是因为{a1,a2}分成若干个次级子问题，在求解的过程中，先求解裂成{a{a2}后的社会福利比较大，{a,aa}不需子问题，然后从子问题的解中得到要求解的问题要进行分裂。所以CS={a,{a2,{a3,aa}o