例（２）：「宣教師と人食い人種」問題 （MC問題）
問題の形式化
- 時刻 t に左岸Lにいる宣教師の数をM(t)，人食い人種の数を C(t) とする．
- 時刻 t でボートが右岸にいる状態を D(t)=R，左岸にいる状態を D(t)=L とする．ただしボートBが岸に着くと全員一回ボートを降りる．
- MC問題の状態は，一般に s（t）＝＜M(t), C(t), D(t)＞
- ただし，0 ? M(t) ? 3，0 ? C(t) ? 3，かつ
|M(t)-M(t+1)|＋|C(t)-C(t+1)|? 2 （i.e., ボートは2人以下）
- 初期状態： s0＝＜ 3, 3, L ＞
- ゴール状態： sｇ＝＜ 0，0, R ＞