今天偶爾想到了過河問題。記得讀國小六年級的時候第一次接觸到這個問題--六個老虎過河問題(百度上有詳細介紹，本文解決的是一個簡單的問題，下一篇文章中将讨論該問題)，當時都是從邏輯思維的方法得到正确的解決方法。本文介紹了普遍适用該類問題的方法以及該方法的改進方法，下一篇文章将介紹問題的變型及解法。
向量法（人、狗、雞、米過河問題）
問題描述：某人帶狗、雞、米用船來過河，隻有人會劃船(好像是廢話，後面問題我們還會假設動物也會劃船),另外至多還能載一物，當人不在時，狗要吃雞(有人可能會質疑：狗吃雞？，但是我看到的是狗和貓都吃小雞)，雞吃米。問人、狗、雞、米怎麼過河？
我們用一個向量來表示人、狗、雞、米所處的狀态，例如：(1 1
1 1)表示人、狗、雞、米都在左岸，則對應的(0 0 0 0)表示人、狗、雞、米都在右岸。這些向量我們稱為狀态向量，但是由于問題的條件限制，有些狀态是允許的，而有些狀态是不允許的，例如(0
1 1 1)表示人不在左岸，顯然是不允許的。我們可以窮舉出所有允許的狀态：
(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)
從上面的允許狀态中，我們可以發現規律如下：
當人在時（也就是第一位為1時），不能有相鄰的0，例如(1 1 0 0)是不允許的
當人不在時(也就是第一個為0時)，不能有相鄰的1 ，例如(0 1 1 0)是不允許的
我們将船的一次運載也用向量表示，例如(1 1 0 0)表示人和狗在船上。由于隻有人會劃船，則允許的運算向量為：
(1 1 0 0)
(1 0 1 0) (1 0 0 1)
(1 0 0 0)
是以我們可以将一次過河過程看成是一個狀态向量與一個運算向量的異或運算（模2加運算：1+1=0 1+0=1 0+0=0）。根據上述的向量法的描述，我們可以将問題簡化成：将狀态(1 1 1 1)經過奇數次與運算向量運算，變成狀态為(0 0 0 0)的狀态轉移過程。下面是過河的圖解過程：
開始狀态
船上狀态
結果狀态
1 (1
1 1 1) ------>
(1 0 1 0) ------>
(0 1 0 1)
2 (0 1 0 1) ------>
(1 0 0 0) ------>
(1 1 0 1)
3 (1 1 0 1) ------>
(1 0 0 1) ------>
(0 1 0 0)
4 (0 1 0 0)
------> (1
0 1 0) ------> (1 1 1 0)
5 (1 1 1 0)
1 0 0) ------> (0
0 1 0)
6 (0 0 1 0)
0 0 0) ------> (1 0 1 0)
7 (1 0 1 0)
0 1 0) ------>
(0 0 0 0)
奇數次：去河對岸
偶數次：回河這邊
注意事項：
在第3次過河時，開始狀态為(1 1 0 1)，如果船上狀态為(1 1 0 0),則結果狀态為(0 0 0 1)，然後經過船上狀态(1 0 0 1),結果狀态為(1 0 0 0),然後經過船上狀态(1 0 0 0)，就可以完成任務(總共5次過河)。但是這裡存在問題：當開始狀态為(0
0 0 1)，船上狀态不可能為(1 0 0 1)。因為開始狀态(0 0 0 1)表示隻有米在左岸，船上狀态(1 0 0 1)表示人和米在船上，這是不可能的！是以船上狀态的選擇是有限制的。奇數時，開始狀态為1的位置，船上對應位置才可以為1；偶數時，開始狀态為0的位置，船上對應的位置才可以為0.通俗的說：奇數時，是将有的東西運到河對岸，偶數時，是将河對岸的東西(河這邊沒有)運到河這邊。這些數學的表述可能太麻煩，我舉例說明：奇數時，當河這邊隻有人、狗、米，我們可以從選擇人、狗上船或則人、米上船，而不能選擇人、雞上船（雞在對岸）;當偶數次數時，河這邊是狗、河對岸則是人、雞、米，我們可以人、雞或則人、米回到河這邊，而不能選擇人、狗過河。
算法實作：
上面的實作可用matlab或則c來實作。若用matlab來實作，則那些狀态向量以及狀态間的異或運算比較容易表示；若用c來實作，則用時較短。兩者的難點在于注意事項中的船上變量的選取問題。是以這種方法不适合用計算機實作，在狀态變量較少的情況下，我們可以直接用手工進行運算的方法來得到結果(大家可以試試)。
改進型算法---圖論法
算法思路：将10個狀态向量用10個點表示，将這10個狀态向量分别與可行的運算向量進行運算，如果結果向量仍為允許的狀态向量，則兩者間連一條線，進而構成了一個圖的問題。我們的目标是找到一條可以從狀态(1 1 1 1)到狀态(0 0 0 0)的通路。下面是我運算得到的圖:
注意：圖中的标号用于表示對應的狀态
具體算法實作如下：
1、Dijkstra算法
結果顯示如下：
從上圖的第七行可知，從标号為1的狀态到标号為10的狀态所要經過的過程為(數組下标是從0開始的)：
1---6---3---7---2---8---5---10
2、通過每對頂點之間的最短路徑算法實作：
從上圖的最短路徑矩陣的第一行第10列可知，從狀态1到狀态10需要7步，從具體最短路徑的第10行可知，所要經過的過程為：
1---6---3---7---2---8---5---10
兩種方法求得的結果相同，我們可以用圖形象的表示如下：
通過對比可以發現，圖論法實質是在向量法的基礎上進行改進的算法，無論是在手動計算還是計算機實作上都比向量法更好。
作者：nineheadedbird