浅析解 “对策问题” 的两种思路.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浅析解,“,对策问题,”,的两种思路,从取石子问题谈起,浅析解,“,对策问题,”,的两种思路,内容提要：,运 筹 学,规划论,动态规划,图 论,对策论,排队论,存储论,等等,线性规划,整数规划,等等,本文所要探讨的正是此类“对策问题”。,运筹学是一门十分年轻的学科，内容包括：规划论、图论、对策论、排队论等。,竞赛中最常出现的对策问题是：有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。,由于对局的复杂性和取胜的多样性，文章将从一道经典的“对策问题”,取石子谈起，着重阐述两种基本思想方法。,浅析解,“,对策问题,”,的两种思路,问 题 描 述,有,N,粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。,请问，甲能否获胜？（1,N,100）,解 析,在本题中，影响胜败的有两个关键因素：,l,当前石子总数,N,l,当前一次最多可拿的石子数,K,用这两个因素,（,N，K）,来表示当前局面的“,状态,”。题目要求的是判断状态,（,N，N,-,1）,是先手必胜还是必败。,浅析解,“,对策问题,”,的两种思路,用一个简单例子分析：假设有,N=,4,粒石子，则一开始甲最多能取,3,粒，用,（4，3）,来表示初始状态。,状态转移的拓扑结构,甲取1粒,甲取2粒,甲取3粒,乙取1粒,乙取2粒,乙取1粒,乙取2粒,乙取1粒,甲取1粒,甲取2粒,甲取1粒,甲取1粒,乙取1粒,（,4,3,）,（,3,2,）,（,2,2,）,（,1,1,）,（,2,2,）,（,1,1,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,自顶而下构造,浅析解,“,对策问题,”,的两种思路,（,4,3,）,（,3,2,）,（,2,2,）,（,1,1,）,（,2,2,）,（,1,1,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,败,败,败,败,败,败,注：这里的胜败指的均是先手胜败。,1如果一个状态没有子状态，是结局，则根据题目条件判定胜负,浅析解,“,对策问题,”,的两种思路,胜,胜,胜,胜,胜,胜,（,4,3,）,（,3,2,）,（,2,2,）,（,1,1,）,（,2,2,）,（,1,1,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,败,败,败,败,败,败,注：这里的胜败指的均是先手胜败。,1如果一个状态至少有一个子状态是先手败，则该状态是先手胜,浅析解,“,对策问题,”,的两种思路,胜,败,胜,胜,胜,胜,胜,胜,（,4,3,）,（,3,2,）,（,2,2,）,（,1,1,）,（,2,2,）,（,1,1,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,败,败,败,败,败,败,注：这里的胜败指的均是先手胜败。,1如果一个状态的所有子状态都是先手胜，则该状态是先手败,浅析解,“,对策问题,”,的两种思路,“动态规划”,或,“记忆化搜索”,空间复杂度,O(N,2,),时间复杂度,O(N,3,),（,4,3,）,（,3,2,）,（,2,2,）,（,1,1,）,（,2,2,）,（,1,1,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,（,1,1,）,（,0,0,）,（,0,0,）,（,0,0,）,浅析解,“,对策问题,”,的两种思路,思路一：,一般性方法,状 态,胜负规则,扩展规则,实现方法,“,一般性方法,”,是从初始状态出发，自顶向下，考察所有状态，,逐步构造出,“,状态转移的拓扑结构,”，,有通行的胜败规则和实现方,法，因此应用十分广泛。,例如,IOI96,的,取数字,，,IOI2001,Ioiwari,都可以用“,一般性方,法,”来解决。,浅析解,“,对策问题,”,的两种思路,思路一：,一般性方法,状 态,列举影响结局胜负的所有因素，综合描述成“,状态,”。根据对局时状态之间的变化，,自顶而下,构造出“,状态转移的拓扑结构,”。,胜负规则,一个状态的胜负取决于其所有子状态的胜负。,1如果一个状态没有子状态，是结局，则根据题目条件判定胜负,1如果一个状态至少有一个子状态是先手败，则该状态是先手胜,1如果一个状态的所有子状态都是先手胜，则该状态是先手败,浅析解,“,对策问题,”,的两种思路,思路一：,一般性方法,扩展规则,在某些场合下，还可以记录一个状态先手胜（负）的最大（最小）利益，以数值形式描述，再根据题目中相应的条件，构成新的具有,针对性,的推算规则。例如,IOI2001Score,一题就是用扩展规则解决的。,实现方法,1预先处理（关键）,列举状态；构造“状态转移的拓扑结构”；动态规划或记忆化搜索求状态先手胜负。,1对局策略,依据已知的状态胜负，时刻把先手必败的状态留给对方。,浅析解,“,对策问题,”,的两种思路,思路一：,一般性方法,“,一般性方法,”也有它的不足：,基 础,“,一般性方法,”,是以“,状态转移的拓扑结构,”为基础设计的。,空 间,“,一般性方法,”,要考察,所有,状态的先手胜负。如果状态数目过多，甚至是无穷多，那,“,一般性方法,”,就无能为力了。,时 间,“,一般性方法,”,还要通过胜负规则来研究状态之间的关系。,如果状态过多，关系复杂，就可能导致算法效率下降。,浅析解,“,对策问题,”,的两种思路,思路一：,一般性方法,由此可见，“,一般性方法,”并不能解决所有的“对策问题”。于是，各种各样的针对单独问题的特殊解法应运而生，不妨总的称之为“,特殊性方法,”。,为了弥补“,一般性方法,”的缺陷，“,特殊性方法,”势必是寻找一种“,决策规律,”，能依据当前状态，按照“,决策规律,”直接决定下一步的走法。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,先看一个简单的例子：,在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？,事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总在其关于中心对称处放一枚，最终甲必然获胜。,甲,乙,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,在这个例子中，甲找到了一种必胜的状态。这种状态是具有某种“平衡性”的，称之为“,平衡状态,”。每当乙破坏了“平衡”后，甲立即使其恢复“平衡”，直到结局。,先看一个简单的例子：,在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？,甲,乙,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,那么怎样寻找“对策问题”中的“,平,衡状态,”呢？如何确定“,决策规律,”使我,方在平衡被破坏后必然能恢复呢？,先看一个简单的例子：,在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？,甲,乙,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,“,一般性方法,”是从初始状态开始，,自顶而下,建立“,状态转移的拓扑结构,”。现在，不妨反其道而行之，从结局或小规模残局开始，,自底向上,分析。,甲必败,：,甲必胜,：,2,3,4,5,6,7,8,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,Fibonacci,数列,“,一般性方法,”是从初始状态开始，,自顶而下,建立“,状态转移的拓扑结构,”。现在，不妨反其道而行之，从结局或小规模残局开始，,自底向上,分析。,甲必败,：,甲必胜,：,2,3,4,5,6,7,8,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,猜,想,：,设,F,为,Fibonacci,数列,（,F,1,=2，F,2,=3，F,K,=F,K,-,1,+F,K,-,2,）,初始时有,N,粒石子，若,NF,则先手必败，否则先手必胜。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,性质,1,：,若,KN，,则状态,（,N,K）,先手必胜,。,性质,2,：,若状态（,N,N-1）,先手必败，则状态（,N,K）K N,先手必败,。,性质,3,：,若状态（,N,K）K N，,则最后一次取走的石子数目不超过2,N/3,。,性质4,：,4,F,i-1,/3,F,i,（F,1,=2，F,2,=3，F,K,=F,K-1,+F,K-2,）,。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,结论1,：状态(,F,i,，A,）A N-K,由性质1，后手获胜。,后手获胜，先手败,K,(,N-K,2K),浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,证 明,：,F,i-1,F,i,F,i,+,1,K,（一）,F,1,(=2)，F,2,(=3),时，显然成立。,（二）若,F,1,至,F,i,成立，则,F,i+1,成立。,设先手取,K,粒石子,。,（1）若,KF,i-1,后手得状态(,N-K,2K),后手获胜，先手败,（2）若,K F,i-1,根据假设（,F,i-1,K,）,K F,i-1,必败，所以后手可以使先手面临(,F,i,，X,),状态。,(,F,i,X,),浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,证 明,：,（一）,F,1,(=2)，F,2,(=3),时，显然成立。,（二）若,F,1,至,F,i,成立，则,F,i+1,成立。,设先手取,K,粒石子,。,（1）若,KF,i-1,后手得状态(,N-K,2K),后手获胜，先手败,（2）若,K F,i-1,F,i-1,F,i,F,i,+,1,K,(,F,i,X,),由性质3：,X2F,i-1,/3 2=4F,i-1,/3,由性质4：,X4F,i-1,/3,F,i,因此(,F,i,X,),是必败,后手获胜，先手败,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,证 明,：,（一）,F,1,(=2)，F,2,(=3),时，显然成立。,（二）若,F,1,至,F,i,成立，则,F,i+1,成立。,设先手取,K,粒石子,。,（1）若,KF,i-1,后手得状态(,N-K,2K),后手获胜，先手败,（2）若,K 2，,先手必胜。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,F,F,N,F,平衡状态:,Fibonacci,数,决策规律:反复缩小范围，找最大,Fibonacci,数,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,空间复杂度,O(1),时间复杂度,O(logN,),特殊性方法,空间复杂度,O(N,2,),时间复杂度,O(N,3,),一般性方法,大大降低,平衡状态:,Fibonacci,数,决策规律:反复缩小范围，找最大,Fibonacci,数,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,状 态,逆向分析,“,特殊性方法,”,是从结局或残局出发，自底而上分析，无须,构造,“,状态转移的拓扑结构,”，,无须考察所有可能的状态与策略，,时间和空间复杂度相对于“,一般性方法,”都不高。,例如,POI99,多边形,，,IOI96,的,取数字也,可以用“,特殊性,方法,”来解决。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,状 态,列举影响结局胜负的所有因素，综合描述成“,状态,”，但并不需要构造出“,状态转移的拓扑结构,”。,浅析解,“,对策问题,”,的两种思路,思路二：,特殊性方法,逆向分析,从简单的结局或残局开始，自底向上分析。,考察特殊情况下（譬如小规模，对称，极大极小等特殊值），先手胜或先手败的一类状态，并尝试从以下几个方面寻找共性：,1,对称性,1,简捷性,1,奇异性,通过分析，将所得性质推广到一般情况，从而找出一类必胜或必败的“,平衡状态,”，同时也得到保持状态“平衡”的“,决策规律,”。,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,1,一次可取先前对方所取石子数的,3,倍,取石子问题的推广：,1,一次可取先前对方所取石子数的,4,倍,1,一次可取先前对方所取石子数的,5,倍,1,一次可取先前对方所取石子数的,K,倍,1,一 般 性 方 法,特 殊 性 方 法,VS,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,一般性方法,：,自顶而,下 考察所有状态胜负,特殊性方法,：,自底而上,研究一类平衡状态,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,一般性方法,：,有通行胜负规则,特殊性方法,：,无通行胜负规则,胜负规则,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,胜负规则,一般性方法,：,关键是动态规划或记忆化搜索的预处理,。,特殊性方法,：,着重于事先的思考，再将“决策规律”转化成程序。,实现方法,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,胜负规则,一般性方法,：,有通行规则可套用，应用面十分广泛；但是受“拓扑结构”限制，而且需考察所有状态，时空复杂度也有可能很高。,特殊性方法,：,不受“拓扑结构”限制，无须考察所有状态，时空复杂度低，编程简单；但是无通行规则，思考难度大。,优点,缺点,实现方法,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,胜负规则,在“对策问题”中，一个状态要么是先手必胜，要么是先手必败！因此，在对局时，我方要做的就是占据必胜，把必败留给对方。,优点,缺点,实现方法,这正是解“对策问题”的核心思想！,核心思想,浅析解,“,对策问题,”,的两种思路,一般性方法,与,特殊性方法,思路方向,胜负规则,优点,缺点,实现方法,“,一般性方法,”,从统一的角度，考察所有状态，来决定对局策略。,“,特殊性方法,”,从特殊的角度，考察一类状态，来决定对局策略。,核心思想,延伸类比,一般性方法,特殊性方法,动态规划,贪,心,浅析解,“,对策问题,”,的两种思路,结,语,“对策论”是运筹学的一个重要分支。本文通过取石子问题，简单的阐述了解决一类“对策问题”的两种思路，也是我的一点心得，但并不能涵盖万一。,文中介绍的“,一般性方法,”与“,特殊性方法,”既是方法，也是思路，更是一种思想。在解其他类型的题目时，也同样可以应用这两种思考方法。,浅析解,“,对策问题,”,的两种思路,结,语,“纸上得来终觉浅，绝知此事要躬行。”,我们还需要不断努力，不断实践，不断探索。只有实践多了，方能：,1,充分运用正向与逆向的思维,1,从各个角度观察问题,1从一般到特殊，从特殊到一般,1,取长补短，采取合理的实现方法,浅析解,“,对策问题,”,的两种思路,结,语,运筹于帷幄之中,决胜于千里之外,