狀態(tài)轉(zhuǎn)移問題

1.人、狗、雞、米過河2.夫妻過河狀態(tài)轉(zhuǎn)移問題主要討論在一定條件下，系統(tǒng)由一狀態(tài)轉(zhuǎn)移到另一狀態(tài)是否可能，如果可能的話，應(yīng)如何具體實(shí)現(xiàn)。人、狗、雞、米過河

某人要帶狗、雞、米過河，但小船除需要人劃外，最多只能載一物過河，而當(dāng)人不在場時狗要咬雞，雞要吃米。問此人應(yīng)如何過河才能保證不發(fā)生狗咬雞，雞吃米現(xiàn)象。人、狗、雞、米過河但依題意，并非所有狀態(tài)都是允許的，分析知，可取狀態(tài)向量如下：人在此岸人在彼岸（1，1，1，1）（0，0，0，0）（1，1，1，0）（0，0，0，1）（1，1，0，1）（0，0，1，0）（1，0，1，1）（0，1，0，0）（1，0，1，0）（0，1，0，1）人、狗、雞、米過河狀態(tài)轉(zhuǎn)移需經(jīng)狀態(tài)運(yùn)算來實(shí)現(xiàn)。在實(shí)際問題中，擺一次渡即可改變現(xiàn)在狀態(tài)。為此引入一個四維向量（稱為轉(zhuǎn)移向量）來反映擺渡情況。向量分量取值也是0，1兩個，意義如下：（1，1，0，0）表示人帶狗過河（1，0，1，0）表示人帶雞過河（1，0，0，0）表示人自己過河依題意，轉(zhuǎn)移向量只能有下面4個（1，0，0，0）（1，1，0，0）（1，0，1，0）（1，0，0，1）人、狗、雞、米過河為實(shí)現(xiàn)本題的狀態(tài)轉(zhuǎn)移，規(guī)定一個狀態(tài)向量與轉(zhuǎn)移向量之間的運(yùn)算：①狀態(tài)向量與轉(zhuǎn)移向量之和為一新的狀態(tài)向量②對應(yīng)分量相加③相加方法為0+0=0，1+0=0+1=1，1+1=0例：（1，1，1，1）+（1，0，1，0）=（0，1，0，1）實(shí)際意義是：人、狗、雞、米均在此岸，人帶雞過河，轉(zhuǎn)變?yōu)樾聽顟B(tài)（0，1，0，1）人、狗、雞、米過河在實(shí)際應(yīng)用時，只考慮由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移。從而我們的問題化為由初始狀態(tài)（1，1，1，1）出發(fā)，經(jīng)奇數(shù)次上述運(yùn)算轉(zhuǎn)化為（0，0，0，0）的轉(zhuǎn)移過程。夫妻過河可取狀態(tài)：用H和W表示此岸的男子和女子數(shù)，用二維向量（H，W）表示狀態(tài)。分析知可取狀態(tài)為夫妻過河當(dāng)i為奇數(shù)時表示過河當(dāng)i為偶數(shù)時表示由對岸回來。運(yùn)算規(guī)則：同普通向量的加法。夫妻過河推廣：①按此規(guī)則4對夫妻能否過河（不能）②規(guī)則中船