Zplhz - 智破连环阵

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

深度优先搜索 搜索确实是一种无奈之下的选择，深度优先搜索就是把所有的情况都考虑进去，找出最优的。可以进行的优化有两种：

1、分枝定界、A*搜索。在正式搜索之前，进行一次预先的贪心处理，尽可能地缩小搜索范围。每次将当前状态，以及接下来达到目标所最少需要的炸弹数（估值）相加，如果大于等于当前的最少炸弹数，那么就剪枝。

2、即使这样，遇到了大数据还是铁定超时，为了让程序在时限内出界，可以适当卡结点。就是已经处理的情况数量，大于一个固定值的时候，输出当前较优值并且退出。

可惜这种算法，仍然无法得到一个较好的分值。 宽度优先搜索——IDA*搜索 为了尽可能缩小处理的情况总数，我们自然而然会想到宽度优先搜索。因为宽度优先搜索从优到劣地对序列进行扩展，对于所有比最优情况劣的状态，都是不会被扩展出来的。但是这一道题目会出现数量级别高达O(N!)的状态，空间显然是承受不住的。此时我们选用DFS ID搜索。

ID就是Iterative Deepening，说白了也就是不断地将深度进行加深，刚开始搜索深度为1的所有状态，如果没找到解，就搜索深度为2的所有状态……这个算法在一定程度上是BFS搜索的一种DFS形式扩展，空间复杂度被降低了，时间复杂度却不会上升太高。在这种搜索中，我们可以预先用A*的估值函数算出下界再开始深度加深，另外仍然可以使用分值定界A*，以及卡结点的优化方法。但是结果仍然不理想（参见“程序结果”） 冒险优化 5

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

注意到“问题简述”中，我将“测试数据是随机生成的”这句话加了下划线! 搜索时，把所能够扩展的状态，按照所能炸掉目标的数量从大到小排序。如果每一次我们都选择最大的（局部利益最优的），那么这就是一个贪心过程。在随机生成的数据中，分析一个最优的使用炸弹的序列，它在每一步所选取的是局部利益第几优的，不难发现大部分都是选取局部最优的！

这给我们什么启发呢？我们是不是能限定每次只选取局部利益前X优的进行搜索呢？这样程序的复杂度从O(N!)降到了O(X^N)级别，而且大多数情况下可以剪枝，是很有效果的！（如果X选取2，那么测试数据中有一个点得9分，一个点得11分，还有一个点超时）

仔细分析一下可以知道，选取“局部利益最优”的步骤还是非常之多的，如果每一步我们都考虑“次优局部利益”，着实还是一种浪费！另外，X取2也不是很符合实际，如果要拿满分甚至更多的分，势必要把X设定为3！

这时候我想到一个限定选取“次优局部利益”次数的算法。我们限定选取“次优局部利益”的总次数上限为MIDDLE_NODE_COUNT，限定选取“第三优局部利益”的总次数上限为LARGE_NODE_COUNT。因为最多M个目标，所以MIDDLE_NODE_COUNT取8左右比较合适，LARGE_NODE_COUNT取2左右比较合适。 总体比较与感想 这道题目的标准数据是两个搜索程序综合而得的，而且运行了相当长的时间才出结果。在考场上的我们，只有6sec的时间限制，强力冒险剪枝自然是必不可少的。

我在本题中使用的冒险剪枝是非常有效并且典型的。在搜索超时的情况下，

6

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

大多数选手会选择卡时，或者卡结点的方法。然而往往这种情况下，只搜索了搜索树的一小部分：

……

而我这样的贪心式搜索，可以覆盖搜索树的大部分地方，并且都是较优值！

[程序]

数据结构&算法设计 #define SMALL_NODE 1 #define MIDDLE_NODE 2 #define LARGE_NODE 3

#define MIDDLE_NODE_COUNT 8 #define LARGE_NODE_COUNT 2

代表前1~SMALL_NODE优的局部状态一定搜索，前SMALL_NODE+1~ MIDDLE_NODE优的局部状态搜索MIDDLE_NODE_COUNT个，前

MIDDLE_NODE+1~LARGE_NODE优的局部状态搜索LARGE_NODE_COUNT个。

int last[MaxN][MaxN];

last[i][j]计算第i个炸弹炸第j个目标后，可以持续炸到第多少个目标

7

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

int dis(int x1, int y1, int x2, int y2)

返回坐标距离的平方 void Init()

读入数据并且生成last数组，last生成完毕以后，各对象的坐标等参数都不需要了。

int maxd;

int hash[MaxN], ans[MaxN], now[MaxN];

maxd记录当前最大深度，hash记录被用过的炸弹，now记录当前炸弹序列，ans记录最优炸弹序列（用于输出）

struct TNext {

int v, last; };

记录局部的所有可转移的方案，v表示使用的炸弹编号，last表示可以出炸到多少号目标。

int lower_evaluate(int killed)

A*估值函数，killed为当前炸毁的目标数量，返回至少需要的炸弹数量。

int search(int Large_Node_Count, int Middle_Node_Count, int killed, int used)

当前剩下的使用“次优”和“第三优”局部状态的数量，killed为当前摧毁的目标数，used为当前使用的炸弹数。 void Doit()

主过程，进行深度的叠加 程序清单 （使用1024*768分辨率+Windows Notepad可达到视觉最佳效果）

8