图的方法建模.pdf

第5章图的方法建模(2课时)

教学目的
掌握用图的方法建模解决实际问题的基本方法
教学内容
用图的方法建模的三个实例
图是由平面上的一些点及这些点之间的连线（边）构成的。用点表示要研究的离散
对象，用边表示对象之间的关系来建立模型，并且用图的性质和算法求解模型，是研究离
散问题的重要手段。
实例一握手的次数
史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都
要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两
次。
之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。
那么，史密斯太太和别人握了几次手呢?
这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果对此建立一个
图模型，问题就变得很简单了。
分析：从题目我们得到了哪些信息?
史密斯和太太邀请四对夫妻参加晚会——房间里共有10人
每个人都不会与自己的配偶握手——握手的两个人不是配偶
每个人都不会跟同一个人握手两次——两个人间的握手最多是一次
史密斯先生问每个人和别人握了几次手，他们的答案都不一样——除史密斯先生外，
每个人和别人握手的次数都不一样。
——除史密斯先生外，每个人握手的次数最多是8次，最少为0次。
——房间里除了史密斯先生外的9个人，他们与别人握手的次数分别为0，1，2，3，

4，5，6，7，8次。
要知道史密斯太太和别人握手的次数，只需确定除史密斯先生外的9人中哪一个是
史密斯太太即可。
根据以上信息，建立图模型

由图可知：
8号的配偶是0号；
7号的配偶是1号；
6号的配偶是2号；
5号的配偶是3号；
史密斯太太是4号，所以史密斯太太和别人握了4次手。
实例二安全渡河问题
三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从
们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大
权掌握在商人们手中。商人们怎样才能安全渡河呢?
对于这类智力游戏经过一番逻辑思索是可以找出解决办法的。我们这里主要是考虑
用数学模型求解，因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推
广。
安全渡河问题可以视为一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸
驶回此岸，都要对船上的人员(商人、随从名几人)作出决策，在保证安全的前提下(两岸
的随从数都不比商人数多)，在有限步内使全部人员过河。
用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出
状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每
一步的决策，达到渡河目标。
模型构成

记第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,"，xykk,0,1,2,=3。将二

维向量sxkkk=(,y)定义为状态。安全渡河条件下的状态集合称为允许状态集合，记作S。

Sxyxyxyxy======{(,)|0,0,1,2,3;3,0,1,2,3;1=}(1)
不难验证，S对此岸和彼岸都是安全的。

记第k次渡船上的商人数为uk，随从数vk。将二维向量duvkkk=(,)定义为决策。允

许决策集合记作D，由小船的容量可知

Duvuvuv=≤+≤={(,)|12,,0,1,2}(2)

因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶回此岸，所以状态sk随

决策dk变化的规律是

k
sskk+1=+−(1)dk(3)

(3)式称为状态转移律。这样，制订安全渡过河方案归结为如下的多步决策模型:

求决策dDk∈(1,2,,k="n)，使状态sSk∈按照转移律(3)，由初始状态s1=(3,3)经

过有限步n到达状态sn+1=(0,0)。

模型求解
可根据(1)——（3）式编程利用计算机求解上述决策问题。
对于商人和随从人数不大的简单状况，用图解法解这个模型更为方便。

在Oxy平面坐标系上画出如图的方格，方格点表示状态sxy=(,)。允许状态集合S是

用圆点标出的10个格子点。允许决策dk是沿方格线移动1或2格，k为奇数时向左、下

方移动，k为偶数时向右、上方移动。要确定一系列的dk，使由s1=(3,3)经过那些圆点最

终移到原点O(0,0)。

实例三渡河问题
某人带狗、羊、以及蔬菜渡河，一小船除需人划外，每次只能载一物过河。而人不
在场时，狗要吃羊，羊要吃菜，问此人应如何过河？
模型构成
此问题可化为状态转移问题，用四维向量（人，狗，羊，菜）来表示状态，当一物
在此岸时相应分量取1，而在彼岸时则取0。
（1）可取状态
人在此岸

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

人在彼岸

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