一.协同任务规划的功能与结构
 
多无人机协同任务规划即是根据一组特定条件的约束，以实现某个准则函数的最优或次优为目标，将某项作战任务分解成一些子任务并分配给多无人机系统中的各个无人机分别去完成的过程。 通常多无人机任务规划可以分成两大部分：上层的任务分配(Task Assignment or Task Allocation)和下层的路径规划(Path Planning)
 
任务分配考虑各种约束条件，以总体任务有效达成为目标，将具体目标和行动任务分配给各机，而各机根据分配的任务再进行具体的作战路径规划。
 
而路径规划的功能是在满足如最大线性速度、最大转角速度、操作的安全性、时间和环境变量等自身或外部限制的前提下在一系列位置之间设计或生成路径。同时，多无人机协同任务规划系统本身又是整个多无人机协同控制系统的重要组成部分。
 
二.任务分配
 
按照无人机作战任务之间的相关联性，可归类为
 1.独立任务分配
 2.协同任务分配
 按照无人机作战任务所处环境可分为
 1.静态任务分配
 2.动态任务分配
 按照分配方法可分为
 1.集中式任务分配
 2.分布式任务分配
 3.分层式分布任务分配
 
协同任务分配
 
多无人机协同任务分配的目标是在考虑各种诸如任务执行顺序、时间、无人机自身物理条件等约束条件的前提下，以总体任务效率最优或次优为目标，离线地或实时地将具体目标和行动任务分配给各机。
 
三.建模
 
以集中式控制系统为基础进行任务分配最常用的模型有
 多旅行商问题（multiple traveling salesman problem,MTSP）模型[13]、
 车辆路径问题(Vehicle Routing,VRP)模型[14]、
 多机路径分配模型(mVRP)[19]、
 混合整数线性规划问题(Mixed-Integer Linear Programming ,MILP,)模型[15]、
 动态网络流优化（Dynamic Network Flow Optimization ,DNFO)模型[16]、
 多处理器资源分配问题模型(Multiple Processsors Resources Allocation ,CMTMP)模型[17]
 除了上述模型外，美国空军研究实验室在无人机任务分配研究中建立了
 带时间窗的不同能力约束车辆路径问题(CVRPTW,Capacitated Vehicle Routing Problem with Time Windows）
 
四.方法
 
1. 集中式任务分配方法
 
集中式控制系统就是编队中的无人机之间的通信、信号的传输和控制均由唯一的一个控制中心来进行。
 常用的模型有MTSP、VRP、MILP、DNFO、CMTAP。
 
1.1最优化方法
 
(1)穷举法，适用于离散且规模小的情况
 (2)整数规划法(Mixed-Integer Linear Programming,MIP)根据既定的目的和目标，通过建立目标函数和约束条件的方法对规模较小的任务分配问题进行解决的一种最优化方法矩阵作业法、单纯型法、匈牙利法、分支定界法等是比较常用的整数规划方法。
 (3)约束规划(Constaint Programming CP)方法由变量集和约束集两者组成，变量集内的所有变量都有自己对应的值域，且变量的取值也只能从其值域中选取，它是求解组合优化问题的一种通用方法。
 (4)图论方法是通过图示的方法把任务和接受任务的成员特征表述出来，同时在任务和系统成员之间用图论方法建立匹配，以此设计出合理可行的任务分配方案。网络流模型和偶图匹配模型是两种经典的图论任务分配模型。
 
1.2启发式算法
 
在能够接受的时间范围内求得局部最优解或满意解。
 (1)列表规划（List Scheduling，LS）方法的步骤是首先建立任务的优先权函数，求得任务的处理次序，然后按照求得的任务处理次序将任务分派给系统成员。最常见的列表规划方法有动态列表规划（Dynamic List Scheduling ，DLS）法、多维动态列表规划（Multi-Dimensional Dynamic List Scheduling,MDLS）方法、多优先级动态列表规划（Multi-Priority List Dynamic Scheduling ,MPLDS）等。
 (2)智能优化算法
 ①进化算法EA 遗传算法GA 遗传规划Genetic Programming-GP 进化规划Evolutionary Programming-GP等
 ②群智能算法 PSO ACO
 ③人工免疫、禁忌搜索、模拟退火。
 
2.分布式任务分配
 
分布式控制系统与集中式控制系统不同的是实现信号传输的方式，前者无人机还可以在编队内进行通信，具有更好的灵活性。分布式控制系统结构相比集中式控制系统结构来说对无人机的要求更高，需要无人机具备独立计算、分析与决策等能力。
 
2.1合同网方法
 
目前，合同网（ContractNet）是应用范围最广的一种分布式任务分配方法，它的核心是为防止产生冲突，对每个问题的求解用通信的方式协商处理。[25]
 合同网方法有发布者和竞标者两个角色，由“招标- 投标- 中标- 确认”4 个交互阶段组成。在合同网协作方法中，系统成员的角色不用提前规定，任何系统成员可以是管理者，也可以是工作者，区别只在于成员是发布任务通知还是应答任务通知，于是任务能够被层次地分解分派。这种方法的缺点是通信量大、作为发布者的系统成员工作强度大且任务分解分配没有有效融合等。
 
2.2 拍卖方法
 
拍卖方法是实现资源配置的一种市场机制，指的是买方在清楚了解拍卖规则的前提下，采用竞价的方式决定特定物品的价格，也就是将要拍卖的物品用公开竞价的方式转卖给应价最高（ 最低）者的一种交易方式。一个拍卖主要由参与方、拍卖品、收益函数和应价策略4 个要素组成，在无人机任务分配问题中，无人机需要执行的任务可视为拍卖品，无人机的任务分配方和任务接受方共同组成参与者，且双方都有各自对应的收益函数和出价策略。拍卖方法是一种协商协议，因其规则明确且便于操作，近年来受到越来越多学者们的关注。拍卖方法用明确的规则引导买卖双方进行交互，可操作性非常强，能在较短时间内将资源合理分配，得到问题的最优解或较优解。该方法现已广泛运用在无人机作战和传感器等资源分配问题中。
 
综述
 
文献[1] 将任务分配方法归纳为集中式任务分配、分布式任务分配、分层次分布式任务分配三类，并对方法进行了简单阐述，提出了几个任务分配的可能的未来发展趋势。
 
文献［6］归纳和总结了多无人机协同任务规划的国内外研究现状，重点总结了任务分配方法的常见模型和算法，对各种算法的优缺点进行了讨论，得出多智能体的市场机制类算法在空战中将有广泛的应用价值。
 
模型
 
文献［5］探索了对不同种类的目标进行侦察、打击和评估任务时异构无人机的协同任务分配问题。对于侦察与评估任务中所得到的信息量，运用信息论中熵的变化量对其进行度量，把无人机对不同类型目标的打击能力简化为对目标的毁伤概率，同时把每个任务之间的关联性考虑在内，建立了异构多无人机协同任务分配模型。
 
文献［7］建立了以合同网协议和多智能体系统理论为基础的有人机／ 无人机编队MAS(Multi-agent System MAS)结构和基于投标过程的无人机任务分配模型。
 
文献[23]提出了集群组网任务分配模型和任务分配求解算法。分析了集群组网的任务分配问题，并剖析了任务分配分层递阶结构；借助层次分析思路，建立了集群组网任务分配模型；结合群体智能优化算法的优势，提出了基于PSO-ICWPA 的集群组网任务分配算法；
 
同构
 
文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。
 
1.蚁群
 
文献［8］在无人机协同多任务分配的研究中，运用了基于分工机制的蚁群算法进行求解，并给出了基于作战任务能力评估的问题解构造策略和基于作战任务代价的状态转移规则，大幅度提升了算法的性能。
 
2.粒子群
 
文献［11］设计出一种多无人机任务分配与航迹规划相结合的整体控制架构，假设威胁和障碍区域为合理的多边形模型，使用改进的算法求出两个航迹点之间的最短路径，将此路径当成任务分配过程全局目标函数的输入，然后用粒子群优化任务分配迭代寻优。
 
文献［10］在基于任务依赖关系和ISO–DATA（Iterative Self-organizing Data Analysis Technique）算法相结合的基础上设计了新的任务分组方法，在保持无人机负载均衡的基础上，给出了基于资源福利的任务组级组粗粒度的无人机任务分配方法，在任务组内提出了结合粒子群算法的细粒度任务分配算法。
 
文献[21]通过综合考虑多无人机任务分配约束条件，以多UCAV 总飞行航程和多UCAV 总飞行时间两个关
 键指标作为任务分配方案的评价标准，构建多无人机任务分配模型，采用改进的QPSO 算法进行优化求解多无人机任务分配问题。
 
文献[22]，综合考虑了协同多任务分配问题的任务优先级和任务协同约束、任务时间约束，同时针对无人机载弹量有限的实际情况，将无人机的载弹量约束等同于无人机执行攻击任务的最大次数限制，建立了协同多任务分配模型，在算法引入自组织惯性权重和加速系数，增强了算法的全局和局部搜索能力，优于遗传算法的协同多任务分配。
 
GA
 
文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 用整数规划法MIP和遗传算法求解。但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。
 
文献[24]针对战场环境的多目标、多任务以及无人机能力有限等特点，设计了一种适应于多目标、多无人机、多任务种类的无人机群协同多任务分配模型。结合该模型以及其中的任务偏序约束、协同任务约束、无人机能力约束等约束条件提出了基于任务序列的遗传算法染色体编码方法，和基于同类任务的遗传算法交叉、变异算子。该方法利用遗传算法的全局搜索优化解特点，对无人机群的协同任务分配进行优化.
 
动态及不确定环境下
 
文献[12]分析了实际战场上信息的不确定性，同时指出了在此条件下多无人机面临的任务分配问题。将收益毁伤代价指标、目标价值及航程代价指标的不确定信息作为参考依据，在此基础上建立了基于区间
 信息环境下多无人机的任务分配模型，采用随机概率的多属性方案排序（Stochastic Multi-criteria Acceptability Analysis,SMAA）方法，得出不确定环境下多无人机动态任务分配求解方法。
 
文献[3]建立了多UCAV任务分配模型，对动态重分配策略进行研究并做出改进，将周期性重调度和事件驱动重调度进行有机结合。提出了一种改进的混合重调度策略．增加了对突发事件的处理能力，并结合粒子群算法和细菌觅食算法的优缺点。提出了混合细菌觅食算法(PBFO)解决多UCAV的动态任务分配问题。
 
异构
 
文献［9］以异构类型多目标多无人机任务分配问题为原型，设计了一种基于时间窗的多无人机联盟组任务分配方法，此算法使用冲突消解机制来防止无人机实时任务分配过程中出现多机资源死锁，其次通过无人机两阶段任务联盟构成算法，组成了任务联盟，使无人机任务分配的有效性和实时性有了很大的提高。
 文献[18]以多异构无人机执行SEAD任务为背景采用图论的方法完成问题的建模,将无人机本体等效为Dubins Car模型,并对其在相应目标处执行侦查、打击、评估任务时的进入角度进行约束,通过Dubins路径完成对无人机飞行路径的等效,采用分布式遗传算法完成对问题的快速求解.
 
文献[4]基于文献[20]的研究成果,将模型适用范围扩展到了异构UAV,但对约束条件的假设仍然相对理想.
 
引用文献
任务空间特性
建模方法
约束条件
算法求解架构
[3]
同类UAV

文献
 
[1]陈侠,乔艳芝.无人机任务分配综述[J].沈阳航空航天大学学报,2016,33(6):1-7. DOI:10.3969/j.issn.2095-1248.2016.06.001.
 [2]李炜,张伟. 基于粒子群算法的多无人机任务分配方法[J].控制与决策，2010,25(9):1359 -1364.
 [3]杨尚君,王社伟,陶军, 等.动态环境下的多UCAV协同任务分配研究[J].电光与控制,2012,19(7):32-36,79. DOI:10.3969/j.issn.1671-637X.2012.07.008.
 [4]Wang J, Zhang Y F, Geng L, et al. A heuristicmission planning algorithm for heterogeneous tasks with
 heterogeneous UAVs[J]. Unmanned Systems, 2015, 3(3):205-219.
 [5]邸斌,周锐,丁全心. 多无人机分布式协同异构任务分配[J].控制与决策,2013,28(2):274 -278.
 [6]朱毅,张涛,程农,等.多UAV协同任务规划研究[J]. 系统仿真学报,2009(20):194 -199.
 [7]刘跃峰,张安.有人机/无人机编队协同任务分配方法[J]. 系统工程与电子技术,2010，32(3):584-588.
 [8]苏菲,，陈岩,沈林成.基于蚁群算法的无人机协同多任务分配[J]. 航空学报,2008(29):184-191.
 [9]林林,孙其博,王尚广,等.基于时间窗的多无人机联盟任务分配方法研究[J].电子与信息学报,2013,35(8):1983-1988.
 [10]谭何顺,曹雷,彭辉,等. 一种多无人机层次化任务分配方法[J]. 解放军理工大学学报(自然科学版),2014,15(1):18 -24.
 [11]孙小雷,齐乃明,董程,等. 无人机任务分配与航迹规划协同控制方法[J]. 火力与指挥控制,2015,37(12):2772 -2776.
 [12]陈侠,唐婷.不确定环境下多无人机动态任务分配方法.火力与指挥控制[J].2013,38(1):45 -49.
 [13]SECREST. Traveling salesman problem for surveillance mission using particel swarm optimization [Ｄ]. wright-PattersonAFB:Air Force Institute of Technologhy,2003.
 [14]O’Rourke K P,Bailey T G,Hill R,et al. Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search[J].Military Operations Research Journal, 2001(6):5 -30.
 [15]ALIGHANBARI M.Task assignment algorithms for teams of UAVs in dynamic environments[D].Cambridge:Massachusetts Institute of Technology,2004.
 [16]NYGARD K E,CHANDLER P R,PACHTER M.Dynamic network flow optimization modles for air vehicle resourceallocation[C]//Proceedingsofthe 2001 American Control Conference,2001,3:1853-1858.
 [17] ALVARO E G .Stability Analysis of Network-based Cooperative Resource Allocation Strategies[D].Columbus:Ohio State University,2003.
 [18]吴蔚楠,关英姿,郭继峰, 等.基于SEAD任务特性约束的协同任务分配方法[J].控制与策,2017,32(9):1574-1582. DOI:10.13195/j.kzyjc.2016.0858.
 [19] Arsie A, Savla K, Frazzoli E. Efficient routing algorithmsfor multiple vehicles with no explicit communications[J].IEEE Trans on Automatic Control, 2009, 54(10):2302-2317.
 [20]Geng L, Zhang Y F, Wang J, et al. Cooperative missionplanning with multipleUAVs in realistic environments[J].Unmanned Systems, 2014, 2(1): 73-86.
 [21]邓可,连振江,周德云, 等.基于改进量子粒子群算法的多无人机任务分配[J].指挥控制与仿真,2018,40(5):32-36. DOI:10.3969/j.issn.1673-3819.2018.05.007.
 [22]梁国强,康宇航,邢志川, 等.基于离散粒子群优化的无人机协同多任务分配[J].计算机仿真,2018,35(2):22-28. DOI:10.3969/j.issn.1006-9348.2018.02.005.
 [23]汪汝根,李为民,刘永兰,刘金松.无人机集群组网任务分配方法研究[J].系统仿真学报,2018,30(12):4794-4801+4807.
 [24]姚敏,王绪芝,赵敏.无人机群协同作战任务分配方法研究[J].电子科技大学学报,2013,(5):723-727. DOI:10.3969/j.issn.1001-0548.2013.05.015.
 [25]SM ITH R G.The Contractnet Protocol :High level Communication and Control in a Distributed problem solver [J]. IEEE Transaction and Computers

团队管理-任务分配
 
任务分配是团队管理中很重要的工作，做好任务分配才能让队员和自己都工作的更高效
 
最近读《李元芳升职记》，看到任务分配部分的内容，结合最近工作中出现的问题，感觉到任务分配能力的重要性。
 中国领导者沟通容易存在问题是经常 “不要让我再说第二遍” “我说过多少遍了？” 这应该是管理沟通中存在的最大的问题。当管理者给团队成员分配任务时，不可以这样。同时，当我们把任务分配给队员，而队员没有按时保质保量完成时，我们也不能将所有责任加之于队员，而是管理人员也同样需要 因人排工。
 按照李元芳升职记书中描述的，分配任务分为以下六部。
 第一步：了解下属的性格和能力：清楚了解每一位下属的性格特点和所具备的能力，根据他们的性格特点和能力素质“因人派事”。
 第二步：与队员明确工作内容，意义，工作时限和合格标准：和队员详细沟通被分派的工作为什么要做，做什么，需要多长时间完成及做到什么程度才算完成。判断下属是否清楚这些信息的唯一标准就是让他们复述，看他们所复述的意思与我们所表达的意思是否一致。
 第三步：明确队员的权利范围和责任：让队员明确，要他们完成这些工作时，他们可以动用的资源，权利及必须承担的责任是什么。
 第四步：确认下属具有完成工作所需要的能力：确认下属具有完成被分派的工作所需要的能力，如果能力不够，一定要及时给与培训和辅导，并且在有其他可选情况下，不可以将该任务分派给不具备能力的员工，否则，后果严重。
 第五步 定期检查和监督下属的工作：通过检查监督，了解工作进展和质量，已经存在的问题，以便有机会及时改进。
 第六步 及时给出评价和奖惩：按事先确定的时间和标准及时给予评价，奖励和惩罚。
 
1.因人派事 是让每个人尽量干最适合他的工作；
 2.沟通工作内容工作意义完成时限及合格标准时，一定要让队员复述，不要简单的提“你清楚了吗”这样封闭式的问题。
 3.让员工明确责权利，避免发授权和过多请示；
 4.不要只给任务不给培养；
 5.千万不可放羊。计划执行监督收尾。监督监督监督。 具体的监督是 了解进度状态，代码审查CodeReview.不做代码审查，所有偷的懒都将N倍返还。
 6.信守承诺。
 
在工作的开展过程中，我们不能抱怨队员素质不高能力不够执行力不到位，公司大环境不够好，需求任务紧等问题，很多时候是管理者在分配任务时的一个或几个方面的问题造成的。一定要在分配任务上做好，否则，问题会层出不穷。

在实际应用中有这样一个场景：有m台服务器，有n个任务，需要把这n个任务按一定策略分配给m台服务器来执行，请按以下要求实现该场景：
 1、使用List列表代表服务器（列表中每个元素为一个IP地址）；
 2、使用List列表代表任务（列表中每个元素为任务ID）；
 3、分配的过程就是把IP地址与任务ID映射上的过程；
 4、策略要支持多个，如按IP地址随机、按任务数量平分等，策略需要支持可扩展（扩展时不用修改已经实现好的策略）；
 
1、实体类定义：
 
//服务器实体类
public class Service {
	private String IP;
	private String serviceName;

}

//任务实体类
public class Task {
	private Integer taskId;
	private String taskName;
}
 
2、抽象父类定义（所有的策略实现都需要继承该类）
 
public abstract class AbstractTaskAllocation {

	/**
	 * 具体的整个过程 在这里定义操作实现的步骤
	 */
	protected void doTaskAllocation(List<Service> serverList, List<Task> taskList) {
		// 1、准备阶段，可以进行一些数据初始化的操作
		this.preparation(serverList, taskList);
		// 2、把IP地址与任务ID映射上阶段
		Map<Object, String> serviceTaskMapping = this.setMapping(serverList, taskList);
		// 3、结果返回阶段
		this.getResult(serviceTaskMapping);
	}

	/**
	 * 1、准备阶段
	 */
	public abstract void preparation(List<Service> serverList, List<Task> taskList);

	/**
	 * 2、把IP地址与任务ID映射上阶段
	 * 
	 * @param taskList
	 * @param serverList
	 */
	public abstract Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList);

	/**
	 * 3、结果返回阶段，分配完后续处理
	 */
	public void getResult(Map<Object, String> serviceTaskMapping){
		// 分配状态查询
		for (Entry<Object, String> entrySet : serviceTaskMapping.entrySet()) {
			System.out.println("服务器IP: " + entrySet.getValue() + " === 任务ID: " + entrySet.getKey());
		}
	}
}
 
3、平均分配策略：
 
public class AverageTaskAllocation extends AbstractTaskAllocation {

	// 进行一些参数校验之类的
	@Override
	public void preparation(List<Service> serverList, List<Task> taskList) {
		if (serverList == null || serverList.size() < 1) {
			System.out.println("没有可用的服务器！");
		}
		if (taskList == null || taskList.size() < 1) {
			System.out.println("暂无需要处理的任务！");
		}
	}

	// 设置服务器和任务之间的隐射关系
	@Override
	public Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList) {
		// map key_value 的形式存储服务器和任务的映射关系 id : ip
		//Map<Object, String> serviceTaskMapping = new HashMap<Object, String>();
		Map<Object, String> serviceTaskMapping = new TreeMap<>();
		// 任务平均分配 参考HashMap 的分配原理
		int serverCount = serverList.size();

		for (int i = 0; i < taskList.size(); i++) {
			int taskAddress = i % serverCount;
			serviceTaskMapping.put(taskList.get(i).getTaskId(), serverList.get(taskAddress).getIP());
			//serviceTaskMapping.put(taskList.get(i).getTaskName(), serverList.get(taskAddress).getServiceName());
		}

		return serviceTaskMapping;
	}

	/*@Override
	public void getResult(Map<Object, String> serviceTaskMapping) {
		// 分配状态查询
		for (Entry<Object, String> entrySet : serviceTaskMapping.entrySet()) {
			System.out.println("服务器IP: " + entrySet.getValue() + " === 任务ID: " + entrySet.getKey());
		}
	}*/
}
 
4、随机分配策略：
 
public class RandomTaskAllocation extends AbstractTaskAllocation {

	// 进行一些参数校验之类的
	@Override
	public void preparation(List<Service> serverList, List<Task> taskList) {
		if (serverList == null || serverList.size() < 1) {
			System.out.println("没有可用的服务器！");
		}
		if (taskList == null || taskList.size() < 1) {
			System.out.println("暂无需要处理的任务！");
		}
	}

	// 设置服务器和任务之间的隐射关系
	@Override
	public Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList) {

		// map key_value 的形式存储服务器和任务的映射关系 id : ip
		Map<Object, String> serviceTaskMapping = new HashMap<Object, String>();
		// 设置的是随机事件 0或者1 各50%，保证随机分配性
		// 服务器的数量，就是任务分配的概率
		int serverCount = serverList.size();
		Random r = new Random();
		for (int i = 0; i < taskList.size(); i++) {
			Integer serverId = r.nextInt(serverCount);
			serviceTaskMapping.put(taskList.get(i).getTaskId(), serverList.get(serverId).getIP());
		}

		return serviceTaskMapping;
	}
	@Override
	public void getResult(Map<Object, String> serviceTaskMapping) {
		// 可以覆盖父类，进行一些子类特殊操作
	}
}
 
5、测试类：
 
public class TaskAllocationTest {

	public static void main(String[] args) {
		List<Service> serverList = new ArrayList<>();
		List<Task> taskList = new ArrayList<>();

		// 添加服务器
		for (int i = 1; i < 11; i++) {
			Service service = new Service();
			service.setIP("10.1.10.3" + i);
			service.setServiceName("我是第"+i+"台服务器");
			serverList.add(service);
		}
		// 添加任务
		for (int i = 0; i < 500; i++) {
			Task task = new Task();
			task.setTaskId(i + 1);
			task.setTaskName("我是第"+i+"个任务");
			taskList.add(task);
		}

		// 随机分配策略：
		AbstractTaskAllocation randomTaskAllocation = new RandomTaskAllocation();
		randomTaskAllocation.doTaskAllocation(serverList, taskList);

		// 平均分配任务策略
		AbstractTaskAllocation averageTaskAllocation = new AverageTaskAllocation();
		averageTaskAllocation.doTaskAllocation(serverList, taskList);

	}
}
 
6、模板模式要点（不熟悉可以去看设计模式那节）
 
模版方法定义了算法的步骤，把这些步骤的实现延迟到了子类。
模版方法模式为我们提供了一种代码复用的重要技巧。
模版方法的抽象类可以定义具体方法、抽象方法和钩子。
抽象方法由子类实现。
为了防止子类改变模版方法中的算法，可以将模版方法声明为final
模版方法和策略模式都封装了算法，一个用组合（策略模式），一个用继承（模版方法）。
 
 
每天努力一点，每天都在进步。

2.5.1题目描述
 
分配问题要求将n个任务分配给n给人，每个人完成任务的代价不同，要求分配的结果最优，此题可以使用回溯求解。
 
2.5.2程序使用说明
 
Java环境1.8.0_111
 
IDE:eclipse
 
需要两个文件Node.java，Assignment.java直接编译两个文件，然后直接运行Assignment.java文件，在控制台查看结果。
 
2.5.3简要分析和设计
 
假设存在四个人a,b,c,d，任务1，任务2，任务3，任务4，和对应的代价矩阵如下
 
 
 

 
 
图二  矩阵（来源于算法设计与分析基础第三版）
 
采用分支界限法，需要计算最优边界Lb，Lb=已分配任务的代价+剩余未分配任务中最小的代价，然后构造状态空间树，上面例子的状态空间树如下：
 
 
 
图三  空间树（来源于算法设计与分析基础第三版）
 
开始节点表示还未给任何人分配任务，然后在开始节点的基础上寻找可扩展节点，由于此时a有四种选择，则有四个扩展节点，然后分别计算可扩展节点的lb，如果lb小于cost,则将其加入优先队列，然后从优先队列中选择一个最优的，作为新的扩展节点，然后在当前节点的基础上为继续进行上述步骤，当有一个节点的状态表示为已将四个节点分配完成，且花费的代价小于已有cost，则更新cost值，然后继续从优先队列里增加值和取值，直到优先队列为空，则最小花费即为最优选择。
 
2.5.4测试用例
 
  {{9, 2, 7, 8},
 
{6, 4, 3, 7},
 
{5, 8, 1, 8},
 
{7, 6, 9, 4}}
 
结果：
 
人员以此选择工作为：2 1 3 4
 
最小花费：13
 
 
 
2.5.5源代码
 
目录结构：
 
 
 
package three.one;
 
import java.util.ArrayList;
 
import java.util.Comparator;
 
import java.util.PriorityQueue;
 
/**
 
 * 
 
 * @author ym
 
 *
 
 */
 
public class Assignment {
 
//对应花费
 
private int[][] cost={
 
        {9, 2, 7, 8},
 
        {6, 4, 3, 7},
 
        {5, 8, 1, 8},
 
        {7, 6, 9, 4}
 
    };
 
 
//构造比较函数
 
Comparator<Node>  comparator = new Comparator<Node>() {
 
public int compare(Node o1, Node o2) {
 
return o1.getLb()-o2.getLb();
 
};
 
};
 
 
//存储优先队列
 
PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(comparator);
 
//记录当前最优解
 
int results = 0;
 
//存储节点
 
Node resultNode=null;
 
 
public Node initRootNode(){
 
Node root = new Node();
 
int lb=0;
 
for(int i=0;i<cost.length;i++){
 
int min=cost[i][0];
 
for(int j=1;j<cost[0].length;j++){
 
if(min>cost[i][j]){
 
min=cost[i][j];
 
}
 
}
 
lb+=min;
 
}
 
root.setLb(lb);//设置lb
 
return root;
 
}
 
 
/**
 
 * 计算一个初始值上界
 
 * @return
 
 */
 
public int  mostBound(){
 
int bound=0;
 
 
for(int i=0;i<cost.length;i++){
 
int max=cost[i][0];
 
for(int j=1;j<cost[i].length;j++){
 
if(max<cost[i][j]){
 
max=cost[i][j];
 
}
 
}
 
bound+=max;
 
}
 
 
return bound;
 
}
 
 
//设置结果
 
public void setResults(int results) {
 
this.results = results;
 
}
 
 
 
/**
 
 * 计算lb
 
 * @param node
 
 * @return
 
 */
 
public void calculateLb(Node node){
 
int lb=0;
 
ArrayList<Integer> upperNode =node.getUpperNode();
 
int size=upperNode.size();
 
for(int i=0;i<size;i++){//计算已选person的界
 
lb+=cost[i][upperNode.get(i)];
 
}
 
 
for(int i=size;i<cost.length;i++){//计算剩余person的最小界
 
int min=cost[i][0];
 
for(int j=1;j<cost[i].length;j++){
 
if(min>cost[i][j]){
 
min=cost[i][j];
 
}
 
}
 
lb+=min;
 
}
 
 
node.setLb(lb);//更新节点lb
 
}
 
 
/**
 
 * 计算孩子节点
 
 * @param node
 
 * @return
 
 */
 
public ArrayList<Node> getChildNodes(Node node){
 
ArrayList<Node> childNodes = new ArrayList<Node>();//孩子节点
 
int i=node.getPerson()+1;
 
int order=0;
 
ArrayList<Integer> upperNode = node.getUpperNode();//获取已经选择的job
 
for(int j=0;j<cost[i].length;j++){
 
if(upperNode==null||order>=upperNode.size()){
 
Node temp =getNode( i,j,upperNode);//设置节点
 
childNodes.add(temp);
 
}
 
else{
 
if(order<upperNode.size()&&!upperNode.contains(j)){//构造子节点
 
Node temp =getNode(i,j,upperNode);//设置节点
 
childNodes.add(temp);
 
}
 
else
 
order++;
 
}
 
}
 
return childNodes;
 
}
 
 
/**
 
 * 
 
 * 
 
 * @param i
 
 * @param j
 
 * @param list
 
 * @return
 
 */
 
public Node getNode(int i,int j,ArrayList<Integer> list){
 
ArrayList<Integer> uppers=new ArrayList<Integer>();
 
if(list!=null&&list.size()>0){
 
uppers.addAll(list);
 
}
 
uppers.add(j);
 
Node temp = new Node(uppers);
 
temp.setPerson(i);
 
temp.setJob(j);
 
calculateLb(temp);
 
return temp;
 
}
 
 
 
/**
 
 * 
 
 * @param node
 
 */
 
public void assiginment(Node node){
 
setResults(mostBound());//计算最大界
 
priorityQueue.add(node);
 
while(!priorityQueue.isEmpty()){
 
Node currentNode = priorityQueue.poll();
 
if(currentNode.getPerson()<cost.length-1){
 
ArrayList<Node> childNodes = getChildNodes(currentNode);
 
for(Node child:childNodes){
 
if(child.getLb()<results){
 
priorityQueue.add(child);
 
}
 
}
 
}
 
else{
 
if(currentNode.getLb()<results){
 
results=currentNode.getLb();
 
resultNode=currentNode;
 
}
 
}
 
 
}
 
}
 
 
 
public int getResults() {
 
return results;
 
}
 
 
 
public Node getResultNode() {
 
return resultNode;
 
}
 
public static void main(String[] args){
 
Assignment at = new Assignment();
 
Node root=at.initRootNode();
 
at.assiginment(root);
 
ArrayList<Integer> list = at.getResultNode().getUpperNode();
 
System.out.println("人员以此选择工作为：");
 
for(int i=0;i<list.size();i++){
 
System.out.print(" "+(list.get(i)+1));
 
}
 
System.out.println();
 
System.out.println("最小花费：");
 
System.out.print(at.getResults());
 
}
 
 
}
 
 
 
package three.one;
 
 
 
import java.util.ArrayList;
 
 
 
/**
 
 * Node类
 
 * @author ym
 
 *
 
 */
 
public class Node{
 
int person=-1;
 
int job=-1;
 
int weight=0;
 
int lb=0;
 
ArrayList<Integer> upperNode;
 
 
public Node(){
 
 
}
 
 
public Node(ArrayList<Integer> upperNode){
 
this.upperNode=upperNode;
 
}
 
 
public int getPerson() {
 
return person;
 
}
 
 
 
public void setPerson(int person) {
 
this.person = person;
 
}
 
 
 
public int getJob() {
 
return job;
 
}
 
 
 
public void setJob(int job) {
 
this.job = job;
 
}
 
 
 
public int getWeight() {
 
return weight;
 
}
 
 
 
public void setWeight(int weight) {
 
this.weight = weight;
 
}
 
 
 
public int getLb() {
 
return lb;
 
}
 
 
 
public void setLb(int lb) {
 
this.lb = lb;
 
}
 
 
 
public ArrayList<Integer> getUpperNode() {
 
return upperNode;
 
}
 
 
 
public void setUpperNode(ArrayList<Integer> upperNode) {
 
this.upperNode = upperNode;
 
}
 
}