Drools planner探险（一）
记得两年前，因为项目需要第一次接触Drools，优秀的文档，强大的机能记忆犹新。之后一直留意Drools的发展。?
这两天项目间隙，突然兴起，研究了一下Drools planner（以下简称planner） ，发现这也是一个非常实用的用于规划的开发框架。以前怎么没注意这位小兄弟？ 以前看的多写的少，今天也将心得分享一下。?
（一）预备知识?
1)? TSP(旅行者问题)
? 这是一个运筹学经常提及的课题，内容是这样的:旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
? 咋一看，这很简单嘛，只要n确定了，城市间的距离也知道了，遍历所有的组合就行了。但是当n很大时，该组合会出现指数型增长，计算量会变得非常大，对于有限的时间和空间来说，可以认为不可计算。
? 这种问题在数学上就叫做 NP-complete(NPC)问题。
? 注：关于P/NP/NPC/NPH等概念，网上有解释很多，感兴趣的朋友可查下维基，这里不占用篇幅。
2)关于启发式算法
? 要解决上述问题，常规的确定性算法（如：暴力求解）就行不通了，这时需要用? 不确定性算法 才能解决。
? 显然，planner的设计者都是这方面的行家，planner中使用了大量算法，其中重要的一类是启发算法（heuristic algorithm）。
? 启发式算法的发展： （以下内容转自 csdn aris_zzy的博客）
? 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。
? 40年代：由于实际需要，提出了启发式算法（快速有效）。
? 50年代：逐步繁荣，其中 贪婪算法和局部搜索 等到人们的关注。
? 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。
? 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。
????????? 由此必须引入新的搜索机制和策略………..
????????? Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。
? 80年代以后：
????????? 模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。
? 最近比较热或刚热过去的：
? 演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等。
? 好了就到这儿吧，言归正传。
（二）什么是 Drools planner？
? planner是一个轻量级，可嵌入规划引擎，优化规划问题的框架。
? 它适用于解决以下问题：
???? 员工轮班：排班护士，修理工，…
???? 议程安排：安排会议，约会，维修工作，广告，…
???? 教学时间表：排课，课程，考试，会议介绍，…
???? 车辆路径：规划车辆（卡车，火车，船只，飞机，……）运费和(或)人
???? 装箱问题：灌装容器，卡车，船只和储存仓库，以及云计算机节点，…
???? 作业车间调度：策划汽车装配线规划，机器的队列，劳动力的任务规划，…
???? 下料问题：同时最大限度地减少浪费：剪纸，钢，地毯，…
???? 运动计划：计划的足球联赛，棒球联盟，…
???? 金融投资组合优化：优化，风险分散，…
???? 。。。
? （只要涉及规划计划之类的通吃啊）?
?
?
注：（本文使用最新版：5.4.0Final）? ○ 算法已实现??? × 算法未实现
由上表可见，planner还处于成长期，一些复杂算法还有待实现。
下面给出一些已实现算法的介绍：
Brute force(强力算法):?
??? 暴力的人生无需解释。。。
First Fit（首次适应算法）：?
??? 从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
?
First Fit Decreasing（首次适应降序算法）：?
??? 顾名思义，在First Fit 基础上加入了排序，以提高匹配效率
?
Best Fit（最佳适应算法）：?
??? 从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
?
Best Fit Decreasing（最佳适应降序算法）：?
??? 同样为Best Fit 的改良版
?
Hill-climbing（爬山法）：?
??? 是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。 爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。
Tabu search（禁忌搜索算法）：?
??? 局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。?
??? 它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试 探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选 择，指导下一步的搜索方向，这就是Tabu表的建立。
看完这个很有压力，说实话我也是，谁让咱不是学数学专业呢。好在这些算法planner已经实现了，剩下的问题是如何选择的问题。 当然如何选择也不简单。
好了今天收工了，下回接着写开发流程。
?