游戏中的数学模型

数学模型

数学模型与游戏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 …… 此处隐藏：2507字，全部文档内容请下载后查看。喜欢就下载吧 ……