人帶貓,雞,米過(guò)河問(wèn)題1

2012高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的，如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： A我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： J2202所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?江西環(huán)境工程職業(yè)學(xué)院參賽隊(duì)員（打印并簽名）:1. 李宇蒙 鐘世鳴 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：教練組日期：2012年_8月圣日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)〉

2012高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：摘要本文主要研究的是人帶著貓、雞、米過(guò)河的問(wèn)題。利用窮舉法，列出各種可能的原因，再用四維向量，經(jīng)過(guò)連線求解，可以的出兩種結(jié)果，分別是經(jīng)過(guò)(0,0,0,1)到(0,0,0,0)和經(jīng)過(guò)(0,1,0,0)到(0,0,0,0)而它們是等優(yōu)的。關(guān)鍵詞：窮舉法、四維向量。一問(wèn)題的提出模仿“商人過(guò)河”模型，做下面游戲：人帶著貓、雞、米過(guò)河，船除需要人劃之外，至多能載貓、雞、米三者之一，而當(dāng)人不在場(chǎng)時(shí)貓要吃雞、雞要吃米。設(shè)計(jì)一個(gè)過(guò)河方案，建立數(shù)學(xué)模型，并使渡河次數(shù)盡量地少。二問(wèn)題的分析因?yàn)檫@是個(gè)簡(jiǎn)單問(wèn)題，研究對(duì)象少所以可以用窮舉法，簡(jiǎn)單運(yùn)算和圖論即可解題。從狀態(tài)（1,1,1,1）經(jīng)過(guò)奇數(shù)次運(yùn)算變?yōu)闋顟B(tài)（0,0,0,0）的狀態(tài)轉(zhuǎn)移過(guò)程為什么是奇數(shù)次？我們注意到過(guò)河有兩種，奇數(shù)次的為從南岸到北岸，而偶數(shù)次的為北岸回到南岸，因此得到下述轉(zhuǎn)移方程，所以最后應(yīng)該是事件結(jié)束時(shí)狀態(tài)轉(zhuǎn)移數(shù)為奇數(shù)次。三基本假設(shè)3,1假設(shè)船，劃船的人外至多能載貓、雞、米三者之一。3,2當(dāng)人不在場(chǎng)時(shí)，貓一定會(huì)吃雞、雞一定會(huì)吃米。四定義符號(hào)說(shuō)明我們將人，貓，雞，米依次用四維向量中的分量表示，當(dāng)一物在此岸時(shí)，相應(yīng)分量記為1，在彼岸時(shí)記為0.如向量（1,0,1,0）表示人和雞在此案，貓和米在彼岸，并將這些向量稱為狀態(tài)向量。五模型的建立我們將人，貓，雞，米依次用四維向量中的分量表示，即（人，貓，雞，米）。

狀態(tài)向量：各分量取1表示南岸的狀態(tài)，例如表0,狀態(tài)向量：各分量取1表示南岸的狀態(tài)，例如表0,1,1,0)表示狗，雞在南岸，人，米在北岸；由于問(wèn)題中的限制條件，有些狀態(tài)是允許的，有些狀態(tài)是不允許的。凡問(wèn)題可以允許存在的狀態(tài)稱為可取狀態(tài)。對(duì)本問(wèn)題來(lái)說(shuō)，可取狀態(tài)向量可以用窮舉法列出來(lái)：(1,1,1,1)，(1,1,1,0)，(1,1,0,1)，(1,0,1,1)，(1,0,1,0)；(,0,0,0,0)，(0,0,0,1)，(0,0,1,0)，(0,1,0,0),(0,1,0,1).六模型的求解經(jīng)過(guò)連線求解可以知道有以下圖形：F(D*0*0*CDF(D*0*0*CD>I』。』0)人貓雞米人貓雞米AtJtCtGtD-*日IjTjiBmR上圖又可以簡(jiǎn)化為：即:即:圖6.1人貓雞米過(guò)河示意圖結(jié)果分析從圖看出有二解，分別是經(jīng)過(guò)(0,0,0,1)到(0,0,0,0)和經(jīng)過(guò)(0,1,0,0)到(0,0,0,0)而它們是等優(yōu)的。八模型的評(píng)價(jià)與改進(jìn)優(yōu)點(diǎn)：本算法將研究對(duì)象用四維向量中的分量表示運(yùn)用窮舉法找出所有可取狀態(tài)向量再用一些基礎(chǔ)運(yùn)算方法將結(jié)果列出來(lái)再以圖形表示出來(lái)。整個(gè)過(guò)程易懂合理。缺點(diǎn)：這里用的是圖論方法解題?？梢杂脛e的方法試試！參考文獻(xiàn)：數(shù)學(xué)建模實(shí)驗(yàn)周義倉(cāng)，赫孝良編西安：西安交通大學(xué)出版社，1999A數(shù)學(xué)建模競(jìng)賽賽題簡(jiǎn)析與論文點(diǎn)評(píng)：西安交大近年參賽論文選編赫孝良等［選編］西安：西安交通大學(xué)出版社，2002A數(shù)學(xué)建模案例分析白其崢主編北京：海洋出版社，2000A數(shù)學(xué)建模案例精選朱道元等編著北京：科學(xué)出版社，2003A數(shù)學(xué)建模導(dǎo)論陳理榮主編北京：北京郵電大學(xué)出版社，1999A數(shù)學(xué)建模：原理