過橋手電:枚舉狀態找最短時間

邏輯思維 · 建議年級 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分鐘三人方案總時間是多少?