- 浏览: 533068 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
参考文档:《搜索方法中的剪枝优化》——南开中学 齐鑫(见附件《剪枝》)
一、剪枝优化的核心问题是设计剪枝判断方法,即确定哪些枝条应当舍弃,哪些枝条应当保留的方法。
二、剪枝的原则:
1. 正确性:
即必须保证不丢失正确的结果
,这是剪枝优化的前提。
为了满足这个原则,我们就应当利用“必要条件”来进行剪枝判断。也就是说,通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样,就可以保证所剪掉的枝条一定不是正解所在的枝条。当然,由必要条件的定义,我们知道,没有被剪枝不意味着一定可以得到正解(否则,也就不必搜索了)。
2. 准确性:尽多剪枝
即能够尽可能多的剪去不能通向正解的枝条 。
3. 高效性:权衡“剪枝判断开销”和“剪枝提速效果”
剪枝判断的副作用及其改善:[
一般说来,设计好剪枝判断方法之后,我们对搜索树的每个枝条都要执行一次判断操作。然而,由于是利用出解的“必要条件”进行判断,所以,必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作,对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用,我们除了要下功夫改善判断的准确性外,经常还需要提高判断操作本身的时间效率。]
然而这就带来了一个矛盾
:我们为了加强优化的效果,就必须提高剪枝判断的准确性,因此,常常不得不提高判断操作的复杂度,也就同时降低了剪枝判断的时间效率;但是,如果剪枝判断的时间消耗过多,就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果,这恐怕也是得不偿失。很多情况下,能否较好的解决这个矛盾,往往成为搜索算法优化的关键。
三、可行性剪枝
在很多情况下,并不是搜索树中的所有枝条都能通向我们需要的结果,很多的枝条实际上只是一些死胡同。如果我们能够在刚刚进入这样的死胡同的时候,就能够判断出来并立即剪枝
四、最优性剪枝 /上下界剪枝
在我们平时遇到的问题中,有一大类是所谓最优化问题,即所要求的结果是最优解。如果我们使用搜索方法来解决这类问题,那么,最优性剪枝是一定要考虑到的。
为了表述的统一,首先要作一些说明:我们知道,解的优劣一般是通过一个评价函数来评判的。这里定义一个抽象的评价函数——“优度”,它的值越大,对应的解也就越优(对于具体的问题,我们可以认为“优度”代表正的收益或负的代价等)。
然后,我们再来回顾一下搜索最优解的过程:一般情况下,我们需要保存一个“当前最优解”,实际上就是保存解的优度的一个下界。在遍历到搜索树的叶子节点的时候,我们就能得到一个新的解,当然也就得到了它的评价函数值,与保存的优度的下界作比较,如果新解的优度值更大,则这个优度值就成为新的下界。搜索结束后,所保存的解就是最优解。
那么,最优性剪枝又是如何进行的呢?当我们处在搜索树的枝条上时,可以通过某种方法估算出该枝条上的所有解的评价函数的上界,即所谓估价函数 。显然, 大于当前保存的优度的下界,是该枝条上存在最优解的必要条件,否则就一定可以剪枝。所以,最优性剪枝也可以称为“上下界剪枝”。同时,我们也可以看到,最优性剪枝的核心问题就是估价函数的建立。
例题:
1. POJ 2331 Water Pipe==> IDA* +剪枝
语法注意:一般在使用memset()时,都不要将memset()放到子程序中初始化一个指针参数对应数组,直接在外面memset()就好了。避免出错! 参见“分类C/C++” ==> “指针常量,指针变量(sizeof使用注意)”
# include <cstdio> # include <cstring> # include <queue> using namespace std; int x1,y1,x2,y2; int k; int l[5]; int c[5]; int cmin; //(A*启发函数) h[i][j]是在假设有无限多每种型号的管道时,从(i,j)到目的点(x2,y2)至少还需要多少根管道 int hx[1001]; int hy[1001]; void bfs(int *h, int endPos){ queue<int> q; h[endPos]=0; q.push(endPos); int curPos; while(!q.empty()){ curPos=q.front(); q.pop(); int i;//假设每种型号的管道取之不尽 for(i=0;i<k;i++){ if(curPos-l[i]>=1 && h[curPos-l[i]]==-1){ h[curPos-l[i]]=h[curPos]+1; q.push(curPos-l[i]); } if(curPos+l[i]<=1000 && h[curPos+l[i]]==-1){ h[curPos+l[i]]=h[curPos]+1; q.push(curPos+l[i]); } } } } bool dfs(int cur, int depth, int type){ if(type==0){ //剪枝 if(depth+hx[cur]>cmin || hx[cur]==-1) return false; //x深搜到值后,继续深搜y if(cur==x2){ return dfs(y1,depth,1); //注意:不是dfs_y(y1,depth+1) } int i; for(i=0;i<k;i++){ if(c[i]==0) continue; if(cur<x2){ if(cur+l[i]<=1000){ // 不要反复检查: && hx[curX+l[i]]!=-1){ c[i]--; if(dfs(cur+l[i],depth+1,0)) return true; c[i]++; } if(cur-l[i]>=1){ c[i]--; if(dfs(cur-l[i],depth+1,0)) return true; c[i]++; } }else{ if(cur-l[i]>=1){ c[i]--; if(dfs(cur-l[i],depth+1,0)) return true; c[i]++; } if(cur+l[i]<=1000){ c[i]--; if(dfs(cur+l[i],depth+1,0)) return true; c[i]++; } } } }else{ //剪枝 if(depth+hy[cur]>cmin || hy[cur]==-1) return false; //y深搜到值 if(cur==y2){ return true; } int i; for(i=0;i<k;i++){ if(c[i]==0) continue; //根据大致方向优先向某个方向扩展 if(cur<y2){ if(cur+l[i]<=1000){ c[i]--; if(dfs(cur+l[i],depth+1,1)) return true; c[i]++; } if(cur-l[i]>=1){ c[i]--; if(dfs(cur-l[i],depth+1,1)) return true; c[i]++; } }else{ if(cur-l[i]>=1){ c[i]--; if(dfs(cur-l[i],depth+1,1)) return true; c[i]++; } if(cur+l[i]<=1000){ c[i]--; if(dfs(cur+l[i],depth+1,1)) return true; c[i]++; } } } } return false; } int main(void){ scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k); int i,depth_max=0; for(i=0;i<k;i++) scanf("%d",&l[i]); for(i=0;i<k;i++){ scanf("%d",&c[i]); depth_max+=c[i]; } //计算A*启发函数 memset(hx,-1,sizeof(hx)); memset(hy,-1,sizeof(hy)); bfs(hx,x2); bfs(hy,y2); //迭代加深DFS for(cmin=0;cmin<=depth_max;cmin++){//保证cmin在循环内部不被修改 if(dfs(x1,0,0)) break; } if(cmin<=depth_max) printf("%d",cmin); else printf("%d",-1); return 0; }
- 剪枝.rar (52.7 KB)
- 下载次数: 0
发表评论
-
快排备忘
2013-10-26 11:27 547http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3970页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 690本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2221本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1935k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1023一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 974要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 729引例、 例1、 例2、 例3、 ... -
模拟退火
2012-10-28 16:34 1199引用:http://www.cnblogs.com/heaad ... -
计算几何(一)——基础算法
2012-07-12 21:07 1903待续 《计算几何资料》为提纲 1. (1) 有向线段 ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 885参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 940这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7180二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1046这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1543一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1492一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
大整数运算(部分转载)
2012-04-12 21:36 1170待补充:“浮点数高精度运算” 参见这里==> ... -
单向链表相关
2012-04-10 16:42 953单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1648前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 2999参考这篇文章,以下前 ...
相关推荐
文中讨论了搜索方法中最常见的一种优化技巧——剪枝,而且主要以剪枝判断方法的设计为核心。文章首先借助搜索树,形象的阐明了什么是剪枝;然后分析了设计剪枝判断方法的三个原则:正确、准确、高效,本文将常见的...
ACM中的回溯法:搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的...本文所讨论的主要内容就是在建立算法的结构之后,对程序进行优化的一种基本方法——剪枝。
齐鑫:《搜索方法中的剪枝优化》 邵铮:《数学模型的建立、比较和应用》 石润婷:《隐蔽化、多维化、开放化——论当今信息学竞赛中数学建模的灵活性》 杨帆:《准确性、全面性、美观性——测试数据设计中的三要素》 ...
这里设计和实现了一个人机对下的五子棋程序,采用了博弈树的方法,应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。
目录: │ Single Agent Search.ppt │ 寻找必败态——博弈问题...│ 谈搜索算法的剪枝优化.pdf │ 近似、随机与局部搜索.pdf │ └─分支限界 优先队列与分支限界法.pdf 分支限界法.ppt 分支限界法的基本思想.ppt
齐鑫:《搜索方法中的剪枝优化》 邵铮:《数学模型的建立、比较和应用》 石润婷:《隐蔽化、多维化、开放化——论当今信息学竞赛中数学建模的灵活性》 杨帆:《准确性、全面性、美观性——测试数据设计中的三要素》 ...
齐鑫:《搜索方法中的剪枝优化》 邵铮:《数学模型的建立、比较和应用》 石润婷:《隐蔽化、多维化、开放化——论当今信息学竞赛中数学建模的灵活性》 杨帆:《准确性、全面性、美观性——测试数据设计中的三要素》 ...
齐鑫:《搜索方法中的剪枝优化》 邵铮:《数学模型的建立、比较和应用》 石润婷:《隐蔽化、多维化、开放化——论当今信息学竞赛中数学建模的灵活性》 杨帆:《准确性、全面性、美观性——测试数据设计中的三要素》 ...
一、棋子识别 监督学习算法——采用YOLO-tiny(基于keras) 二、搜索算法 采用alpha-beta剪枝对棋局局面进行搜索 三、基于ANN的棋局评估 将实验二中的棋局判断函数更改为人工神经网络模型,并采用进化计算对该网络...
搜索方法中的剪枝优化 南开中学 齐鑫 数学模型的建立、比较和应用 苏州中学 邵铮 隐蔽化、多维化、开放化 ──论当今信息学竞赛中数学建模的灵活性 杭州外国语学校 石润婷 准确性、全面性、美观性 ——测试数据...
1.2.1 世界规模的大赛——Google Code Jam(GCJ) 1.2.2 向高排名看齐!——TopCoder 1.2.3 历史最悠久的竞赛—— ACM-ICPC 1.2.4 面向中学生的信息学奥林匹克竞赛——JOI-IOI 1.2.5 通过网络自动评测——Online ...
针对属性约简算法CARRDG在实现技术层面上的可改进之处,在原有的三种约简分辨图深度优先搜索原则(成员独占原则、友人劝阻原则、陌生人吸纳原则)的基础上,增加新的深度优先搜索原则——阻挡层阻挡原则。...
骆 骥 -《由"汽车问题"浅谈深度搜索的一个方面——搜索对象与策略的重要性》 毛子青 -《动态规划算法的优化技巧》 俞 玮 -《基本动态规划问题的扩展》 张一飞 -《求N!的高精度算法》 ## 2002 戴德承 -《退...
对“热度”评价进行建模 什么时候使用决策树 练习 第8章 构建价格模型 构造一个样本数据集 k-最近邻算法 为近邻分配权重 交叉验证 不同类型的变量 对缩放结果进行优化 不对称分布 使用真实数据——eBay API 何时...
这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些...
使用真实数据——eBay API 189 何时使用 k-最近邻算法 195 第9章 高阶分类:核方法与 SVM 197 婚介数据集 197 数据中的难点 199 基本的线性分类 202 对数据进行缩放处理 209 理解核方法 211 支持向量机 215 ...
计算机科学丛书——模式分类 Pattern Classification,Second Edition 中译本 ------------------------------------------------------------------------- 作者:(美)Richard O.Duda Peter E.Hart David G....
计算机科学丛书——模式分类 Pattern Classification,Second Edition 中译本 ------------------------------------------------------------------------- 作者:(美)Richard O.Duda Peter E.Hart David G....