数学建模状态转移法PPT学习教案

1、会计学1 数学建模状态转移法数学建模状态转移法 (2) 可取运算可取运算. 状态转移需经状态运算来实现状态转移需经状态运算来实现. 在实际问题中在实际问题中, 摆一次摆一次 渡可改变现有的状态渡可改变现有的状态, 为此引进一个四维的状态运算向量为此引进一个四维的状态运算向量, 用它来反用它来反 映摆渡操作情况映摆渡操作情况. 根据题意根据题意, 状态运算向量集合为状态运算向量集合为: D D = ( 1, 0, 1, 0 ) , ( 1, 1, 0, 0 ) , ( 1, 0, 0, 1 ) , ( 1, 0, 0, 0 ) . 把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量把每一次

2、摆渡运作看成为一个可取状态向量和一个状态运算向量 的向量相加或相减的向量相加或相减 (去往对岸为相减，返回此岸为相加）去往对岸为相减，返回此岸为相加）. 在以上所规定的意义下在以上所规定的意义下, 这个问题的状态转移模型可表示为这个问题的状态转移模型可表示为: s i+1 = s i + (-1) i d k , 其中其中 s i S S , d k D D ; ; 且对任意且对任意 j i , 都有都有 s j s i 令令 s1 = ( 1, 1, 1, 1 ) , sn = ( 0, 0, 0, 0 ) , 利用计算机编程处理利用计算机编程处理, 例如，例如， 可以用可以用 Math 软

3、件编程求解这个摆渡操作方案软件编程求解这个摆渡操作方案 , 即求出即求出 n 和和 d1 , d2 , d3 , , dn 各是多少各是多少. 第1页/共11页 具体的结果为：具体的结果为： （ 1，1，1，1 ） )0 , 1 , 0 , 1( )0, 0, 0, 1( )0 , 0 , 1 , 1( )0 , 1 , 0 , 1( )1 , 0, 0, 1( )0,0,0, 1( )0 , 1 , 0 , 1( （ 0，1，0，1 ）( 1，1，0，1 ） （ 0，0，0，1 ）（ 1，0，1，1 ） （ 0，0，1，0 ） （ 1，0，1，0 ） （ 0，0，0，0 ） 。 或者为：或者

4、为： （ 1，1，1，1 ） )0 , 1 , 0 , 1( （ 0，1，0，1 ） )0, 0, 0, 1( （ 1，1，0，1 ） )1 , 0 , 0 , 1( （ 0，1，0，0 ） )0 , 1 , 0 , 1( （ 1，1，1，0 ） )0 , 0 , 1 , 1( （ 0，0，1，0 ） )0 , 0 , 0 , 1( （ 1，0，1，0 ） )0 , 1 , 0 , 1( （ 0，0，0，0 ）。）。 第2页/共11页 问题问题 2 . 商人过河问题商人过河问题 三名商人各带一名仆人过河三名商人各带一名仆人过河, 渡船最多载渡船最多载 2 人人. 在任何一岸在任何一岸, 仆人数

5、不允许大于商人数仆人数不允许大于商人数, 否则仆人就要杀人越货否则仆人就要杀人越货. 请制定一个安全渡河的操作方案请制定一个安全渡河的操作方案. 求解求解. 用一个二维向量来表示此岸的商人数、仆人数的具体状态用一个二维向量来表示此岸的商人数、仆人数的具体状态. 例如例如: ( 3, 3 ) 表示此岸有三个商人表示此岸有三个商人, 三个仆人三个仆人 ; ( 0, 2 ) 表示此岸表示此岸 无商人无商人 , 两个仆人两个仆人 ; 等等等等 . 状态运算向量集合状态运算向量集合 为为: D D = ( 0, 1 ) , ( 0 , 2 ) , ( 1, 1 ) , ( 1, 0 ) , ( 2, 0

6、 ) . 把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量 的向量相加或相减的向量相加或相减 （去往对岸为相减，返回此岸为相加）（去往对岸为相减，返回此岸为相加）. 允许状态向量集合允许状态向量集合 为为: S = ( 3, 3 ) , ( 3, 2 ) , ( 3, 1 ) , ( 3, 0 ) , ( 2, 2 ) , ( 1, 1 ) , ( 0, 3 ) ,( 0, 2 ) , ( 0, 1 ) ， ( 0, 0 ) 第3页/共11页 和上一问题一样和上一问题一样, 可以用可以用 Mathematica 软件编程求解软件编

7、程求解. 具体的结果为（具体的结果为（ 4 种方案）：种方案）： 方案方案 1： （ 3，3 ） )2, 0( （ 3，1 ） )1 , 0( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 , 2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 , 2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )1 , 0( （ 0，2 ） )2, 0( （ 0，0 ） 。 在以上所规定的意义下在以上所规定的意义下, 这个问题的状态转移模型可表示为这个问题的状态转移模型可表示为: s i+1 = s i + (-1) i d

8、k , 其中其中 s i S S , d k D D ; ; 且对任意且对任意 j i , 都有都有 s j s i . . 方案方案 2： （ 3，3 ） )2, 0( （ 3，1 ） )1 , 0( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )0 , 1( （ 1，1 ） )1 , 1( （ 0，0 ） 。 第4页/共11页 方案方案 3： （ 3，3 ） )1 , 1( （ 2，2 ） )0 , 1(

9、 （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )1 , 0( （ 0，2 ） )2, 0( （ 0，0 ） 。 方案方案 4： （ 3，3 ） )1 , 1( （ 2，2 ） )0 , 1( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （

10、0，1 ） )0 , 1( （ 1，1 ） )1 , 1( （ 0，0 ） 。 本题还可以用作图方法来求解，具体做法可参考教科书第本题还可以用作图方法来求解，具体做法可参考教科书第11页页. 以上两个例子本身并无多大实际意义以上两个例子本身并无多大实际意义, 但它们展示了如何将实际问但它们展示了如何将实际问 题转化为题转化为 状态转移状态转移 问题问题, 并用并用 状态转移法状态转移法 来求解问题的过程和来求解问题的过程和 思考方法思考方法. 习题习题. 在与问题在与问题2同样的假定下同样的假定下, 试求解四对商人过河问题。试求解四对商人过河问题。 如果渡船最多可载如果渡船最多可载 3 人，试

11、求解五对商人和六对商人过河问题。人，试求解五对商人和六对商人过河问题。 如果渡船最多可载如果渡船最多可载 4 人，试求解任意对商人过河问题。人，试求解任意对商人过河问题。 第5页/共11页 问题问题 3. 取石游戏问题取石游戏问题 三堆石子三堆石子, 各堆数目任意各堆数目任意. 两人轮流取走石子两人轮流取走石子, 规定只准在一堆中规定只准在一堆中 至少取走一颗至少取走一颗, 至于是哪一堆可任意选定至于是哪一堆可任意选定. 谁取到最后的一颗石子谁取到最后的一颗石子 为输为输, 请制定一个取胜策略请制定一个取胜策略. 建模思想建模思想 : 利用利用二进制二进制 及及 “与与 ”、“非非 ” 运算来

12、模拟状态及其转运算来模拟状态及其转 移过程移过程. 建立状态转移模型建立状态转移模型: 设在操作中某一状态的三堆石子数分别为设在操作中某一状态的三堆石子数分别为 n1 , n2 , n3 . 将它们化将它们化 为二进制数为二进制数 : 其中其中 a1 , b1 , c1 不都为零不都为零. . n1( a1 a2 an ) , n2( b1 b2 bn ) ,n3( c1 c2 cn ) , 令令: N = ( a1 a2 an ) + ( b1 b2 bn ) + ( c1 c2 cn ) , 称它为称它为 状态状态 n1 , n2 , n3 的的 状态指标数状态指标数 . 这里三个二进制数

13、各对应数位这里三个二进制数各对应数位 上的数字相加法则规定为上的数字相加法则规定为 “与与 ” 、“或或 ” 运算运算: 1 + 1 = 0 , 1 + 0 = 1 , 0 + 1 = 1 , 0 + 0 = 0 . 第6页/共11页 若若 N = 0 , 则称状态则称状态 n1 , n2 , n3 为为 必必 输状态输状态 , 简称为简称为 L状态状态 ( Lost ) . 若若 N 0 , 则称状态则称状态 n1 , n2 , n3 为为 必赢状态必赢状态, 简称为简称为 W状态状态 ( Win ) . 显然任显然任 何一种状态要末是何一种状态要末是 L状态状态 , 要末是要末是 W状态状

14、态 , 亦即两者必居其一亦即两者必居其一. 设对某一设对某一 L状态状态 n1 , n2 , n3 ( N = 0 ) 进行一次取石操作进行一次取石操作, 无妨设无妨设 n1 n1 , 相应的二进制数相应的二进制数 ( a1 a2 an ) ( a1 a2 a n ) . L状态状态 n1 , n2 , n3 状态状态 n1 , n2 , n3 ; 相应地相应地 , N = 0 N . 若若 a1 a1 , 则则 a1 = 1 - - a1 . 因因 a1 + b1 + c1 = 0 a1 + b1 + c1 = 1 N 0 . 若若 a1 = a1, 则考察则考察 a2 与与 a2 , 如果

15、如果 a2 a2 , 同理可得同理可得 N 0 , 否则否则 继续考察下去继续考察下去. 因为必存在某个下标号因为必存在某个下标号 k ,使使ak ak , 故必有故必有 N 0 , 这说明一个这说明一个 L状态状态 , 任意进行一次取石操作任意进行一次取石操作, 都会变成一个都会变成一个 W状态状态 . 模型的理论分析模型的理论分析: (1) 一个一个 L 状态状态 , 任意进行一次取石操作任意进行一次取石操作 , 都会都会 变成一个变成一个 W 状态状态 . 第7页/共11页 (2) 对于任一个对于任一个 W 状态状态 , 总存在着某一个取石操作总存在着某一个取石操作 , 使它变成使它变成

16、 一个一个 L 状态状态 . 假定一个假定一个 W 状态为状态为: n1 , n2 , n3 ( N 0 ) . 记与三个十进制数记与三个十进制数 n1 , n2 , n3 相对应的二进制数分别为相对应的二进制数分别为 : ( a1 a2 an ) , ( b1 b2 bn ) , ( c1 c2 cn ) . 以下三种情况必有一种是成立的以下三种情况必有一种是成立的: i) ( a1 a2 an ) ( (b1 + c1)(b2 + c2)(bn + cn) ) ; ii) ( b1 b2 bn ) ( (a1 + c1)(a2 + c2)(an + cn) ) ; iii) ( c1 c2

17、 cn ) ( (a1 + b1)(a2 + b2)(an + bn) ) . 无妨设第无妨设第 i) 种情况成立种情况成立 . 这说明这说明 , 二进制数二进制数 ( a1 a2 an ) 所对应的十进制数所对应的十进制数 n1 与与 二进制数二进制数 ( (b1 + c1)(b2 + c2)(bn + cn) ) 所对应的十进制数所对应的十进制数 n 有关系有关系 : n1 n . 由此由此 , 只须在第一堆中取走只须在第一堆中取走 (n1 - - n ) 颗石子颗石子, W状态状态 n1 , n2 , n3 变化而成一个新状态变化而成一个新状态 n , n2 , n3 , 这个状态的这个

18、状态的 状态指标数状态指标数 N = 0 . 这说明这说明: 对于任一个对于任一个 W 状态状态, 总存在着某一个取石操作总存在着某一个取石操作, 使它变成一个使它变成一个 L 状态状态 . 第8页/共11页 制定取胜策略制定取胜策略 : 选取某堆选取某堆 , 从中取走适量石子从中取走适量石子 , 使这三堆构成使这三堆构成 L状态状态. 备注备注：（：（1） N = 0 时未必有时未必有 n1 + n2 = n3 ，例如：，例如： n1 = 15 0 1 1 1 1 ， n2 = 21 1 0 1 0 1 ， n3 = 26 1 1 0 1 0 ， 显然显然 n1 + n2 n3 , 但此时，但此时，N = 0 0 0 0 0 = 0 ； n1 = 3 0 0 0 0 0 1 1 ， n2 = 69 1 0 0 0 1 0 1 ， n3 = 70 1 0 0 0 1 1 0 ， 显然又有显然又有 n1 + n2 n3 , 但此时但此时 ，N = 0 0 0 0 0 = 0 ； 又例如：又例如： （2） n1 + n2 = n3 时未必有时未必有 N = 0 ，例如：，例如： n1 = 15 0 0 1 1 1 1 ， n2 = 21 0 1 0 1 0 1 ， n3 = 36 1 0 0 1 0 0 ， 显然显然 n1