数学模型

数学模型与游戏2011年2月21日

数学模型

过河问题

过河问题是世界名题，有很多种说法。最早引进中国的 是中国数学会第一届理事，扬州中学的数学教师陈怀书 先生。后我国数学科普作家、哈军工大教授薛鸿达先生 曾写过一篇专文《渡河难题》,对此进行了全面介绍。 我们将介绍三种不同的形式。

数学模型

例1 商人们怎样安全过河问题(智力游戏) 随从们密约, 在河的任 一岸, 一旦随从的人数 比商人多, 就杀人越货. 乘船渡河的方案由商人决定. 商人们怎样才能安全过河? 问题分析 多步决策过程

河

小船(至多2人) 3名商人 3名随从

决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员 要求~在安全的前提下(两岸的随从数不比商人多), 经有限步使全体人员过河.

数学模型

模型构成xk~第k次渡河前此岸的商人数yk~第k次渡河前此岸的随从数 sk=(xk , yk) ~过程的状态 xk, yk=0,1,2,3;

k=1,2,

S ~ 允许状态集合 S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}

uk~第k次渡船上的商人数vk~第k次渡船上的随从数 dk=(uk , vk) ~过程的决策 D={(u , v) u+v=1, 2} 状态因决策而改变

uk, vk=0, 1, 2;k=1,2, D ~允许决策集合 ~状态转移律

sk+1=sk +(-1)kdk

数学模型

模型构成

求dk D(k=1,2, n), 使sk S, 并按转移律 sk+1=sk+(-1)kdk 由 s1=(3,3)到达 sn+1=(0,0).

问题归结为由状态 (3,3)经奇数次可取运算，即 模型求解 由可取状态到可取状态的转移，转化为(0,0)的转 移问题。 y 穷举法 ~ 编程上机

图解法 状态s=(x,y) ~ 16个格点 允许状态 ~ 10个 点 允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移. d1, d11给出安全渡河方案

3 2 1 d11 0 1 2

s1d1

sn+1

3

x

数学模型

商人们怎样安全过河智力游戏 多步决策过程(数学模型)

规格化方法 便于求解 (计算机编程等) 易于推广: 商人和随从人数增加或小船容量加大; 考虑4名商人各带一随从的情况.

多步决策模型: 恰当地设置状态和决策, 确定状态 转移律及目标(目标函数).

数学模型

例2. 人、狗、鸡、米过河问题这是一个人所共知而又十分简单的智力游戏。某人要带狗、 鸡、米过河，但小船除需要人划外，最多只能载一物过河， 而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。

在本问题中，可采取如下方法：一物在此岸时相应分量为1, 而在彼岸时则取 为0,例如(1,0,1,0)表示人和鸡在此岸， 而狗和米则在对岸。

数学模型

(i)可取状态：根据题意，并非所有状态都是允许的，例如 (0,1,1,0)就是一个不可取的状态。本题中可取状态(即系 统允许的状态)可以用穷举法列出来，它们是： 人在此岸 人在对岸 (1,1,1,1) (0,0,0,0) (1,1,1,0) (0,0,0,1) (1,1,0,1) (0,0,1,0) (1,0,1,1) (0

,1,0,0) (1,0,1,0) (0,1,0,1) 总共有十个可取状态，对一般情况，应找出状态为可取的充 要条件。 (ii)可取运算：状态转移需经状态运算来实现。在实际问题 中，摆一次渡即可改变现有状态。为此也引入一个四维向量 (转移向量),用它来反映摆渡情况。例如 (1,1,0,0) 表示人带狗摆渡过河。根据题意，允许使用的转移向量只能 有(1,0,0,0,)、(1,1,0,0)、(1,0,1,0)、 (1,0,0,1)四个。

数学模型

规定一个状态向量与转移向量之间的运算。规定状态向量与 转移向量之和为一新的状态向量，其运算为对应分量相加， 且规定0+0=0,1+0=0+1=1,1+1=0。 (解释) 在具体转移时，只考虑由可取状态到可取状态的转移。问题 化为： 由初始状态(1,1,1,1)出发，经奇数次上述运算转化为 (0,0,0,0)的转移过程。 我们可以如下进行分析 (第一次渡河):

(1,1,0,0) (0,0,1,1) (1,0,1,0) (0,1,0,1) (1,1,1,1) (1,0,0,1) (0,1,1,0) (1,0,0,0) (0,1,1,1)

(不可取) (可取) (不可取) (不可取)

数学模型

(第二次渡河) (1,1,0,0) (1,1,1,1) (1,0,1,0) = (0,1,0,1) (1,0,0,1) (1,1,0,0) (1,1,0,1) (1,0,0,0)

(1,0,0,1)

(不可取) (循环,回到原先出现 过 (不可取) (可取)

以下可继续进行下去，直至转移目的实现。上述分析实际 上采用的是穷举法，对于规模较大的问题是不宜采用的。

数学模型

图解法

问题转化为求点(1,1,1,1)到点(0,0,0,0)的一条通路。

人在此岸 (1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)0,0,0,1 1,1,1,1 0,1,0,1 1,1,0,1 0,1,0,0 1,1,1,0 1,0,1,1

人在对岸 (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)

0,0,1,0

1,0,1,0

0,0,0,0

数学模型

例3:高塔逃生：铁匠海乔90,公主安娜50,侍女40,铁 链30 原则： 人下来时两个筐子必须都有人或铁链，并且重量相差 10公斤。 注意不同于过河 问题，此过程是 两个筐子装的总重量不超过170公斤。不可逆的。共有 八种不同的方案， 转化：用向量表示状态:如(9,5,4,3)表示四者均在上面， 可试着做一下。 (9,4)表示海乔和侍女在上面，其余在下面。从(9,5,4,3)开

始，到(3)结束。 方案之一：开始 铁链下去 侍女下去铁链上来 铁链拿到筐外 公主在下面 可把铁链拿到筐里

(9,5,4,3) →(9,5,4) →(9,5,3) → (9,5)→(9,4)→(5,4,3) →(5,4) →(5,3) →(5)→(4)→(3)。

数学模型

Dü rer魔方(或幻方)问题

德国著名的艺术家Albrecht Dü rer(1471-1521) 于1514年曾铸造了一枚名为“Melencotia I”的铜 币。令人奇怪的是在这枚铜币的画面上充满了数 学符号、数字及几何图形。这里，我们仅研究铜 币右上角

的数字问题

数学模型

什么是Dü rer魔方所谓的魔方是指由1~n2这n2个正整 数按一定规则排列成的一个n行n列 的正方形 。n称为此魔方的阶 。多么奇妙的 Dü rer魔方：4阶，每一行之和为 魔方！ 34,每一列之和为34,对角线 (或反对角线)之和是34,每个 小方块中的数字之和是34,四个 角上的数字加起来也是34 铜币铸造时间：1514年

数学模型

构造魔方是一个古老的数学游戏，起初它 还和神灵联系在一起，带有深厚的迷信色彩。 传说三千二百多年前(公元前2200年),因治 水出名皇帝大禹就构造了三阶魔方(被人们称 “洛书”),至今还有人把它当作符咒用于某 些迷信活动，大约在十五世纪时，魔方传到了 西方，著名的科尼利厄斯· 阿格里帕(1486-1535) 先后构造出了3~9阶的魔方 。

数学模型

如何构造魔方奇数(不妨n=5)阶的情况 Step1: 在第一行中间写1 Step2: 每次向右上方移一格依次填按由小到大排列的下 一个数，向上移出界时填下一列最后一行的小方格；向 右移出界时填第一列上一行的小方格。若下面想填的格 你想构造Durer魔方吗？ 已填过数或已达到魔方的右上角时，改填刚才填的格子 如何构成所有的Durer魔方？Durer魔方有多少？ 正下方的小方格，继续Step2直到填完 偶数阶的情况 偶数阶的魔方可以利用奇数 阶魔方拼接而成，拉尔夫· 斯特雷 奇给出了一种拼接的方法 ，这里 不作详细介绍 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9

数学模型

同阶魔方的个数三阶 四阶 五阶 1个 880个 反射和中心旋转生成8个 反射和中心旋转生成7040个

没人知道有多少个！!! 魔方数量随阶数n增长 的速度实在是太惊人了！

数学模型

仍以4阶方阵为例 定义：如果4×4数字方，它的每一行、每一列、每一对 角线及每个小方块上的数字之和都为一确定的数，则称

这个数字方为 Durer魔方。

R=C=D=S

其中：R为行和，C为列和，D为对角线和，S为小方块和

设D为所有满足R=C=D=S的Durer魔方的集合。10 80 100 150 40 0 9 15 1 6 1 18 0 7 1 允许取相同的数字， 18 并且允许数字在某 9 10 7 0 10 6 0 个数域里任意取值。 0 9 1 16 0 9 1 9 9 6 1 9 9 7

140 110 50 70 20

160 90 60

120 130 30

数学模型

a11 a12 a13 a14

b11 b12 b13 b14

A=

a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44

B=

b21 b22 b23 b24 b31 b32 b33 b34 b41 b42 b43 b44

类似于矩阵的加法和数乘，定义魔方的加法和数乘。易验证，D 对加法和数乘封闭，且构成一线性空间。 记 M ={所有的4×4数字方} ,则其维数为16。 而D是M的子空间，则D是有限维的线性空间。 根据线性空间的性质，如果能得到D的一组基， 则任一个Durer方均可由这组基线性表示。

数学模型

Durer魔方的维数和生成集R=C=D=S=1的方阵构成的线性空间具有什么样

的性质？ (这是非常必要的，因为我们一般取的是整数。)类似于构造n维欧氏空间 1在第一行中共有4种取法，为保持上述 的标准基，利用0和1我们 性质的成立，第二行中的1还有两种取法。当 来构造一些R=C=D=S=1 第二行的1也取定后，第三行与第四行的1就完 的最简单的方阵。 全定位了，故一共可作出8个不同的最简方阵， 称之为基本魔方并记之为Q1,… ,Q8

数学模型

由 0,1 数字组合，构造所有的R=C=D=S=1的魔方。 共有8 个，记为Qi, i=1,2,…,8。1 00

01

00

1

00

00

01

Q1=

0

00 0

01 0 0 0 1

00 0 0 1 0

10 1 0 0 0

Q2=

0

00 0

10 0 1 0 0

01 0 0 0 1

00 1 0 0 0

Q3=

1 0 0

Q4= 01 0