浅谈逆向思维在解题中的应用课件.ppt

1、正难则反正难则反 浅谈逆向浅谈逆向思维在解题中的应用思维在解题中的应用 引入有一排路灯，一共八盏，均关闭。要求打开其中三盏，没有任意两盏相邻，有多少种不同的方式。如果直接考虑三盏打开的灯，需要讨论！不妨来考虑没有被打开的那些灯。引入要开3盏灯，则有5盏是关闭的两盏相邻的关闭的灯之间只能插入一盏开着的灯等价于在六个可选位置中选三个插入开着的灯所以答案为C(6,3)逆向思维引入逆向思维是一种思考问题的方式，它有悖于逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃多靠正常思维不能或是难于解决的问题

2、迎刃而解。而解。问题答案例一、Dinner Is Ready题目描述M根骨头分给n个孩子，第i个孩子有两个参数Mini和Maxi，表示第i个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。给出n(0n8),M(0Maxi(XiMaxi+1)|Si|无法计算，但是，|Si|可解！那么，我们是否可以通过可解的|Si|从而得到无法计算的|Si|呢？例一、Dinner Is Ready于是，我们就得到了：nSSSSAnswer.321n1113121n21.*)1(.).().(SSSSSSSSSSSSSnnn例一、Dinner Is Ready至此，问题已经被解决。时间复杂度为O(2n*(n+

3、M)在原集合Si的模|Si|不可解的情况下，我们通过可解的|Si|得到了一个基于容斥原理的算法。例二、Greedy Path题目描述 给定一个有向图G=(V,E)对于eE,有参数Ce和Te,分别表示该条边的费用与时间。求一个回路，使得回路中费用总和与时间总和的比值最大。例二、Greedy Path题目是求一条回路，但不是边权和最大或者最小，不能直接使用经典算法，似乎无从下手。我们的目标是找一条回路C=(V,E),使得F(C)最大：)(EeeEeeTCCF例二、Greedy Path0*)(*EeeEeeTCFC设S为G中所有回路组成的集合。假定C*=(V*,E*)S就是我们要求的最优回路*)(

4、EeeEeeTCCF定义函数O(t):),(*max)(EeeEeeSEVCTtCtO例二、Greedy Path我们做一个猜想：如果有o(t*)=0，也就是存在C*=(V*,E*)S 满足：*EeeEeeTCt我们认为C*就是最优回路！证明：如果存在另一条回路C1=(V1,E1)S更优 则*)()(*0*11111toTtCtTCtEeeEeeEeeEee与与O(t*)=0矛盾矛盾例二、Greedy Path更进一步，可以发现：如果t*是最优答案，则存在：*0)(*0)(*0)(tttotttottto根据该性质，便得到了算法：我们只要从一个包含t*的区间(tl,th)开始，不断地二分，计算

5、o(tl+th)/2)，得到新的上下界，直到达到精度要求。时间复杂度为O(lgK*N3)例三、Building Towers题目描述用N块积木来搭建H层的塔(不一定要用完所有的积木)要求相邻的两层积木数量相差为1最底层积木数量为M(N32767,H60,M10)任务1：可以搭建成多少种不同的塔?任务2：用H个整数从底到顶表示一个塔的结构，问字典序第K小的塔是什么？(H=6,M=2,N=13)例三、Building Towers动态规划算法动态规划算法用Fi,j,k表示当前层有i块砖，还剩下j层，可用的砖块数量为k的方案总数动态规划方程：Fi,j,k=Fi+1,j+1,k-i+Fi-1,j+1,

6、k-i边界条件:FM,H,N=1,其他为例三、Building Towers容易看出，这个动态规划方程一共涉及了N*M*K个状态，最大约为60*70*2400=10M。如果每个状态用一个double来保存信息，则至少需要80M的内存不论是时间复杂度，还是空间复杂度，都让人难以接受。失败例三、Building Towers将规划的顺序作一个反转，有什么好处呢？记忆化因子自顶向下的搜索算法逆向动态规划自底向上的动态规划算法例三、Building Towers逆向动态规划的好处在于：1)自顶向下的看问题，有“一览众山小”的开阔视野，可以顺利地为如何搜，先搜什么后搜什么，以及如何剪枝等作合理的布局。2

7、)在类似于本题的计数问题中，可以采用部分记忆化的方法，即只记录那些比较容易被多次搜索到的状态。这样一来，减少了存储的状态量，加快了查询的速度。例三、Building Towers让我们来看看逆向动态规划的精彩表现：NHM正向动态规划所需要处理的状态量逆向动态规划中存储的状态量 正逆向动态规划状态数比值1000401012000003055392.801500 501026250005371488.741200601028800004987557.741500601036000003801894.69总结例一 补集转化思想例二 参变量法例三 逆向动态规划总结以退为进避其锋芒攻其软肋打破思维定势Thank You!