·418· 智能系统学报 第14卷 表14个Agent动态规划算法 Table 1 The dynamic programming algorithm for 4 Agents c 特征函数值 (C) v(C) a1) vta1)=30 la) 30 (a2) v(Ia2》=40 (a2) 40 as) v(Ia3)=25 {a3} 25 (a4) v({a4)=45 las) 45 a,az v({a1,a2)=50,f{a1)+fa2D=70 a1,{a2} 70 {a1,a3} ({a1,a3》=60,fa1)+fla3)=55 {a1,a3 60 {a1,a4} ({a1,a4l)=80,fa1》+fa4l)=75 a1,a4} 80 (2.a3) v{a2,a3)=55,f({a2})+f({a3)=65 (a2).(a3) 65 az,a4) v({a2,a4》=70,f{a2)+fla4l)=85 {a2,{a4} 85 {a3,a4} {a3,a4)=80,f({a3)+f({a4)=70 {a3,a4 80 v({a1,a2,a3l)=90,fIa1)+f({a2,a3)=95 f(Ia2)+fa1,a3》=100,fa3》+f{a1,a2)=95 {a1,a2,3} {a2,{a1,a3} 100 v({a1,a2,a4)=120,f({a1)+f({a2,a4)=115 f({a2)+f{a1,a4)=120,f(la4)+f{a1,a2)=115 {a1,a2,a4} {a1,a2,a4} 120 {a1,a3,a4l)=100,fa1l)+f1a3,a4)=110 {a1,a3,a4} fa3)+f(ta,a4D=105,fa4)+f{a1,a3》=105 {a1,{a3,a4l 110 {a2,a3,a4)=115,f{a2D+f{a3,a4l)=120 {a2,a3,a4l f(a3》+f({a2,a4》=110,f{a4)+f{a2,a3》=110 {a2l,{a3,a4} 120 va,a2,a3,a4)=140,fa4》+f{a1,a2,a3D=145 la1,d2,a3,a4} fla1,a2l)+fa3,a4》=150,fa3)+f({a1,a2,a4)=145 f(la1,a3D+fa2,a4D=145,fa2)+f(la1,a3,a4)=150 {a1,a2,{a3,a4} 150 f(ta1,a4l)+fla2,a3)=145,fa1》+f{a2,a3,a4l)=150 定理4给定一组Agent集，使用动态规划算 集合（见表2）。设G,G2,,G∈S。是所有的存 法求得最优联盟结构的时间复杂度O3")。 在的唯一配置的结合（即不存在具有相同联盟大 DP算法在该算法的运行过程中实际做了如 小的两个元素)，令F:SCs→2s是一个函数，按照 下几方面： 提前设定好的配置返回所有的联盟结构。N表示 1)评估图上的运动： 一个列表，里面的每一个元素表示一组具有相同 2)在表1中存储最优结构； 配置的联盟结构。形式上，N定义为：N= 3)从底部节点开始向上运动。 {F(G),F(G2,,F(Gsa》,N,N2,…,Ne∈N表示N 5联盟生成求近似最优解 中的每个元素（见表3）。 表24个Agent联盟列表 Rahwan等B将联盟配置与Anytime算法进行 Table 2 The coalition list of 4 Agents 结合提出一种联盟结构相似最优解算法；为Ab CLs 联盟列表值 izui等基于整数分区对联盟结构进行推广从而 CLI {a1,{a2h,{a3l,{a4} 对联盟配置(coalition configuration)进行了定义。 CL2 {a1,a3l,{a1,a4},{a2,a3},{a2,a4h,{a3,a4 5.1基本定义 CL3 在进行求解的过程中，设CL∈2”，其中 {a1,a2,a3,{a1,2,a4},{a1,a3,a4h,{a2,a3,a4} se{1,2,,k是联盟列表，CL是联盟列表CL,的 CL4 {a1,a2,a3,a4}O(3n ) 定理 4 给定一组 Agent 集，使用动态规划算 法求得最优联盟结构的时间复杂度 。 DP 算法在该算法的运行过程中实际做了如 下几方面： 1) 评估图上的运动； 2) 在表 t 中存储最优结构； 3) 从底部节点开始向上运动。 5 联盟生成求近似最优解 Rahwan 等 [34]将联盟配置与 Anytime 算法进行 结合提出一种联盟结构相似最优解算法；为 Alb￾izuri 等 [35]基于整数分区对联盟结构进行推广从而 对联盟配置 (coalition configuration) 进行了定义。 5.1 基本定义 CLs ∈ 2 n s ∈ {1,2,· · ·, k} CLi CLs 在进行求解的过程中，设 ，其中 是联盟列表， 是联盟列表 的 G1,G2,· · ·,Gςcs ∈ ςcs F : ςCS → 2 CS N N {F(G1),F(G2),· · ·,F(G|ςCS|)} N1,N2,· · ·,NςCS ∈ N N 集合 (见表 2)。设 是所有的存 在的唯一配置的结合 (即不存在具有相同联盟大 小的两个元素)，令 是一个函数，按照 提前设定好的配置返回所有的联盟结构。 表示 一个列表，里面的每一个元素表示一组具有相同 配置的联盟结构。形式上， 定义为： N = ， 表 示 中的每个元素 (见表 3)。 表 1 4 个 Agent 动态规划算法 Table 1 The dynamic programming algorithm for 4 Agents C 特征函数值 t(C) v(C) {a1} v({a1}) = 30 {a1} 30 {a2} v({a2}) = 40 {a2} 40 {a3} v({a3}) = 25 {a3} 25 {a4} v({a4}) = 45 {a4} 45 {a1,a2} v({a1,a2}) = 50, f({a1})+ f({a2}) = 70 {a1},{a2} 70 {a1,a3} v({a1,a3}) = 60, f({a1})+ f({a3}) = 55 {a1,a3} 60 {a1,a4} v({a1,a4}) = 80, f({a1})+ f({a4}) = 75 {a1,a4} 80 {a2,a3} v({a2,a3}) = 55, f({a2})+ f({a3}) = 65 {a2},{a3} 65 {a2,a4} v({a2,a4}) = 70, f({a2})+ f({a4}) = 85 {a2},{a4} 85 {a3,a4} v({a3,a4}) = 80, f({a3})+ f({a4}) = 70 {a3,a4} 80 {a1,a2,a3} v({a1,a2,a3}) = 90, f({a1})+ f({a2,a3}) = 95 f({a2})+ f({a1,a3}) = 100, f({a3})+ f({a1,a2}) = 95 {a2},{a1,a3} 100 {a1,a2,a4} v({a1,a2,a4}) = 120, f({a1})+ f({a2,a4}) = 115 f({a2})+ f({a1,a4}) = 120, f({a4})+ f({a1,a2}) = 115 {a1,a2,a4} 120 {a1,a3,a4} v({a1,a3,a4}) = 100, f({a1})+ f({a3,a4}) = 110 f({a3})+ f({a1,a4}) = 105, f({a4})+ f({a1,a3}) = 105 {a1},{a3,a4} 110 {a2,a3,a4} v({a2,a3,a4}) = 115, f({a2})+ f({a3,a4}) = 120 f({a3})+ f({a2,a4}) = 110, f({a4})+ f({a2,a3}) = 110 {a2},{a3,a4} 120 {a1,a2,a3,a4} v({a1,a2,a3,a4}) = 140, f({a4})+ f({a1,a2,a3}) = 145 f({a1,a2})+ f({a3,a4}) = 150, f({a3})+ f({a1,a2,a4}) = 145 f({a1,a3})+ f({a2,a4}) = 145, f({a2})+ f({a1,a3,a4}) = 150 f({a1,a4})+ f({a2,a3}) = 145, f({a1})+ f({a2,a3,a4}) = 150 {a1,a2},{a3,a4} 150 表 2 4 个 Agent 联盟列表 Table 2 The coalition list of 4 Agents CLs 联盟列表值 CL1 {a1},{a2},{a3},{a4} CL2 {a1,a3},{a1,a4},{a2,a3},{a2,a4},{a3,a4} CL3 {a1,a2,a3},{a1,a2,a4},{a1,a3,a4},{a2,a3,a4} CL4 {a1,a2,a3,a4} ·418· 智 能 系 统 学 报 第 14 卷