“过河”问题的解法
-
“过河”问题的解法
陕西省西安市长安区第二中学
杨西武
【关键词】
迪克斯特拉算法，图论，最短路径
【内容提要】
信息学奥林匹克竞赛，
各类资料中都涉及“过河”一题，但
都没有给出详解及程序。历届考题也没有涉及到，原
因是其测试
数据不便给出多组。但此题对考察学生的分析能力和解题能力却
很有帮助。本文旨在给出其详解。
【问题描述】
某人
< br>m
带一只羊
s
，一只狼
w
和一筐白菜
v
过河。
没有船，他
每次游过河时只能带一件东西，当没有人管理时，狼和羊不能相
处，羊和白菜不能相处。在这些条件的约束下，他怎样才能将三
件东西从左岸
带往右岸？试编程给出一组过河次数最少的方案。
【问题分析】
用无向图描述上述问题的解法路径
用结点代表状态
例如：
初始状态
v1
可记为
m
,
s
,
w
,
v
,
< br>（即，
人、
羊、
狼、
白菜皆在左岸，右岸为空，这是一种安全状态，即满足约束条件
的状态）<
/p>
。最终状态
v10
可记为
,
m
,
s
,
w
,
v
<
/p>
；
当人和羊过河后的状态可记为
w
,
v
,
m
,
s
（即，狼和白菜
在左岸，人和羊在右岸，这也是一种完全
状态）
。
可根据约束条件写出所有的安全状态：
即：①
m
,
s
,
w
,
v
,
②
w
< br>,
v
,
m
,
s
③
m
,
w
,
v
,
s
< br>
④
m
,
s
,
v
,
w
⑤
m
,
s
,
w
< br>,
v
⑥
m
,
s
,
w
,
v
⑦
s
< br>
,
m
,
w
,
v
⑧
w
,
m
,
s
,
v
< br>
⑨
v
,
m
,
s
,
w
⑩
,
m
,
s
,
< br>w
,
v
将
这些安全状态分别用结点
v1v2
„„
v10
表示
若结点
< br>vi
经过一次过河可以到达结点
vj
，则可以认为
vi
和
vj
之间有一条边，于是可以得到如下无向图：
V
8
V
1
V
2
V
3
V
5
V
7
V
6
V
10
V
9
V
4
从
v1
到
v10<
/p>
的一条路径，即表示该题的一种解法
求过河次数最少的的方案也就是该图的一条最短路径
【算法】
①模拟题意，找出所有安全状态（见过程
starter
）
②模拟题意，找出各结点之间的关联，即建立图（见过程
create
）
③用迪克斯特拉算法，求出最短路径并打印。
【源代码】
program MWSV;
type
way=record
num:integer;
dist:integer;
next:0..16;
end;
boat=record
m,w,s,v:0..1;
end;
var b:array[1..16]of
boat; n:integer;