资源描述：
《混乱无序的数据，通过简单的方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、约定：凡是用(*和*)括住的都不是发言内容！！！No.1(*动画结束*)大家好！我是南京市金陵中学的刘一鸣。今天我要和大家讨论的就是：一类搜索问题的优化思想——数据的有序化。No.2数据有序化的思想，就是将杂乱的数据，通过简单的分类和排序，变成有序的数据，从而加快搜索的速度。(*点击超级链接“为什么要进行数据有序化”，gotoNo.3*)No.3为什么要数据有序化呢？我们平时遇到的搜索问题，其数据往往有一大特点，那就是杂乱无章，毫无次序可言。(*点击鼠标，杂乱数据图出现*)就是杂乱的数据。(*点击鼠标，有
2、序数据图出现*)而这则是有序的数据。但是，在同一个题目中，应用的算法相同，而数据的有序程度不同，程序的效率往往会有较大的差异。下面，我就给大家举一个例子，“装箱问题”。No.4请大家仔细看题目，注意，这里和一般的“装箱问题”不同的地方就在于，题目是要求“放满”集装箱，也就是说，货物体积总和必须恰巧等于集装箱总体积。No.5这里提供了两种算法的时间比较，我们不难发现，第2种算法在多数情况下运行得很好，而第1种算法则不很理想。No.6两个程序效率不同的原因在哪里？(*点击鼠标，图表出现*)主要的原因是，我们在
3、使用最优性剪枝的时候，最希望的就是能较早地得到一个逼近最优解的较优解。(*点击鼠标，"最优解"出现*)这里就是最优解。(*点击鼠标，"不理想解"出现*)这里是不太理想的初始解，不排序而直接搜索，很可能会产生这种初始解。(*点击鼠标，"最理想解"出现*)这里是最理想的初始解，不排序而直接搜索和先排序再搜索都可能会产生这种初始解，不过后者的概率似乎略大。(*点击鼠标，"较理想解"出现*)这里是较为理想的初始解，先排序再搜索，很可能会产生这种初始解，这就是它的优势所在。No.7当然，数据有序化的优点并不仅仅是这
4、些。首先，对于大多数数据，它都有良好的优化效果，不过也不乏专门针对它的数据；其次，它实现起来很简单，对于刚才那个问题，在搜索前加上一个冒泡排序，只用加上几行就可以了；再其次，使用这种方法不会与其它优化方法形成冲突，甚至会为它们创造便利。所以，不难看出，数据有序化在实际应用中是大有裨益的。No.8数据有序化大致可以分为两种。第1种就是“预处理阶段的数据有序化”(*点击对应的HyperLink,gotoNo.9*)No.9(*点击鼠标*)一般来说，我们解决一个问题，都是读入数据以后直接进行数据的加工。(*点击
5、鼠标，直至"加工"出现*)预处理阶段的数据有序化，就是在加工之前多一个数据的处理过程，把它们由杂乱的排成有序的。(*点击鼠标，直至第2个箭头出现*)下面，我以IOI2000的"积木搭建"为例具体讲解。No.10这道题目的题意大家应该比较熟悉了，我就不再多讲了。传统的做法，是基于3维空间的算法，大家可以看看WangRenshen同学的解题报告，这种方法虽然容易想到，但是效率并不高，有些官方测试数据甚至会超时。现在，我们尝试在预处理阶段对数据进行有序化处理，来优化搜索。No.11先对构型的数据进行有序化处理。
6、(*点击鼠标*)将构型的所有小方块按照它们在空间中的顺序排序并编号。(*点击2次鼠标*)用一个集合[1,v]表示构型。(*点击2次鼠标*)这样，就将原来的3维几何体转化成了一个1维的集合。No.12然后，我们对积木的数据进行有序化处理。(*点击鼠标*)枚举所有能够插入构型的积木。(*点击2次鼠标*)用积木所包含的方块的编号组成的集合分别表示每块积木。(*点击3次鼠标*)这样，一个积木可以放进构型里，就可以用一个集合是否包含于另一个集合来表示。(*点击2次鼠标*)No.13下面，我们看看怎样从一个构型里挖去
7、一块积木。这是一个构型，(*点击鼠标*)我们用[1,10]表示。现在，我们挖去一块积木，(*点击鼠标，并将鼠标指针指向浅绿色区域*)大家请看，浅绿色区域代表挖掉的一块积木{3,6,7,9}，那么，剩下的构型就是集合{1,2,4,5,8,10}。(*点击2次鼠标*)这个操作，数据有序化处理以后，我们可以用集合的减运算来表示。(*点击鼠标*)No.14我们现在对于剩下的那个构型(*点击3次鼠标*)还想继续放一块积木(*点击3次鼠标*)就是这块{4,5,7,8}。我们发现，{4,5,7,8}并不包含于{1,2,
8、4,5,8,10}，(*点击鼠标*)所以我们判定，(*点击2次鼠标*)积木不能放入构型。No.15最后看看积木的冲突的判定(*点击2次鼠标*)不难看出，左右两个积木单独放，都能放进构型(*点击2次鼠标*)但是，这两个积木同时放，是存在冲突的，就是第7号方块(*鼠标指向7号方块*)(*点击鼠标*)转化为集合表示，我们会发现，冲突的积木的交集不为空集。No.16至此，预处理阶段的数据有序化处理全部完毕，大家可以看一看有序化前后的比
