算法合集之《“约制、放宽”方法在解题中的应用》

《算法合集之《“约制、放宽”方法在解题中的应用》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006年全国信息学冬令营讲座一张一弛，解题之道——“约制、放宽”方法在解题中的应用广东省中山纪念中学陈启峰第21页共21页2006年全国信息学冬令营讲座目录一张一弛，解题之道1——“约制、放宽”方法在解题中的应用1目录2【摘要】3【关键字】3“约制、放宽”方法的定义4引言4例题分析4[例一]骑士4【问题描述】4【问题分析】5【数学模型】5【算法模型分析】5【确定总算法和研究对象】5【分析研究对象】6【“约制”方法确定新任务】6【寻找两个向量的规律】6【“约制”方法解决新任务】8【回到研究对象】10【回到起点】11【小结】11[例二]友

2、好的动物12【问题描述】12【问题分析】12【数学模型】12【原始算法的矛盾】13【数据范围分析】13【数据结构优化时的矛盾】13【分析矛盾】14【“放宽”方法化解矛盾】14【小结】15[例三]消防站16【问题描述】16【问题分析】16【数学模型】16【算法模型分析】16【预处理】17【确定动态规划时的矛盾】17【总结分析】17第21页共21页2006年全国信息学冬令营讲座【“放宽”方法转化限制】18【进一步分析】18【“约制”方法增添限制】19【确定动态规划转移方程】19【小结】20总结21【感谢】21【摘要】本文主要阐述了“约制、放

3、宽”方法在解题中的应用。第一部分解释了什么“约制、放宽”方法。第二部分论述了在解题中为什么需要“约制、放宽”方法。第三部分通过分析《骑士》、《友好的动物》和《消防站》分别介绍了“约制”方法、“放宽”方法和两者综合应用在解题中起的作用。最后作者结合自身经验谈谈在解题中如何灵活运用“约制、放宽”方法。【关键字】“约制”方法“放宽”方法过于宽松过于繁杂过于独立过于严格约制条件、限制放宽条件、限制第21页共21页2006年全国信息学冬令营讲座正文“约制、放宽”方法的定义“约制”方法——添增一些约束的条件、限制，并保证在这些条件和限制下依然能找到

4、解。“放宽”方法——减除、放宽一些条件、限制，并保证在这些条件和限制下依然能找到解。引言在分析问题、设计算法的时候，我们常常会觉得条件、限制过于繁杂、严格或者过于宽松、独立以致无法下手。这时，不妨尝试“约制、放宽”方法。“约制”方法往往在我们迷茫时指出一条光明大道，“放宽”方法则常常在关系错综复杂时破除阻扰和荆棘。巧妙地运用这两种方法能使我们在解题中排除万难，直入脏腑。例题分析下面，本人从“约制”方法，“放宽”方法和两者的综合应用三个方面精心挑选了三个题目并作详细分析，希望这能起到抛砖引玉的作用。[例一]骑士选自POI2005的STAG

5、E1的《KNIGHTS》【问题描述】有一骑士在一个无限大的棋盘上移动。它每次的移动都用一个整数对来描述——整数对（a,b）表示骑士能从位置（x,y）跳到位置(x+a,y+b)或者(x-a,y-b)。每个骑士有一系列的已确定的整数对，描述这骑士能进行哪些移动。我们保证每个骑士能到达的位置不在同一直线上。当两个骑士以位置（0，0）为始点能到达的所有位置完全相同时（可能做很多次移动），我们就说这两个骑士是等价的。可以证明对于每一个骑士，都存在一个只有两个整数对的等价骑士。第21页共21页2006年全国信息学冬令营讲座任务：读入一个骑士的所有整

6、数对，找出一个只有两个整数对的等价骑士。【问题分析】【数学模型】令输入的整数对分别表示为向量,向量……向量，找出两个整数对——向量和与这n个向量等价,也就是对于任意的整数序列，都存在两个整数使得并且对于任意两个整数，都存在一个整数序列，使得【算法模型分析】看到这个题目，最容易想到的算法是枚举这两个向量和用宽度优先搜索判断是否等价。但是要寻找的这两个向量的范围是无限大的，并且棋盘也是无限大的。因此这个算法宛如大海捞针一般，极难在有限的时间内找到解。然后尝试贪心、动态规划、图论等硬做的算法，但这些算法都在预料之中以失败告终。最后，看来只有必

7、经之路——数学方法才能可以解决这个问题。【确定总算法和研究对象】用数学方法解决等价转化等题目的方法还是不胜枚举的。例如有归纳法，有总体法，有解方程法，有数形结合。对于这个题目，我们应选取什么数学方法好呢？注意到，如果任意的三个向量都可以与某两个向量等价，那么便可以从n(n>2)个向量中任选三个向量出来，用与它们等价的两个向量代替它们，从而变成n-1个向量。不断重复上述的过程，直到只剩下两个向量为止，这时剩下的两个向量便是一个可行解。而由问题描述可以知道：对于任意三个向量都存在两个向量与它们等价。这便意味这种方法是可行的。于是，就可以确定

8、下总算法——不断化三为二第21页共21页2006年全国信息学冬令营讲座，同时也产生了我们的研究对象——如何把三个向量等价替换为两个向量？【分析研究对象】因为满足条件的解（等价的两个向量）是无限多个的，解的范