今回は「農夫と山羊と狼とキャベツの問題」という、古典的なパズルを解いてみましょう。
農夫が狼と山羊とキャベツを持って川の左岸にいます。農夫はこれらを川の右岸へ運ばなければいけませんが、ボートにはそのうちのひとつしか乗せることができません。狼は山羊を好んで食べるため、この 2 つを同じ岸に残すことはできません。また、山羊はキャベツを好んで食べるため、この 2 つも同じ岸に残すことはできません。この条件で、荷物をすべて右岸へ運ぶ最短手順を求めてください。
このパズルを深さ優先探索と幅優先探索で解いてみましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。コンピュータに解かせる前に、自分で考えてみるのも面白いでしょう。
このパズルを深さ優先探索で解く場合、同じ移動手順を何度も繰り返すことがないように注意しなければいけません。極端な例ですが、何も工夫しないと、同じ物を持って左右の岸を往復する、といったことも起こります。この場合、過去の状態を記憶しておけば、簡単にチェックすることができます。つまり、過去のある状態と同じになった場合は、そこで探索を打ち切ればいいわけです。
次はデータ構造を考えましょう。今回は Python を使うので、データを文字列 farmer, wolf, goat, cabbage で表しても、簡単にプログラムを作ることができます。この場合、左右の岸は配列やタプルで表し、そこに文字列を格納することになります。
これでもいいのですが、もっと簡単な方法がデータをビットで表すことです。過去に同じ状態があるかチェックするとき、整数値の比較をするだけで済みますし、状態の変更もビットのオン・オフだけなので簡単です。そこで、次のような定数を定義します。
リスト : 定数の定義 Farmer = 0x01 # 農夫 Goat = 0x02 # 山羊 Wolf = 0x04 # 狼 Cabbage = 0x08 # キャベツ All = 0x0f # 全部揃った状態
ところで、ボートを表すデータがありませんが、ボートには必ず農夫が乗り込むので、ボートのデータは農夫で代用することができます。
それではプログラムを作りましょう。最初に、岸が安全な状態か調べる関数 is_safe() を作ります。
リスト : 安全確認
def is_safe(side):
if side & Farmer == 0:
# 農夫がいない場合
x1 = Goat | Wolf
x2 = Goat | Cabbage
if side & x1 == x1 or side & x2 == x2:
return False
return True
農夫がいない場合、山羊と狼が残っている、または、山羊とキャベツが残っていたら、山羊もしくはキャベツが食べられてしまいます。return で False を返します。それ以外の場合は安全なので True を返します。
次はボートを動かす手順を生成する関数 make_move() を作ります。
リスト : ボートの移動
def make_move(left, right):
xs = []
for x in [0, Goat, Wolf, Cabbage]:
r = Farmer | x
if left & r == r or right & r == r:
xs.append((left ^ r, right ^ r))
return xs
引数 left, right は左右の岸の状態を表します。make_move() はボートを動かして新しい状態を生成し、それをリスト xs に格納して返します。for ループでボートに乗る組み合わせを生成します。リストの先頭要素 (0) は農夫だけがボートに乗る場合を表します。x と Boat の論理和を求めて変数 r にセットします。これがボートの状態になります。
left と y の論理積が y と等しい場合、左岸からボートに乗ることができます。逆に、right と y の論理積が y と等しい場合、右岸からボートに乗ることができます。どちらの場合も、left と y の排他的論理和、right と y の排他的論理和を求めることで、ボートを動かすことができます。その結果をリスト xs に追加して、最後に return で返します。
次は深さ優先探索で解を求める関数 dfs() を作ります。
リスト : 深さ優先探索
def dfs(moves):
left, right = moves[-1]
if right == All:
print_moves(moves)
print()
else:
for l, r in make_move(left, right):
if is_safe(l) and is_safe(r) and (l, r) not in moves:
moves.append((l, r))
dfs(moves)
moves.pop()
引数 moves はタプル (左岸の状態, 右岸の状態) を格納したリストです。これで移動手順を表します。moves の末尾から現在の岸の状態を取り出して変数 left, right にセットします。right が All と等しければ、左岸から右岸へ移ることができました。関数 print_moves() で手順を表示します。
そうでなければ、make_move() で新しい状態を生成して、for ループで順番に取り出して変数 l, r にセットします。l と r が安全な状態で、かつ moves に含まれていなければ、移動可能な新しい状態です。(l, r) を moves に追加して dfs() を再帰呼び出しします。戻ってきたら pop() で末尾データを削除して、moves を元に戻すことをお忘れなく。
あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みください。
それでは実行してみましょう。
>>> dfs([(All, 0)]) [ Farmer Wolf Goat Cbbage ] [ ] [ Wolf Cbbage ] [ Farmer Goat ] [ Farmer Wolf Cbbage ] [ Goat ] [ Cbbage ] [ Farmer Wolf Goat ] [ Farmer Goat Cbbage ] [ Wolf ] [ Goat ] [ Farmer Wolf Cbbage ] [ Farmer Goat ] [ Wolf Cbbage ] [ ] [ Farmer Wolf Goat Cbbage ] [ Farmer Wolf Goat Cbbage ] [ ] [ Wolf Cbbage ] [ Farmer Goat ] [ Farmer Wolf Cbbage ] [ Goat ] [ Wolf ] [ Farmer Goat Cbbage ] [ Farmer Wolf Goat ] [ Cbbage ] [ Goat ] [ Farmer Wolf Cbbage ] [ Farmer Goat ] [ Wolf Cbbage ] [ ] [ Farmer Wolf Goat Cbbage ]
7 手の手順を 2 通り見つけることができました。実はこのパズル、全部で 10 通りの状態しかありません。そして、右側へ全部移動することが、いちばん手数のかかる問題だったなのです。コンピュータで解くには、ちょっと簡単なパズルでしたね。
一般に、深さ優先探索では最初に求まる解が最短手順とはかぎりません。最短手順を求める場合は「幅優先探索」が適しています。そこで、次は幅優先探索で最短手順と最長手数の局面を求めてみましょう。
幅優先探索のプログラムは次のようになります。
リスト : 幅優先探索
def bfs():
queue = [[(All, 0)]]
while len(queue) > 0:
moves = queue.pop(0)
left, right = moves[-1]
if right == All:
print_moves(moves)
print()
else:
for l, r in make_move(left, right):
k = (l, r)
if is_safe(l) and is_safe(r) and k not in moves:
xs = moves[:]
xs.append(k)
queue.append(xs)
リスト queue を「キュー」として使います。データは queue の末尾に追加します。これはメソッド append() を使えば簡単です。データの取り出しはメソッド pop() を使います。pop() は引数に整数を指定すると、その位置にある要素をリストから取り除いて返します。リストは破壊的に修正されることに注意してください。つまり、queue.pop(0) でキューの先頭要素を取り出し、queue.append(x) でキューに x を追加することができます。
while ループでキューにデータがあるかぎり探索処理を続行します。ループの中の処理は深さ優先探索と似ています。新しい状態へ移動できる場合、新しい手順を生成して、それを queue に追加するところが異なります。あとは難しいところはないでしょう。
それでは実行結果を示します。
>>> bfs() [ Farmer Wolf Goat Cbbage ] [ ] [ Wolf Cbbage ] [ Farmer Goat ] [ Farmer Wolf Cbbage ] [ Goat ] [ Cbbage ] [ Farmer Wolf Goat ] [ Farmer Goat Cbbage ] [ Wolf ] [ Goat ] [ Farmer Wolf Cbbage ] [ Farmer Goat ] [ Wolf Cbbage ] [ ] [ Farmer Wolf Goat Cbbage ] [ Farmer Wolf Goat Cbbage ] [ ] [ Wolf Cbbage ] [ Farmer Goat ] [ Farmer Wolf Cbbage ] [ Goat ] [ Wolf ] [ Farmer Goat Cbbage ] [ Farmer Wolf Goat ] [ Cbbage ] [ Goat ] [ Farmer Wolf Cbbage ] [ Farmer Goat ] [ Wolf Cbbage ] [ ] [ Farmer Wolf Goat Cbbage ]
7 手の手順を 2 通り見つけることができました。当然ですが、深さ優先探索と同じ結果になります。
最後に最長手数の局面を探す関数 bfs_max() を作ります。
リスト : 最長手数の局面を探す
def bfs_max():
xs = [(0, All)]
check = [(0, All)]
move = 0
while True:
ys = []
for left, right in xs:
for l, r in make_move(left, right):
k = (l, r)
if is_safe(l) and is_safe(r) and k not in check:
ys.append(k)
check.append(k)
if not ys: break
move += 1
xs = ys
print("最長手数", move)
for l, r in xs:
print_side(l)
print_side(r)
print()
print("状態の総数", len(check))
bfs_max() は最長手数の局面を求めるだけで、その手順は出力しません。リスト xs に move 手で到達する局面をセットします。最初は [(0, All)] で初期化します。変数 check は同一局面のチェックに使用します。新しく生成した局面は check に追加します。while ループの中で xs から move 手の局面を取り出し、make_move() で move + 1 の局面を生成します。それが安全でなおかつ新しい局面であれば、リスト ys と check に追加します。
move + 1 手の局面が生成されなかった場合、xs の局面が最長手数になります。ys が空リストであれば break で探索を終了して結果を表示します。そうでなければ、ys を xs にセットして探索を続行します。
それでは実行結果を示します。
>>> bfs_max() 最長手数 7 [ Farmer Wolf Goat Cbbage ] [ ] 状態の総数 10
最長手数の局面は 1 通り、左岸にすべてが揃っている状態です。生成した局面数も 10 通りしかありませんでした。
このパズルの状態遷移図に示すと次のようになります。
[(F,G,W,C), ()]
│
[(W,C), (F,G)]
│
[(F,W,C), (G)]
│
├──────┐
│ │
[(C), (F,G,W)] [(W), (F,G,C)]
│ │
[(F,G,C), (W)] [(F,G,W), (C)]
│ │
├──────┘
│
[(G), (F,W,C)]
│
[(F,G), (W,C)]
│
[(), (F,G,W,C)]
取りうる状態は 10 通りしかないので、簡単なパズルであることがわかります。
#
# farmer.py : 農夫と山羊と狼とキャベツの問題
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
Farmer = 0x01 # 農夫
Goat = 0x02 # 山羊
Wolf = 0x04 # 狼
Cabbage = 0x08 # キャベツ
All = 0x0f # 全部揃った状態
# 安全確認
def is_safe(side):
if side & Farmer == 0:
# 農夫がいない場合
x1 = Goat | Wolf
x2 = Goat | Cabbage
if side & x1 == x1 or side & x2 == x2:
return False
return True
# 移動
def make_move(left, right):
xs = []
for x in [0, Goat, Wolf, Cabbage]:
r = Farmer | x
if left & r == r or right & r == r:
xs.append((left ^ r, right ^ r))
return xs
# 手順の表示
def print_side(side):
print('[', end=' ')
if side & Farmer > 0:
print('Farmer', end=' ')
if side & Wolf > 0:
print('Wolf', end=' ')
if side & Goat > 0:
print('Goat', end=' ')
if side & Cabbage > 0:
print('Cbbage', end=' ')
print(']', end= ' ')
def print_moves(moves):
for l, r in moves:
print_side(l)
print_side(r)
print()
# 深さ優先探索
def dfs(moves):
left, right = moves[-1]
if right == All:
print_moves(moves)
print()
else:
for l, r in make_move(left, right):
if is_safe(l) and is_safe(r) and (l, r) not in moves:
moves.append((l, r))
dfs(moves)
moves.pop()
# 幅優先探索
def bfs():
queue = [[(All, 0)]]
while len(queue) > 0:
moves = queue.pop(0)
left, right = moves[-1]
if right == All:
print_moves(moves)
print()
else:
for l, r in make_move(left, right):
k = (l, r)
if is_safe(l) and is_safe(r) and k not in moves:
xs = moves[:]
xs.append(k)
queue.append(xs)
# 最長手数の局面を探す
def bfs_max():
xs = [(0, All)]
check = [(0, All)]
move = 0
while True:
ys = []
for left, right in xs:
for l, r in make_move(left, right):
k = (l, r)
if is_safe(l) and is_safe(r) and k not in check:
ys.append(k)
check.append(k)
if not ys: break
move += 1
xs = ys
print("最長手数", move)
for l, r in xs:
print_side(l)
print_side(r)
print()
print("状態の総数", len(check))