擺渡問題

擺渡問題

擺渡問題(ferry problem)是一類組合最佳化問題,在一條河的一邊岸上有一隻狼、一隻羊和一棵白菜,已知狼吃羊和羊吃白菜,在河中只有一條小舟且每次只能載它們三者之一,問如何用最少的次數將它們安全擺渡到對岸?這就是所謂擺渡問題,也可將它推廣到一般的情形。

基本介紹

  • 中文名:擺渡問題
  • 外文名:ferry problem
  • 所屬學科:數學
  • 所屬問題:組合學(組合多最最佳化)
  • 簡介:一類組合最佳化問題
基本介紹,擺渡問題的推廣與變形,

基本介紹

中世紀,英國數學家阿爾昆(Alcuin,735-804)在其《益智集》(Problems for the Quickening of the Mind)中提出:有人攜帶一隻狼、一隻羊、一籃白菜渡河。唯一的工具是一條小船。小船一次只能載他自己和三樣東兩中的一樣。如果只留下羊和白菜在一起,羊就會吃掉白菜;如果留下羊和狼在一起,狼就會吃掉羊。問這個人如何安排擺渡,方能使白菜、羊和狼都平安抵達對岸?
可以利用路徑的概念解此問題。
:河左岸允許出現的情況有以下10種情況:人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及窄(各物品已安全渡河)。把這10種狀態視為10個點,若一種狀態通過一次擺渡後變為另一種狀態,則在兩種狀態(點)之間畫一直線,得到圖1。
擺渡問題
圖1
這樣擺渡問題就轉化成在圖中找出以“人狼羊菜”為起點,以“空”為終點的簡單路徑。容易看出,只有兩條簡單路徑符合要求,即
(1)人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空:
(2)人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。
對於簡單路徑(1)的安排為:人帶羊過河;人剛來;帶狼過河;放下狼再將羊帶回;人再帶菜過河;人回來;帶羊過河。
對於簡單路徑(2)的安排為:人帶羊過河;人回來;帶菜過河;放下菜再將羊帶回;人再帶狼過河;人回來;帶羊過河。
上述的兩種方案都是去4次、回3次,且不會再有比這更少次數的渡河辦法了。

擺渡問題的推廣與變形

16世紀,義大利數學家塔塔格里亞(N.Tartaglia,1499-1557)將擺渡問題設計成一個新版本:
三位美麗的新娘和她們愛吃醋的先生一同旅行。他們來到了一條河邊,但只有一條小船,小船一次至多只能載二人。為了避免有人吃醋,他們約定:除非自己的先生在身旁,否則任一女士不得和其他男子在一起。問怎樣安排渡河?
答案是往返1 1次。如果只有兩對夫婦,則往返5次就夠了;如果有四對或更多對夫婦,那么問題無解。該問題後來又被推廣成:
(1)n對夫妻用一條船過河,該船僅可由一人來劃,至多可載
個人,條件仍是任一女士除非自己的先生在身旁,否則不得和其他男子在一起。問至少需要往返幾次?(設擺渡次數為y,則
時,
時,
時,
。)
(2)問一條船至少能載幾個(X)人時,才能使11對夫妻可乘它渡河,而任一女士除非自己的先生在身邊,否則不得和別的男子在一起;假設船僅可由一人來劃。並求往返擺渡的最小次數(y)。結果見表1。
表1 擺渡問題的解
n
x
y
2
2
5
3
2
11
4
3
9
5
3
11
》5
4
2n-1
與擺渡問題相類似的是火車轉軌問題。圖2中有一火車頭L和兩節貨車車廂
,DA是
所在側線的公共部分,長度足夠停放
,但不能同時容下這兩節車廂,也容小下火車頭L。這樣,停在DA上的車廂可以轉軌到側線上。工程師的工作是轉換
的位置。問如何完成?這個問題並不難,但如果有更多的車廂(如在鐵路貨物分類站),要按車廂目的地先後順序進行排列,那么__:I二程師就需要有很高的數學水平才能完成職責了。

相關詞條

熱門詞條

聯絡我們