国家集训队2009论文集浅谈估价函数在信息学

《国家集训队2009论文集浅谈估价函数在信息学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈估价函数在信息学竞赛中的应用浙江省绍兴一中周而进1目录摘要关键字前言1  估价函数在搜索中的应用1.1 在一类最优性问题中的应用1.1.1  UVa 10605 Mines For Diamonds1.1.1.1  问题描述1.1.1.2  分析1.1.2  UVa 11163  Jaguar King1.1.2.1  问题描述1.1.2.2  分析1.1.2.3  一些拓展1.1.3   小结1.2  在一类可行性问题中的应用1.2.1  Ural 1589 Sokoban1.2.1.1  问题描述1.2.1.2  分析1.2.2  小结2  

2、估价函数在优化一类动规方面的应用2.1  USACO DEC08 GOLD  Largest Fence2.1.1  问题描述2.1.2  分析2.2  小结3  估价函数在一类较优解求解问题中的应用3.1  TSP问题3.1.1  问题描述3.1.2  分析3.2  小结参考文献感谢2摘要估价函数在状态空间庞大，状态转移费时的一类逐步求精问题求解中有重要的应用。本文从3个方面，浅谈了估价函数在信息学竞赛中的应用，讲解了估价函数的选取、评估、应用，解决原本难以下手的问题。关键字估价函数逐步求精搜索动态规划较优性平衡性3前言估价函数是将状态在未来求解中

3、的优劣映射到一个具体数值的一种评估。举一个简单的例子，在一个国际象棋博弈中，一个刚学会下棋的小孩总会被告知：1个兵1分，一个象或马3分，一个车5分，皇后9分，有了这么一个标准，自然而然会得到一个最简单的估价，以下一步能吃掉对方的子的分值作为下一步的估价函数，如果将这个估价函数应用到程序中，那原本只会暴力搜索的程序就具备了初级棋手的实力了。信息学竞赛中题目往往变化多端，在无法找到最优方法解决问题的时候，通过合理运用估价函数，时常能达到出人意料的效果，事半功倍。41估价函数在搜索中的应用1.1在一类最优性问题中的应用在信息学竞赛中，我们往往会碰到一类最优

4、性问题的求解，而问题本身很难找到一个有效的多项式解法，于是只能采取搜索策略。但这类问题往往状态空间庞大，直接暴力搜索肯定效率低下。如果我们运用估价函数，就能及时对搜索进行剪枝，从而大大提高程序的效率。11.1.1MinesForDiamonds1.1.1.1问题描述给定一个n*m钻石矿区，你需要挖一些地道将所有的钻石挖出来：一条地道是一条从边境出发的折线，途中覆盖的钻石都算采到，两条折线不能相交，但可以相邻，求最小的地道总长度保证n，m≤11，钻石个数≤101.1.1.2分析首先，因为这个题范围比较小，也没有别的什么多项式方法，所以就考虑搜索。直接写

5、暴力自然是TLE的，所以需要剪枝。来看一个数据:来看看这个暴力的效果：123456深度94114551517766120生成节点数1UVa Online Judge 10605 Mines For Diamonds5789101112深度205116793522027370243721916826705638生成节点数1314151617深度2006646358721500167773974675362212004303生成节点数707可见到深度较深的时候，扩展的节点数疯狂上涨，所以如果我们能在前期就剪去一部分节点，那将大大提高程序的效率。自然而然的

6、，就想到了通过估价函数进行剪枝：如果g+h≥ans，那就没有必要继续搜索下去，这里g表示到达目前状态的花费，而h就是对当前局面转变成目标状态的一个乐观估计，也就是需要保证h≤h*，h*是真实的需要的步数。于是，如何设计估价函数h成了主要问题，重新审题发现，这里钻石的个数不是很多，而本问题的一个主要限制在于两条地道不能相交，如果我们忽略的这个条件，那原问题就转化为了：给定一个点集，需要你将他们划分成一些子集，每个子集的点通过一条链相连，要求总和最小。而这个问题是可以通过一个二次dp完成的，令opt[s]表示点集s的最优解，则有：opt[s]=min{o

7、pt[st]+w[t]，t⊂s}这里w[t]表示将点集t用一条链连起来的最小费用：w[t]=min{w[tk]+dist[tk][k]，k∈t}如果将opt[s]作为估价函数，首先他满足h≤h*，并且在大多数时候，这也是非常接近最有解的：对于这个数据，现在这个加了估价函数的程序，跑出的结果就是：123456深度000000生成节点数789101112深度6000000生成节点数1314151617深度0021124334216733生成节点数优化效果不言而喻，在UVa上也能以0.1s以内AC。721.1.211163JaguarKing1.1.2.1

8、问题描述有n只豹子要排队，位置为1..n(n%4=0)，，其中编号为1的为豹王，只有豹王可以和别的豹子交换位