logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

一类搜索的优化思想.PPT 30页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:593 KB
下载过该文档的会员
你可能关注的文档:
一类搜索的优化思想 ——数据有序化 数据有序化 为什么要进行数据有序化 数据有序化的实现 两种实现方法的比较 数据有序化的思想,就是将杂乱的数据,通过简单的分类和排序,变成有序的数据,从而加快搜索的速度。 为什么要进行数据有序化 杂乱的数据 有序的数据 例1 装箱问题 题目大意: 现有一个体积为V的集装箱和N种货物,每一种货物都有固定的体积,数量无限。你的任务是:写一个程序,求出最少用多少个货物,就能放满集装箱。 数据规模:V货≤V≤109 运行时间的对比 N 不排序,直接搜索 先按体积从大到小排序,再搜索 10 >160秒 9.8545秒 30 >200秒 0.1356秒 60 >200秒 0.1595秒 100 >200秒 0.2285秒 测试方法:随机生成20个数据,测试运行时间并求平均值。 程序效率不同的原因 不理想的初始解 最理想的初始解 最优解 比较理想的初始解 数据有序化的益处 对于大多数的数据,都有良好的优化效果; 简便易行; 和其他类型的优化方法一般都不冲突。 数据有序化的实现 预处理阶段的数据有序化 实时处理阶段的数据有序化 预处理阶段的数据有序化 加工 常规方法 杂乱的数据 有序的数据 例2 积木搭建 题目大意:给定12种积木和一个体积小于50的构型,求最少使用多少个积木可以将这个构型搭建起来 目标构型示例 积木示例 第1步数据有序化 y x z 1 2 3 4 5 6 7 8 9 10 集合[1,10] 第2步数据有序化 1 2 3 4 5 6 7 9 10 8 3 6 7 9 积木{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} 从构型中挖去一个积木 试图再放一块积木 1 2 3 4 5 6 7 9 10 8 4 5 7 8 {4,5,7,8} {1,2,4,5,8,10} 积木不能放入构型 积木的冲突 1 2 3 4 5 6 7 10 8 4 5 7 8 3 6 7 9 4 5 7 8 9 3 6 7 9 3 6 7 9 4 5 8 {3,6,7,9} U {4,5,7,8} = {7} ≠φ U 数据有序化前后 数学模型的对比 数据有序化前 数据有序化后 目标构型(3维) 目标集合(1维) 积木(3维) 小集合(1维) 积木拼接成为目标构型 小集合的合并成为目标集合 积木在3维空间里没有冲突 小集合的交集为空集 数据有序化后,数学模型得到了精简 实时处理阶段的数据有序化 加工 常规方法 杂乱的数据 有序的数据 保存 舍弃 传统表示方法 S S1 S2 Sn …… 保存 舍弃 如果S或S的同构状态 中有一个已经保存 否则 最小表示法 S Smin 保存 舍弃 已保存? Y N 例3 N皇后问题-2 题目大意:假定通过翻转、旋转得到的状态与原状态属于同构状态,求所有不同构的n皇后状态总数。 状态表示方法 由于一行中只能有一个皇后,所以用一个n元组(a1,a2,a3,…,an)表示当前的状态,其中ai表示第i列的皇后所在的行。 Q Q Q Q Q (3,1,4,2,5) 翻转、旋转的具体过程(1) 以铅垂线为轴的翻转: Q1 Q2 Q3 Q4 Q5 Q1 Q2 Q3 Q4 Q5 (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 枚举 已保存? 保存 Y N 舍弃 当前状态可能是最小表示吗? Y N 回溯 新的剪枝条件 a1≤a5 a1≤6-a1 a1≤b1 a1≤b5 a1≤6-b1 a1≤6-a5 a1≤6-b5

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号