SGOI14之《图书查询问题》解题报告
   
　　　　　　　　　　　　　　　　　　　　　　　　　　　福州一中 陈阳

【思路】

　　看到这个题目，可能会有几种不同的想法：

　　1、 建立图论模型。但是目前没有想到比较好的建模方法，因为图论不太切合本题的本质特点。

　　2、 枚举所有的个不同的查询器，从中选取满足条件的。但是时间复杂度狂大。

【分析】

　　我们仔细分析题目，就会发现查询器更本质特点。我们定义查询器的阶数：一个查询器，如果有i个_，那么就称为i阶查询器。显然，按照题目要求，每个查询器都是不可以"升级"的，也就是查找范围最大的，因此，我们的目标是……找出所有最大查询器。

　　我们定义i阶弱查询器：只要求满足条件1，不要求满足条件2，也就是说不一定是最大查询器。我们一开始得到的特征串，就是所有0阶弱查询器。而2个i阶查询器，如果有且只有1位不同，那么可以把他们合并，成为一个i+1阶弱查询器。不难证明，通过不断的合并，可以得到所有的i阶弱查询器。而一个i阶弱查询器，如果不能和其他i阶弱查询器合并，那么它就是一个最大的，即是一个所求得查询器。

【解法】

　　通过以上分析，已经得到算法的概要，但是如果不注意实现方法，也可能无谓的增加复杂度。
算法步骤如下：

　　假设当前要合并的是i阶弱查询器。

　　1、 将所有i阶弱查询器按照1的个数从小到大排序。显而易见，i阶弱查询器j只能和一个i阶弱查询器合并，并且2个查询器的1的个数差只能为1，能够和j合并的弱查询器个数不超过n。所以排序之后可以有效的减少合并的范围。

　　2、 依次判断每个弱查询器j，假设它有k个1。

　　　　1) 考察每个含有k+1个1的i阶弱查询器t，如果他们可以合并的话，得到一个i+1阶弱查询器。同时标记j和t为已访问。
　　　　2) 判断这个弱查询器是否和原来已经得到的i+1阶弱查询器相同，不同的话加入i+1阶弱查询器的列表。
　　　　3) 如果遍历完所有t，j仍然未被访问，那么j是最大查询器，输出。

　　3、 如果i+1阶查询器个数〉0，那么i:=i+1，返回1；否则结束算法。
而求所有的关键查询器就比较简单，只要标记所有的查询器能够查找到的书，如果一本书只能被一个查询器查找到，这显然就是关键查询器。空间复杂度为O(m)，时间复杂度为O(r×m)。

【优化】

　　上述求所有查询器的过程，在时间和空间上都有很多可以优化的地方。

　　空间优化：计算i+1阶弱查询器，显然只用到i阶弱查询器，我们只要保存这2层，空间复杂度为 。

　　时间优化：

　　1、 加快排序操作：数据量可能比较大，排序应该使用O(nlogn)级别的排序，如快速排序。

　　2、 加快合并操作。算法中合并操作将被大量使用，因此一定要加快合并的速度。如果每个弱查询器用一个n位的3进制数（或者一个n位的串）表示的话，合并操作的时间是O(n)，不够理想。一个较好的数据结构是一个弱查询器用2个n位二进制数表示，弱查询器item由item.u和item.v表示，如果对于第i位，item.u的第i位是1，item.u的第i位是0，那么弱查询器item的输入的第i位是1；如果item.u的第i位是0，item.u的第i位是1，那么弱查询器item的输入的第i位是0；如果item.u的第i位是0，item.u的第i位是0，那么弱查询器item的输入的第i位是_。这样合并操作可以通过位运算完成。首先，判断是否可以合并，也就是要算两个弱查询器有几位不同。定义e=(item[i].u xor item[j].u) or (item[i].v xor item[j].v)，如果item[i]和item[j]的某一位不同，那么在e里面这一位将是1。统计e里面1的个数，如果恰好是1的话，就说明2个弱查询器有且只有1个不同，可以合并。然后得到合并结果newitem.u=item[i].u and item[j].u、newitem.v=item[i].v and item[j].v。判断e里面有几个1，可以用一个1..2的boolean数组，标记出所有的2。这样判断e里面有几个1只用O(1)，整个合并过程也降为O(1)。

　　3、 加快判断重复的速度：由于不同的弱查询器合并，可能产生相同的新弱查询器，因此要判重。如果用线性比较判重的话，O(m)，显然很慢。用树结构的话可以降为O(logm)，而用Hash的话可以降为O(1)（用(item[i].u+1)×(item[i].v+1)取模得到Hash值）。
　　经过优化之后，时间复杂度为

【小结】

　　出这题的想法来自逻辑范式化简的Quine-McCluskey方法的第一步和第二步：求所有的质蕴含（即极大圈）和必要质蕴含。从QM法得到的最主要的思想，就是通过不断合并得到结果。另外加上数据结构和算法的多方面优化，才能比较理想的用程序实现算法。


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有