过桥手电:枚举状态找最短时间

逻辑思维 · 建议年级 6

在规则完整的三人有限状态问题中比较所有有效转移并求最短总时间。

下载视频
展开视频文字稿
  1. 三人单独过桥要一、二、五分钟,手电必须随人,每次最多两人,同行用较慢者的时间。
  2. 先让一分和二分的人一起到对岸,手电也在对岸。这一步用较慢者的两分钟,累计两分。
  3. 还要接五分的人,所以一分的人带手电返回起岸,用一分钟,累计变成三分。
  4. 接着一分和五分的人一起过桥,用五分钟。现在三个人和手电都在对岸,累计八分。
  5. 把每一种允许的过桥办法都算一遍,没有哪一种少于八分钟;刚才的八分钟走法也符合全部规则。
  6. 最短时间是八分钟。每一步都要同时记录三个人和手电在哪一岸,方向不能画反。
讲解依据

逻辑思维

有限状态最短路,并用反向检查确认。

看一个例子

三人单独过桥需1、2、5分钟;开始都与手电在同岸。每次最多2人、也允许1人,手电必须随人,两人同行耗较慢者时间。全员到对岸最少多久?

8分钟:1和2过桥2分,1返回1分,1和5过桥5分。把每种允许的过桥办法逐一比较,没有比8分钟更快的;这条路径也符合手电必须随人的规则。

马上试一题

所给1、2、5分钟三人方案总时间是多少?