問怎樣才能把狼,羊,白菜都安全過河?

作者：由小糊塗發表于書法時間：2020-12-08

劉醉白2020-12-08 23:07:20

嗯，可以想想答案每一步是為什麼，核心就是在人不在的時候不能讓狼和羊、羊和菜在一起，所以在人不在的時候只能讓狼和菜在一起，而且此題步驟最少的運法不唯一。

下面我給一個圖論的解法：

河邊一共只有十種狀態是可以存在的，分別是人狼羊菜、人羊菜、人狼菜、人狼羊、狼菜、人羊、狼、羊、菜、空。

以每種狀態作為一個頂點，狀態之間如果可以轉化，那麼這兩個狀態對應的頂點之間連一條邊

，那麼此題對應的圖如下：

此題

步驟最少的運法

就是

從“人狼羊菜”這個頂點到“空”這個頂點的一條最短路徑

。一般地，求給定的兩點之間的最短路徑可以使用Dijkstra演算法。

此題的兩個解是：

其中第一個解就對應你給的解：人先把羊帶過去，然後回來接狼過河，過去之後再把羊帶回來，回來過後把羊放下，再把白菜帶過去，然後回來接羊。

第二個解對應的是：人先把羊帶過去，然後回來把白菜帶過去，過去之後再把羊帶回來，回來過後把羊放下，然後接狼過河，然後回來接羊。

真摯少年2020-12-10 13:50:08

概述

這個問題可以使用數學中的「集合」與「對映」的知識來形式化，下面我們首先給出幾個定義，然後給出計算過程，最後講解原理．

定義１（演化鏈）：每個元素皆來自自然數的一個有限長的定序元組稱為一個演化鏈．

例１：

是一個演化鏈，也可寫為

$2 \to 1 \to 3 \to 1 \to 3 \to 2 \to 4$

．

定義２（全集）：包含了當前討論問題所在宇宙的所有登場角色的集合

$A = \{ \mathrm{sheep}, \mathrm{wolf}, \mathrm{vegetable}, \mathrm{human} \}$

．

定義３（狀態）：

的一個子集稱為是一個狀態．

定義４（狀態集）：

的所有子集組成的集合，記做

．

定義４（演化）：一個定序二元組

，其中

$S_1, S_2 \in S(A)$

．有時候我們把它記為

$S_1 \to S_2$

．

定義５（演化路徑）：

$\mathbb{N}^\star$

的一個非空有限子集到

的一個對映稱為是一個演化路徑．

例２：下面給出一條演化路徑（它未必是合法的）

$\begin{align} f(1) &= \{ \mathrm{sheep}, \mathrm{human} \} \\ f(2) &= \{ \mathrm{sheep} \} \\ f(3) &= \{ \mathrm{human}, \mathrm{sheep} \} \end{align}$

該條演化路徑亦可記為：

$\{ \mathrm{sheep}, \mathrm{human} \} \to \{ \mathrm{sheep} \} \to \{ \mathrm{human}, \mathrm{sheep}, \mathrm{vegetable} \}$

下面我們開始計算，使用Mathematica軟體，得益於它強大有力的符號計算功能，計算過程其實非常簡單，我們只要把規則用Wolfram語言表達出來，軟體可以自動「找出」我們想要的答案．

計算方法

Mathematica軟體的符號計算功能可以很好地應付這個問題．

我們主要是考慮河對岸的情況，我們考慮河對岸的生物的個數的演化（迭代），也就是說，我們考慮的是，在每一個週期中，河對岸的「狀態」，事實上，當我們知道了河對岸在每一個週期的狀態，我們就能反推出狀態的變化，從而就得到了具體的運輸操作方法．

一個狀態是全集（全體角色集）

的一個有限子集，對一個有限子集我們可以數它有多少個元素，我們可以首先確定，各個週期下的狀態都是幾元的．

首先我們知道最開始，河對岸肯定什麼都沒有，所以最開始的狀態是

$\{ \}$

，也就是

$\emptyset$

，也就是

元的．我們記最開始的週期序數為

，也就是說第

個週期就是最開始．那麼第

個週期呢，就表示獵人第一次到達河對岸，此時河對岸有獵人，以及和獵人同乘船隻的蔬菜/狼/羊（只能是其中一個），所以此時河對岸的狀態是

元的，然後獵人會回來，它應該空手回來，要不然就出現了迴圈（我們會說迴圈是無意義的，因為這樣的演化路徑是不收斂的），所以我們知道，頭三個週期的演化鏈是這樣子的：

0 -> 2 -> 1

事實上，最終我們找出的有效的演化鏈它是這樣子的：

2 -> 1 -> 3 -> 1 -> 3 -> 2 -> 4

我這樣子解釋給大家聽：最開始河對岸有０個生物，然後有２個生物，然後有１個生物，然後有３個生物，然後有３個生物，然後有２個生物，最後有４個生物．容易驗證，存在符合這條演化鏈的合法的演化路徑．

需要確定的就是每一輪河對岸的生物具體有哪些，形式化地說，就是要知道，對於有限的

，所有可能的

元狀態又哪些：

我們構造一個全集，它包含全部角色：

allSet = {human， sheep， vegetable， wolf}；

然後我們排除那種不可能出現的情況：

inValid［set_List］：=

And［Not［MemberQ［set， human］］，

Or［SubsetQ［set， {wolf， sheep}］， SubsetQ［set， {vegetable， sheep}］］］；

解讀為：當人不在現場時，狼和羊同處或者羊和菜同處的不合理的，那麼合理的情況就是不合理的否：

valid［set_List］：=

And［Not［inValid［set］］， Not［inValid［Complement［allSet， set］］］］

注意到這裡我們還加了Complement，也就是河對岸和河這邊都要考慮，set表示河對岸，Complement［allSet， set］表示河這邊．

sets［n_Integer］：= Select［Subsets［allSet， {n}］， valid］；

這裡使用了一個函式生成所有可能的n元組，也就是n個生物共處時所有的可能，也就是所有的n元狀態：

容易驗證確實也是如此．

下面我們定義合理的一步演化：

validRule［rule_Rule］：= And［

Not［MemberQ［Intersection［Keys［rule］， Values［rule］］， human］］，

MemberQ［Union［Keys［rule］， Values［rule］］， human］，

Or［

SubsetQ［Keys［rule］， Values［rule］］，

SubsetQ［Values［rule］， Keys［rule］］

］

假如說數量增多了，那麼原先的必是現在的子集，假如說數量減少了，那麼現在的必是原先的子集，並且，人必須位於兩岸之一，是為了防止出現這種情況：

{ vegetable， wolf } -> { sheep， human }

表示河對岸先是有蔬菜和狼（這是人在河岸這邊），結果人從河岸這邊去到河對岸之後蔬菜和狼卻憑空消失了，顯然不可能．

evolve［n1_Integer， n2_Integer］：=

Select［Outer［Rule， sets［n1］， sets［n2］， 1］ // Flatten， validRule］；

這裡evolve表示從n1個生物到n2個生物所有可能的演化，我們來試一試：

基本也就如此，例如說 sheep -> human， sheep， vegetable 表示人把 vegetable 帶到對岸，這時對岸的生物組合就從 sheep 變成了 human， sheep， vegetable，其他請自行體會．

下面我們試圖把這些演化連線起來，連成一條合法的演化路徑：

beginWith

［

sets_List

，

rule_Rule

］

：=

Map

［

Values

，

Select

［

sets

，

ContainsExactly

［

Keys

［

］，

Values

［

rule

］］

connect

［

rule_Rule

，

values_List

］

：=

Map

［

rule

，

values

］

connects

［

rules1_List

，

rules2_List

；

Length

［

rules1

］

Length

［

rules2

］

：=

Map

［

connect

［

，

beginWith

［

rules2

，

］］

，

rules1

］

Flatten

chain

［

c_List

］

：=

Table

［

evolve

［

［［

］］，

［［

］］］，

{

，

Range

［

，

Length

［

］

］}］

接下來就是見證答案的時刻了：

答案解讀：在0 -> 2 -> 1 -> 3 -> 1 -> 3 -> 2 -> 4這條演化鏈上有兩種可能的（合法的或者說有效的）演化路徑：

演化路徑一：人先帶著羊到對岸，然後人空手回來，然後人再帶蔬菜到對岸，然後人和羊回來，然後人在帶狼到對岸，然後人空手回來，然後人再帶狼到對岸．

演化路徑二：人先帶著羊到對岸，然後人空手回來，然後人再帶著狼到對岸，然後人帶著羊回來，然後人再帶著蔬菜到對岸，然後人空手回來，然後人再帶著羊到對岸．

數學原理

給定全集

$A = \{ \mathrm{sheep}, \mathrm{wolf}, \mathrm{vegetable}, \mathrm{human} \}$

令

表示

的所有的非空子集組成的集合，我們用

類比河對岸的生物組合情況，形式化地，定義

$\begin{align} f : \mathbb{N}^\star &\longrightarrow S(A) \\ n &\longmapsto f(n) \end{align}$

令

表示迭代的輪數，則

稱為是一條演化路徑．

我們的目的是求出

$f(1), f(2), f(3), \cdots, f(N), n < \infty$

使得

滿足

，並且對任意

$1 \leq n \leq N$

，

都滿足：

１）當

$\mathrm{human} \not\in f(n)$

時，

$\{ \mathrm{sheep}, \mathrm{wolf} \} \not\subset f(n), \{ \mathrm{sheep}, \mathrm{vegetable} \} \not\subset f(n)$

．（動物互斥律，狼和羊在獵人不在時不能共存，羊和蔬菜在獵人不在時不能共存）

２）當

$\mathrm{human} \not\in A \setminus f(n)$

時，

$\{ \mathrm{sheep}, \mathrm{vegetable} \} \not\subset A \setminus f(n), \{ \mathrm{sheep}, \mathrm{wolf} \} \not\subset A \setminus f(n)$

．（對偶的動物互斥律，不僅要考慮河對岸的情況，還要考慮河岸這邊的情況）

３）如果

$\mathrm{human} \in f(n)$

，那麼必有

$\mathrm{human} \not\in f(n+1)$

，如果

$\mathrm{human} \not\in f(n)$

，那麼必有

$\mathrm{human} \in f(n+1)$

．（不可能在兩個相鄰的週期獵人都在對岸）

４）

$f(n) \subset f(n+1)$

或者

$f(n) \supset f(n+1)$

有且必有其一成立．（物質守恆，貨物必須經過運輸才出現在對岸/從對岸返回）

滿足上述約束的演化路徑

稱為是一條合法的演化路徑．

規定

為河對岸的初始狀態，我們求得：

$f(0) = \emptyset$

並且依上述Mathematica計算過程我們求得：

$\begin{align} f(1) &= \{ \mathrm{sheep}, \mathrm{human} \} \\ f(2) &= \{ \mathrm{sheep} \} \\ f(3) &= \{ \mathrm{human}, \mathrm{sheep}, \mathrm{vegetable} \} \\ f(4) &= \{ \mathrm{vegetable} \} \\ f(5) &= \{ \mathrm{human}, \mathrm{vegetable}, \mathrm{wolf} \} \\ f(6) &= \{ \mathrm{vegetable}, \mathrm{wolf} \} \\ f(7) &= \{ \mathrm{human}, \mathrm{sheep}, \mathrm{vegetable}, \mathrm{wolf} \} \end{align}$

另外一種演化路徑我就不寫了．根據每一個週期河對岸的狀態，我們容易反推出狀態的變化，也就是船隻的運載情況，也就是答案，上面我們已經解讀過了一次．

總結

沒有什麼特別的技巧，我們只不過是把所有的約束條件都用數學符號清晰又嚴格地表述出來，因為問題規模很小，所以我們也沒用什麼演算法，完全就是窮舉再篩選．這道題是一些數學建模教科書上的典型例題，據說還可以用

$0\text{-}1$

線性規劃的方法來解，有興趣的讀者不妨試試．據說也可以用動態規劃的方法來求解，假設在第

步河對岸已經集齊了人、蔬菜、羊和狼，我們可以考慮第

步時對岸是什麼情況，再考慮第

步時對岸是什麼情況，然後我們找到第

步到第

步的規律，就可以應用動態規劃方法了，有興趣的讀者不妨試試．

思考題

１。

試

用線性規劃的方法來求解該問題．

２。

試

用動態規劃的方法來求解該問題．

附錄

完整的Mathematica程式碼如下：

allSet

{

human

，

sheep

，

vegetable

，

wolf

}；

inValid

［

set_List

］

：=

And

［

Not

［

MemberQ

［

set

，

human

］］，

［

SubsetQ

［

set

，

{

wolf

，

sheep

}］，

SubsetQ

［

set

，

{

vegetable

，

sheep

}］

］

］；

valid

［

set_List

］

：=

And

［

Not

［

inValid

［

set

］］，

Not

［

inValid

［

Complement

［

allSet

，

set

］］］

］；

sets

［

n_Integer

］

：=

Select

［

Subsets

［

allSet

，

{

}］，

valid

］；

validRule

［

rule_Rule

］

：=

And

［

Not

［

MemberQ

［

Intersection

［

Keys

［

rule

］，

Values

［

rule

］］，

human

］］，

MemberQ

［

Union

［

Keys

［

rule

］，

Values

［

rule

］］，

human

］，

［

SubsetQ

［

Keys

［

rule

］，

Values

［

rule

］］，

SubsetQ

［

Values

［

rule

］，

Keys

［

rule

］］

］

］；

evolve

［

n1_Integer

，

n2_Integer

］

：=

Select

［

Outer

［

Rule

，

sets

［

］，

sets

［

］，

］

Flatten

，

validRule

］；

beginWith

［

sets_List

，

rule_Rule

］

：=

Map

［

Values

，

Select

［

sets

，

ContainsExactly

［

Keys

［

］，

Values

［

rule

］］

］

］；

connect

［

rule_Rule

，

values_List

］

：=

Map

［

rule

，

values

］；

connects

［

rules1_List

；

Length

［

rules1

］

，

rules2_List

；

Length

［

rules2

］

：=

Map

［

connect

［

，

beginWith

［

rules2

，

］］

，

rules1

］

Flatten

；

chain

［

c_List

］

：=

Table

［

evolve

［

［［

］］，

［［

］］］，

{

，

Range

［

，

Length

［

］

］}

］；

answers

Fold

［

connects

，

chain

［{

，

}］］；

［

Length

［

answers

］］；

［

answers

］；

可直接複製貼上執行．

曲直瀨道三2021-01-03 15:36:30

你自己都知道答案的事情，為什麼要提問？知乎不是貼吧，不要搞自問自答。

知乎使用者2021-02-12 07:50:51

其實就是小時候的趣味數學題裡的經典月經題：

難度應該是最簡單的，比倒油問題還簡單，其給人的震撼不及“一斤棉花和一斤鐵哪個重？”這個問題。這是最適合假日間堵住小孩子嘴的手段了，答出來了誇一下小孩子前途不可限量，答不出了可以堵住大部分嘰嘰喳喳。

C十十20年2021-09-26 07:57:05

程式參見《C++程式設計精要教程》。

標簽： rule 對岸演化 set list

上一篇:《城市的勝利》引言節譯

下一篇：這兩幅字寫的如何，哪幅更好呢？

問怎樣才能把狼,羊,白菜都安全過河?

猜你喜歡

02.線性組合張成空間和基

分數槽和整數槽繞組磁動勢的頻譜和繞組係數分析的Matlab程式

matlab三階矩陣如何畫三維曲面圖？程現結果如下，但菜鳥不會編碼，虛心求教？

HashSet的原理

古生物分類如何排除趨同演化？

問怎樣才能把狼,羊,白菜都安全過河?

猜你喜歡

02.線性組合 張成空間和基

分數槽和整數槽繞組磁動勢的頻譜和繞組係數分析的Matlab程式

matlab三階矩陣如何畫三維曲面圖？程現結果如下，但菜鳥不會編碼，虛心求教？

HashSet的原理

古生物分類如何排除趨同演化？

02.線性組合張成空間和基