傳教士與食人族題目

題目：
有n名食人族、m名傳教士和兩艘船在河的右岸，所有人都希望能夠搭船到左岸過去，A船能夠乘載最多2人，B船能夠承載最多3人。限制為無論何時兩岸的情形，食人族人數都得小於或等於傳教士人數。我們希望能夠得出在不同n值以及不同m值的情況下，過河的最少次數。

兩岸狀態

首先建立state.py檔，用於存放兩岸狀態、船的狀態和各種函式。先建立出一個class名為State，用來儲存兩岸狀態，但由於我們的人在開始後總量和人種便不會改變，因此只需要紀錄單邊的情形就可以得知另一邊的情形。我們選擇紀錄一開始的右岸(原先所有人所在的河岸)情形，要紀錄的內容有傳教士人數、食人族人數、船A是否在右岸、船B是否在右岸，還有上回所提到的A*演算法函式為f(x) = g(x) + h(x)，因此也需要設計儲存f值、g值和h值的地方。在最後我們需要將所有展開的節點，從終點處回推至起點處形成一條最短路徑，因此還是設計了空間儲存編號以及父結點的編號。最後因為本題設計船數有兩艘，因此我們設計額外的class去做特定的船隻狀態儲存，但在class State中依然要保留空間給他。另外為了方便最後展示結果，我們設計一項函式能夠顯示結點資訊。
最後的設計如下：

# State (Missionaries, Cannibals, BoatA, BoatB)
class State:
    def __init__(self, m, c, a, b):
        self.m = m  # The number of Missionaries on the right side
        self.c = c  # The number of Cannibals on the right side
        self.a = a  # a = 1: BoatA on the right side; a = 0: BoatA on the left side
        self.b = b  # b = 1: BoatB on the right side; b = 0: BoatB on the left side
        self.num = 0
        self.parent = None
        self.g = 0                      # g(x)
        self.h = 0                      # h(x)
        self.f = self.g + self.h  # f(x) = g(x) + h(x)
        self.boat = BoatState(0, 0, 0, 0)
        self.cost = 0

船A與船B狀態

而船的class就相對簡單很多了，只需要紀錄分別在船A和船B上的食人族數和傳教士數。
設計如下圖：

class BoatState:
    def __init__(self, am, ac, bm, bc):
        self.am = am  # The number of Missionaries on BoatA
        self.ac = ac  # The number of Cannibals on BoatA
        self.bm = bm  # The number of Missionaries on BoatB
        self.bc = bc  # The number of Cannibals on BoatB
        self.node = [am, ac, bm, bc]