很多的题目，如果我们可以建立数学模型，应该尽量用解析法来处理，因为简单的模型更清晰地反映了事物之间的关系。但是，并不是所有的题目都可以建立简单的数学模型。我们这时必须使用搜索的方法，也就是枚举所有可能情况来寻找可行解或最优解。于是我们需要利用很多技巧来提高效率：可行性剪枝，最优性剪枝，调整搜索顺序，等方法都很有用，在它们的帮助下，我们可以大大提高搜索的效率。引题：N个物品与N个位置，给定每个物品的可能放的位置集合，要求寻找一一对应的关系。但还给出物品位置之间的限制（例如：如果1放在3则2不能放在1）。求一组可行解，或给每一种对应关系一个权，求满足条件的最优解。简单分析：如果我们枚举每一个物品的位置，然后判断。这样的时间复杂度为O(N!)。好像似乎也只能这样。进一步分析：我们看一个例子，N=6：其它限制有4条(a,b,c,d)表示如果a放在b则c不能放在d1356225331413262我们发现，如果我们一旦确定了3和5的位置，其它4个物品的位置之间已经没有限制关系了，这样其它4个物品的位置可以通过匹配来解决。部分搜索+匹配：搜索一部分变量，使得余下的变量之间的关系简化，然后通过一些高效算法（匹配）完成余下问题。通过部分搜索为匹配算法提供条件（例如上面的例子创造二分图关系），而匹配算法代替搜索，高效地完成余下的任务。部分搜索+匹配的方法充分发挥了搜索和匹配算法的双重优势。搜索的优势在于应用性广，可以克服复杂的情况，匹配算法的优势在于效率高。两者相互促进，同时也弥补对方的不足。这也是这个方法的成功的关键。一个部分搜索+匹配算法的经典例子。题目简述(NOI2003二试第三题)B国的连环阵由M个武器组成。最初，1号武器处于攻击状态，其他武器都处在无敌自卫状态。以后，一旦第i（1i<M）号武器被消灭，1秒钟以后第i+1号武器就自动从无敌自卫状态变成攻击状态。A国有N个炸弹，每个炸弹的作用半径均为k，且会持续爆炸5分钟。在这5分钟内，瞬间消灭离它直线距离不超过k的、处在攻击状态的B国武器，不会炸毁本国炸弹。任务：决定一个序列a1、a2、a3…使得在第ax号炸弹引爆的时间内连环阵被摧毁。这里的x应当尽量小。输入：N,M及武器和炸弹的坐标。测试数据中的坐标是随机生成的。初步分析：A国炸弹I可以炸到B国武器J的条件：(u[I]-x[J])2+(v[I]-y[J])2<=R2进一步分析：每一颗炸弹必定炸掉B国武器中编号连续的一段。5分钟只是表明每一颗炸弹可以炸掉任意多个编号连续的B国武器。普通的搜索方法：每次寻找一个编号最小的没有被炸掉的B国武器，选择一颗没有使用过并能炸到此武器的A国炸弹，然后使用这颗炸弹炸掉B国武器连续的一段，继续深度优先搜索下一颗炸弹的编号，如果发现B国武器已经全部炸毁就可以回溯。搜索的时间复杂度为O(n!)。即使加上优化，程序效率也不是很高。部分搜索：此题使用部分搜索的算法需要一些转化：如果已经将B国武器根据编号分为x段，其中第I段为[Si,Ti](S1=1,Ti>=Si,Ti+1=Si+1)。然后的任务就是判断是否可以从A国的N颗炸弹中选出x颗，分别可以炸掉其中的一段。其实我们把搜索分为了两部分，（１）将B国武器根据编号分为x段。（２）判断是否可以从A国的N颗炸弹中选出x颗，分别可以炸掉其中的一段。建图：C[S][T][I]表示A国炸弹I是否可以炸到B国武器S,S+1..T-1,T。样例1：43606666000150311性能分析（1）：搜索的基本框架已经建立，虽然数据是随机生成的，但是m个B国武器的划分方案还是非常多的，有时可能高达2m。时间上很难承受，如果使用卡时，正确性受到影响，效果不会很好。只有4个数据可以在时限内出解，另外6个如果卡时，有2个也可以得到最优解。优化一（最优性）：如果A国炸弹可以重复使用，设：Dist[I]=炸掉B国武器I－m的最少使用炸弹数。可以用动态规划计算Dist值，状态转移方程如下：Dist[m+1]=0。Dist[I]=Min(Dist[J]+1|Can[I][J-1][K](1<=K<=n))(1<=I<=N)(I<J<=N+1)求Dist的时间复杂度为O(N3)。优化二（可行性）：部分搜索＋匹配的方法一般都可以用两个效果很好的可行性优化：(1)提前判断是否可以匹配成功，避免多余的搜索。(2)每次匹配可以从以前的匹配开始扩展，不需要重新开始。性能分析（2）：通过上述两个优化，程序的效率有了很大的提高。10个测试数据中有8个可以在时限内出解，另外2个如果卡时，也可以得到最优解。进一步优化：优化二虽然排除了许多不必要的划分，但是在判断时浪费了不少时间。因此，在枚举划分长度时