習題 狀態(tài)轉移法人狼羊菜問題

1、2.2.1人、狼、羊、菜渡河問題,問題提出,一個擺渡人F希望用一條小船把一只狼W、一只羊G和一籃白菜C從一條河的左岸渡到右岸去，而船小只能容納F、W、G、C中的兩個，由于狼會吃羊，羊會吃白菜，在運送的過程中決不能在無人看守的情況下，留下狼和羊，羊和白菜在一起，應該如何渡河才能將狼、羊、白菜都運過河？,1,PPT學習交流,這是一個有趣的智力游戲問題，可以用推理的方法解決，但比較抽象，不易理解，如果建立數(shù)學模型，進行數(shù)學化把此問題化為狀態(tài)轉移問題來解決，顯得直觀且通俗易懂。,建立模型,將人、狼、羊、白菜在左岸的狀態(tài)依次用一個四維向量表示，設一物在左岸時記相應的分量為1，否則記為0，如A（1，0，1

2、，0）表示人和羊在左岸，沒有狼和白菜，并成為一個狀態(tài)，,2,PPT學習交流,如果全部運到右岸，這時在左岸的狀態(tài)是（0，0，0，0）根據(jù)數(shù)學中的乘法原理可得，共有2222=22=16種，但由問題中限制的條件可知有的狀態(tài)是允許的，而有的狀態(tài)是不允許的，凡是問題條件允許存在的狀態(tài)稱為可取狀態(tài)，如（1，0，1，0）（即人和羊在一起）是一個可取狀態(tài)，但（0，0，1，1）（羊和白菜在一起）是一個不可取狀態(tài)。,3,PPT學習交流,一、可取狀態(tài) A（10種） 次序是（人，狼，羊，白菜）（以左邊為標準）， 分別是（1，1，1，1） （0，0，0，0） （1，1，1，0） （0，0，0，1） （1，1，0，1）

3、（0，0，1，0） （1，0，1，1） （0，1，0，0） （1，0，1，0） （0，1，0，1） 右邊五個正好是左邊五個的相反狀態(tài)。,4,PPT學習交流,（1，0，0，0） （0，1，1，1） （0，1，1，0） （1，0，0，1） （0，0，1，1） （1，1，0，0） 是不可取的6種狀態(tài)。,二、可行運載B（4種） 次序是（人，狼，羊，白菜） （1，0，1，0） （1，1，0，0） （1，0，0， 1） （1，0，0，0）,5,PPT學習交流,三、加減運算規(guī)則 規(guī)定A（可取狀態(tài)）與B（可行運載）相加減類似于二進制取尾法則進行運算 0+0=0，1+0=1，0+1=1，1+1=0； 0-0=0

4、，1-0=1，0-1=1，1-1=0。,問題轉化為：從初始狀態(tài)（1，1，1，1）經(jīng)過多少次加減運算轉化為狀態(tài)（0，0，0，0）。這就把一個實際問題轉化為進行可取加減運算的數(shù)學問題了。,6,PPT學習交流,模型運算,如果一個狀態(tài)是可取的就打“”，否則就打“”，雖然可取但已出現(xiàn)過的狀態(tài)打“E ”，每次運去用減法，每次運回用加法，于是問題可利用窮舉法解答如下：,初始狀態(tài) 可行運載（去） 運載后左邊狀態(tài),7,PPT學習交流,運去后左邊狀態(tài) 可行運載（回） 當前左邊狀態(tài),8,PPT學習交流,第七步出現(xiàn)了（0，0，0，0）狀態(tài),9,PPT學習交流,實際問題轉化為數(shù)學游戲問題，再借助規(guī)定的數(shù)學運算求出結果，即實現(xiàn)建模，易于在計