资源描述：
《一类搜索的优化思想 ——数据有序化.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、一类搜索的优化思想 ——数据有序化南京市金陵中学刘一鸣数据有序化为什么要进行数据有序化数据有序化的实现两种实现方法的比较数据有序化的思想，就是将杂乱的数据，通过简单的分类和排序，变成有序的数据，从而加快搜索的速度。为什么要进行数据有序化杂乱的数据有序的数据例1装箱问题题目大意：现有一个体积为V的集装箱和N种货物，每一种货物都有固定的体积，数量无限。你的任务是：写一个程序，求出最少用多少个货物，就能放满集装箱。数据规模：V货≤V≤109运行时间的对比N不排序，直接搜索先按体积从大到小排序，再搜索10>160秒9.8545秒30>200秒0.1356秒60>200秒0.1595秒100>200秒0
2、.2285秒测试方法：随机生成20个数据，测试运行时间并求平均值。程序效率不同的原因不理想的初始解最理想的初始解最优解比较理想的初始解数据有序化的益处对于大多数的数据，都有良好的优化效果；简便易行；和其他类型的优化方法一般都不冲突。数据有序化的实现预处理阶段的数据有序化实时处理阶段的数据有序化预处理阶段的数据有序化加工常规方法杂乱的数据有序的数据例2积木搭建题目大意：给定12种积木和一个体积小于50的构型，求最少使用多少个积木可以将这个构型搭建起来目标构型示例积木示例第1步数据有序化yxz12345678910集合[1,10]第2步数据有序化123456791083679积木{3,6,7,9}
3、积木能放进构型12345679108[1,10]{1,2,4,5,8,10}[1,10]-{3,6,7,9}={1,2,4,5,8,10}从构型中挖去一个积木试图再放一块积木123456791084578{4,5,7,8}{1,2,4,5,8,10}积木不能放入构型积木的冲突1234567108457836794578936793679458{3,6,7,9}U{4,5,7,8}={7}≠φU数据有序化前后 数学模型的对比数据有序化前数据有序化后目标构型（3维）目标集合（1维）积木（3维）小集合（1维）积木拼接成为目标构型小集合的合并成为目标集合积木在3维空间里没有冲突小集合的交集为空集数据有
4、序化后，数学模型得到了精简实时处理阶段的数据有序化加工常规方法杂乱的数据有序的数据保存舍弃传统表示方法SS1S2Sn……保存舍弃如果S或S的同构状态中有一个已经保存否则最小表示法SSmin保存舍弃已保存？YN例3N皇后问题-2题目大意：假定通过翻转、旋转得到的状态与原状态属于同构状态，求所有不同构的n皇后状态总数。状态表示方法由于一行中只能有一个皇后，所以用一个n元组(a1,a2,a3,…,an)表示当前的状态，其中ai表示第i列的皇后所在的行。QQQQQ(3,1,4,2,5)翻转、旋转的具体过程(1)以铅垂线为轴的翻转：Q1Q2Q3Q4Q5Q1Q2Q3Q4Q5（a1,a2,a3,a4,a5）
5、（a5,a4,a3,a2,a1）→90度、180度、270度的旋转（a1,a2,a3,a4,a5）→（6-b1,6-b2,6-b3,6-b4,6-b5）→（6-a5,6-a4,6-a3,6-a2,6-a1）→（6-b5,6-b4,6-b3,6-b2,6-b1）以水平线为轴的翻转：（a1,a2,a3,a4,a5）→（6-a1,6-a2,6-a3,6-a4,6-a5）以对角线为轴的翻转：（a1,a2,a3,a4,a5）→（b1,b2,b3,b4,b5）→（b5,b4,b3,b2,b1）翻转、旋转的具体过程(2)应用数据有序化SSmin枚举已保存？保存YN舍弃当前状态可能是最小表示吗？YN回溯新的剪
6、枝条件a1≤a5a1≤6-a1a1≤b1a1≤b5a1≤6-b1a1≤6-a5a1≤6-b5空间复杂度的降低SSmin枚举已保存？保存YN舍弃当前状态可能是最小表示吗？YN回溯应用最小表示法的算法 与常规算法的比较状态的生成判断同构的费用（或判断最小表示的费用）时间复杂度空间复杂度常规算法O(a*N!)(a<1)O(N*
7、S
8、)O(a*N!*N*
9、S
10、)O(N*
11、S
12、)应用最小表示的算法O(b*N!)(b<13、。追求好的性价比。谢谢！请大家多多指教!
