野人與牧師

　　假設河分為南、北岸。今欲由南岸到北岸。

　　今以（南岸牧師數、南岸野人數）的二維向量表示系統的狀態：

起始狀態：(3,3)
終止狀態：(0,0)

　　若只考慮南岸、合法的狀態有：
(3,3),(2,2),(1,1),(3,2),(3,1),(3,0),(2,1),(2,0),(1,0),(0,0)

　　現在再將北岸列入考慮，所以真正合法的系統狀態只有：
(3,3),(2,2),(1,1),(3,2),(3,1),(3,0),(0,0)

　　同理，合法的渡河操作狀態有：
(0,1),(1,0),(1,1),(0,2),(2,0)

南岸到北岸的結果，可以用向量減法求得；
而北岸到南岸可用向量加法求得。

　　每一次向量加減運算後都檢查一下運算的合法性。如此，經過奇數次運算後即可到達 (0,0) 。

　　還蠻好玩的，您可以試著玩玩看。　^_^


※ 引述《DanniesRex (笨小孩)》之銘言：

各位前輩，
可否和在下聊聊以下題目，各位的想法與解?
話說古時後，有 3位牧師帶著 3位野人要渡河，河岸只有一隻二人式的獨木舟。
現在遇到問題有
(1)獨木舟一次只可搭乘 2人，而此 6人均會划舟。
(2)河的任一岸，若有野人多於牧師人數時，牧師就會備野人吃掉。
亦即只有下列狀態之一時，才是安全的
a.任何一岸，牧師人數為3
b.任何一岸，牧師人數為0
c.任何一岸，野人與牧師的人數相等
試問如何想出一套順序包括
(a)初始狀態
(b)終止狀態
(c)任一可行解
使得3位牧師帶著3個野人能安全地過何。

Tags: [AI] [math] [math model] [notation]