問題概要
川の左岸に3人の宣教師と3人の人喰い人がいる。
一つの小舟を使って6人とも右岸に渡りたいものとする。
ただし、小舟は最大2人しか乗れない。
左岸・右岸のいずれにおいても人喰い人の人数よりも宣教師の人数がすくなければ宣教師は喰われる。
6人とも無事に右岸に渡る手順を求めよ。
解法
コードはpython 3で書いた。
左岸の宣教師と人喰い人、小舟の個数を状態とし、深さ優先探索で解く。
左岸のそれぞれの人数が求まれば、右岸の人数も一意的に定まることに注目し、左岸の数だけを考える。
ここで、
左岸の宣教師と人喰い人、小舟の個数の状態を'sXYZ'と定義する。(0<=X<=3,0<=Y<=3,0<=Z<=1)
つまり、宣教師3人、人喰い人3人、小舟1つだった場合は's331'、
宣教師1人、人喰い人2人、小舟0つだった場合は's120'となる。
つまり、この問題は探索木において's331'をスタートとし、's000'をゴールとするような経路を求めることになる。
宣教師の数＞人喰い人の数（'s230'など）の状態は宣教師が人喰い人に喰われてしまうので、遷移先を空集合とする。
遷移先の明示はリストを使うことにする。
上記の内容をソースコードに書くと以下のようになる。
コード
DFS.py
children = {'s331':['s310','s130','s220','s320','s230',],'s310':['s321','s331'],
's130':[],'s220':['s321','s231','s331'],'s320':['s331'],'s230':[],
's321':['s120','s300','s210','s220','s310'],'s120':[],'s231':[],'s300':['s311','s321'],'s210':[],
's311':['s110','s210','s200','s300'],'s200':[],'s110':['s131','s311','s211','s121','s221'],
's131':[],'s211':[],'s121':[],'s221':['s020','s110','s200'],'s020':['s121','s221','s131','s031'],
's031':['s010','s020'],'s010':['s211','s121','s031','s111','s021'],'s111':['s000','s100','s010'],
's021':['s000','s010'],'s100':[]}
def Print(List,Close,s):
list_num = len(List)
print(List,end = "")
if list_num == 0:
base = 78
elif list_num > 0:
base = 80
for i in range(0,base-(list_num*6 + (list_num-1)*2)):
print(" ",end = "")
close_num = len(Close)
print(Close,end = "")
if close_num == 0:
base = 118
elif close_num > 0:
base = 120
for i in range(0,base-(close_num*6 + (close_num-1)*2)):
print(" ",end = "")
print("|",s)
L = ['s331']
C = []
print("|List |Close |s")
print("/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////")
while len(L) != 0:
s = L.pop(0)
Print(L,C,s)
if s == 's000':
print("I found a goal!!!!!!!!!!!!")
break
C = C + [s]
Print(L,C,s)
m = [v for v in children[s] if (v not in C)&(v not in L)]
L = m + L
Print(L,C,s)
考察
この方法だと汎用性が無く、遷移を書くときにもミスが起きる可能性が高い。
さらに、宣教師と人喰い人の人数が多くなった場合の遷移が多すぎて書ききれない。
したがって、本来は状態遷移をリストではなく再帰的な手法を用いるとよい。
しかし、今回は学校の課題として方法を指定されたのでこの方法を取った。