基于間接矩陣法的商人過河問題數(shù)學(xué)模型

韓家寶 蔣偉

摘要：經(jīng)典的商人過河問題是指“三商三隨”安全過河問題，當(dāng)商人和隨從數(shù)量大于三或者商人與隨從數(shù)量不同就會產(chǎn)生不同的結(jié)果。本文綜合鄰接矩陣和可達(dá)矩陣，提出間接矩陣的概念，并利用間接矩陣，針對多人等數(shù)量商人隨從過河問題和多人不等數(shù)量商人隨從過河問題是否有解以及最少步數(shù)問題提出解決方案，比傳統(tǒng)的方法在討論商人數(shù)量和隨從數(shù)量較大且商人數(shù)量多時(shí)，運(yùn)算量大大減小。

關(guān)鍵詞：商人過河;鄰接矩陣;最少步數(shù);間接矩陣

一、引言

商人過河問題是一個經(jīng)典的智力游戲問題，也是數(shù)學(xué)建模中的一個經(jīng)典案例，在許多數(shù)學(xué)建模教材中都曾出現(xiàn)過。商人過河問題看起來比較簡單，但其中蘊(yùn)含的狀態(tài)轉(zhuǎn)移思想和多步?jīng)Q策思想是十分深刻的。其中經(jīng)典的商人過河問題指的是三商三隨過河問題，其中如何過河、最少步數(shù)等問題都已有結(jié)論。但是當(dāng)商人和隨從人數(shù)發(fā)生變化時(shí)，是否有解以及最小步數(shù)都還沒有明確結(jié)論。

因此，本文提出間接矩陣的概念，針對當(dāng)商人和隨從人數(shù)發(fā)生變化時(shí)的各種情況下是否存在安全過河方案以及方案最小步數(shù)問題進(jìn)行良好的解決。

二、模型建立

本文為解決商人過河問題中的是否有解及最小步數(shù)問題，提出間接矩陣和偽間接矩陣的概念。

（一）間接矩陣的提出

在此類比鄰接矩陣的概念對間接矩陣進(jìn)行定義：表示頂點(diǎn)i之間相間關(guān)系的矩陣。其中間接矩陣的級數(shù)k表示該間接矩陣中相間關(guān)系的相間步數(shù)，。表示頂點(diǎn)可以恰通過k次轉(zhuǎn)移到達(dá)頂點(diǎn)j，表示頂點(diǎn)i不可以恰通過k次轉(zhuǎn)移到達(dá)頂點(diǎn)j。

以圖1為例，其1級間接矩陣即表示點(diǎn)之間間隔1步的相連情況，即為其鄰接矩陣。其2級矩陣即為間隔2步的相連情況，如v1可以通過的方式與v5相連，則，但v1與v3之間沒有間隔2步的連接方式，則。同理即可得到圖1的2級間接矩陣，

三、模型求解

本文以三商三隨、四商四隨、四商三隨三種情況為例，利用間接矩陣法，對其是否有解及最小步數(shù)進(jìn)行求解。

（一）三商三隨問題求解

由于在河的任一岸，一旦隨從的人數(shù)比商人多，隨從就會殺人越貨。因此商人和隨從的人數(shù)分布存在安全與不安全的不同情況，其中安全狀態(tài)則為任一岸的商人人數(shù)不小于該岸隨從人數(shù)（由于當(dāng)此岸商人人數(shù)為0時(shí)，不存在殺人越貨的可能，因此也是安全狀態(tài)），通過窮舉法可列舉此岸全部安全狀態(tài)向量。

由于在轉(zhuǎn)移過程中必須保證永遠(yuǎn)處于安全狀態(tài)，因此上述安全狀態(tài)即可作為“圖”的頂點(diǎn)集：

由于只有一艘船，所以每次船帶人離開此岸后，下一次一定是船帶人回到此岸，因此可得到以下狀態(tài)轉(zhuǎn)移向量：

小船回到此岸：d=（0，+1），（0，+2），（+1，0），（+1，+1），（+2，0）

小船離開此岸：-d（0，-1），（0，-2），（-1，0），（-1，-1），（-2，0）

各個安全狀態(tài)之間的轉(zhuǎn)移即可作為“有向圖”的邊，由于船離開此岸和回到此岸的狀態(tài)轉(zhuǎn)移向量不同，即兩次的鄰接矩陣不同，分別得到船離開此岸和回到此岸的鄰接矩陣：

根據(jù)偽間接矩陣的性質(zhì)，可以得到基于該問題的偽k級間接矩陣表達(dá)式：

其中即表示（3，-3）狀態(tài)不可以經(jīng)過k次轉(zhuǎn)移到達(dá)（0，0）狀態(tài);表示（3，3）狀態(tài)可以經(jīng)過k次轉(zhuǎn)移到達(dá)（0，0）狀態(tài)，而其數(shù)值即為狀態(tài)經(jīng)過次轉(zhuǎn)移到達(dá)狀態(tài)的路徑數(shù)。令的數(shù)值不等于0的最小的k值即為最小渡河次數(shù)，的數(shù)值即為通過最小渡河次數(shù)到達(dá)（0，0）狀態(tài)的路徑數(shù)。

由于該問題需要考慮的是船在彼岸時(shí)（0，0）狀態(tài)能否達(dá)到的問題，所以只需要考慮k為奇數(shù)時(shí)的情況。

將三商三隨問題的鄰接矩陣帶入其中可以求得當(dāng)k≤9時(shí);當(dāng)k=11時(shí)，。即三商三隨問題最小渡河步數(shù)為11步，該步數(shù)下路徑有4條。

四、結(jié)論

可以利用間接矩陣整合鄰接矩陣與可達(dá)矩陣，并且利用間接矩陣可以簡單、直觀表達(dá)圖論中是否有解、最小步數(shù)、路徑數(shù)等多種問題，更好的解決狀態(tài)轉(zhuǎn)移類問題。但間接矩陣難以表達(dá)實(shí)際的路徑方案，因此在方案的表達(dá)上，需要結(jié)合圖解法進(jìn)行求解。

參考文獻(xiàn)

[1] 姜英姿，趙建強(qiáng)，米軍利. 數(shù)學(xué)建模教程[M]. 中國礦業(yè)大學(xué)出版社，2017：15-17.

[2] 周凱，鄔學(xué)軍，宋軍全. 數(shù)學(xué)建模[M].浙江大學(xué)出版社，2017：17-18.

[3] 邵建鋒.商人渡河問題的有解性分析[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識，2012（20）：139-146.

[4] 張念發(fā)，張憲新，劉長征. 基于狀態(tài)空間搜索法的商人過河問題解決方案[J]. 電腦編程技巧與維護(hù)，2010（18）： 36-37+92.

[5] 王濤.用矩陣求圖中路徑數(shù)目的另一種證明方法[J].長沙民政職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2018， 25（03）： 107-108.

[6] 原慧琳.汪定偉. 最短路徑的可達(dá)矩陣算法[J].信息與控制，2011，40（02）： 202-208+213.

[7] 張靜，李茂清. 由鄰接矩陣求解可達(dá)矩陣的一種改進(jìn)簡便算法[J].電腦知識與技術(shù)（學(xué)術(shù)交流）， 2007（01）：177-178.