《一类搜索的优化思想》由会员分享，可在线阅读，更多相关《一类搜索的优化思想（30页珍藏版）》请在金锄头文库上搜索。
1、一类搜索的优化思想 数据有序化,数据有序化,为什么要进行数据有序化 数据有序化的实现 两种实现方法的比较,数据有序化的思想，就是将杂乱的数据，通过简单的分类和排序，变成有序的数据，从而加快搜索的速度。,为什么要进行数据有序化,例1 装箱问题,题目大意：现有一个体积为V的集装箱和N种货物，每一种货物都有固定的体积，数量无限。你的任务是：写一个程序，求出最少用多少个货物，就能放满集装箱。数据规模：V货V109,运行时间的对比,测试方法：随机生成20个数据，测试运行时间并求平均值。,程序效率不同的原因,不理想的初始解,最理想的初始解,最优解,比较理想的初始解,数据有序化的益处,对于大多数的数据，都有
2、良好的优化效果； 简便易行； 和其他类型的优化方法一般都不冲突。,数据有序化的实现,预处理阶段的数据有序化 实时处理阶段的数据有序化,预处理阶段的数据有序化,加工,例2 积木搭建,题目大意：给定12种积木和一个体积小于50的构型，求最少使用多少个积木可以将这个构型搭建起来,目标构型示例,积木示例,第1步数据有序化,集合1,10,第2步数据有序化,1,2,3,4,5,6,7,9,10,8,积木3,6,7,9,1,2,3,4,5,6,7,9,10,8,1,10,1,2,4,5,8,10,1,10-3,6,7,9 = 1,2,4,5,8,10,从构型中挖去一个积木,试图再放一块积木,4,5,7,8,
3、1,2,4,5,8,10,积木不能放入构型,积木的冲突,1,2,3,4,5,6,7,10,8,9,数据有序化前后 数学模型的对比,数据有序化后，数学模型得到了精简,实时处理阶段的数据有序化,加工,保存,舍弃,传统表示方法,S,保存,舍弃,最小表示法,S,Smin,保存,舍弃,例3 N皇后问题-2,题目大意：假定通过翻转、旋转得到的状态与原状态属于同构状态，求所有不同构的n皇后状态总数。,状态表示方法,由于一行中只能有一个皇后，所以用一个n元组(a1,a2,a3,an)表示当前的状态，其中ai表示第i列的皇后所在的行。,(3,1,4,2,5),翻转、旋转的具体过程(1),以铅垂线为轴的翻转：,（
4、a1,a2,a3,a4,a5）,（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),应用数据有序化,S,Smin,枚举,回溯,新的剪枝条件,a1a5 a16-a1 a1b1 a1b5 a16-b1 a16-a5 a16-b5,空间复杂度的降低,S,Smin,枚举,回溯,应用最小表示法的算法 与常规算法的比较,两种实现方法的比较,总结,努力创造符合科学美的数据。 追求好的性价比。,谢谢！,请大家多多指教!,
