探索木・「ハノイの塔」
ノートブックの作成
ノートブックのタイトルは AI-5 とします． Jupyter Notebook を起動し，新規にノートブックを作成してください． ノートブックの作成方法は第1回の資料を参照してください．
ハノイの塔
今回は ハノイの塔（Tower of Hanoi） を取り上げましょう．
ハノイの塔
3本の支柱（A，B，C）があり，支柱Aに3枚の円盤（小，中，大）が重なっている．
円盤を他の支柱に移動させることができるが，
必ず大きい円盤の上に小さい円盤が積まれる状態でなければいけない．
支柱Aにある全ての円盤を支柱Cに移すにはどうすれば良いか．
この問題を 状態空間モデル で表現します．
状態空間モデル
円盤の状態を，支柱Aにあるとき1 ，支柱Bにあるとき2， 支柱Cにあるとき3と表す． この状態を，$(小, 中, 大)$の円盤の順に並べる． 例えば，初期状態は全ての円盤が支柱Aにあるため$(1, 1, 1)$と表す． また，目的状態は全ての円盤が支柱Cにあるため$(3, 3, 3)$と表す． $$ 初期状態：(1, 1, 1) $$ $$ 目的状態：(3, 3, 3) $$ 行動（操作）は，円盤を現在の支柱から，他の支柱へ移動することで与えられる． ただし，大きい円盤を小さい円盤の上に移動させることはできない． 円盤（小）に対する行動は下記の6通りである． ここで，$y$と$z$は円盤（中）と円盤（大）の状態である．
- $(1, y, z) \rightarrow (2, y, z)$ #支柱Aから支柱Bへ
- $(1, y, z) \rightarrow (3, y, z)$ #支柱Aから支柱Cへ
- $(2, y, z) \rightarrow (1, y, z)$ #支柱Bから支柱Aへ
- $(2, y, z) \rightarrow (3, y, z)$ #支柱Bから支柱Cへ
- $(3, y, z) \rightarrow (1, y, z)$ #支柱Cから支柱Aへ
- $(3, y, z) \rightarrow (2, y, z)$ #支柱Cから支柱Bへ
実装
クラスの定義
最初にライブラリをインポートします．
前回と同様に，探索問題の型 を表すSearchPrblemと
幅優先探索 を表すbreadth_firstをインポートします．
from simpleai.search import SearchProblem, breadth_first
次に 初期状態 と 目的状態 を定義します． 初期状態は$(1, 1, 1)$，目的状態は$(3, 3, 3)$です．
START = (1, 1, 1)
GOAL = (3, 3, 3)
インポートしたSearchProblemクラスをオーバライドして，
ハノイの塔を表すHanoiProblemを定義します．
オーバライドするメソッドは，actions，result，is_goalの3種類です．
class HanoiProblem(SearchProblem):
def actions(self, state):
...
def result(self, state, action):
...
def is_goal(self, state):
...
actions(self, state)
実行可能な行動のリストを返します． 行動は全部で18パターンが存在します．
def actions(self, state):
list = []
s = state[0]
m = state[1]
l = state[2]
# 円盤小
if s == 1:
list.append((2, m, l))
list.append((3, m, l))
if s == 2:
list.append((1, m, l))
list.append((3, m, l))
if s == 3:
list.append((1, m, l))
list.append((2, m, l))
# 円盤中
if m == 1 and s != 1:
if s != 2:
list.append((s, 2, l))
if s != 3:
list.append((s, 3, l))
if m == 2 and s != 2:
if s != 1:
list.append((s, 1, l))
if s != 3:
list.append((s, 3, l))
if m == 3 and s != 3:
if s != 1:
list.append((s, 1, l))
if s != 2:
list.append((s, 2, l))
# 円盤大
if l == 1 and (s != 1 and m != 1):
if s != 2 and m != 2:
list.append((s, m, 2))
if s != 3 and m != 3:
list.append((s, m, 3))
if l == 2 and (s != 2 and m != 2):
if s != 1 and m != 1:
list.append((s, m, 1))
if s != 3 and m != 3:
list.append((s, m, 3))
if l == 3 and (s != 3 and m != 3):
if s != 1 and m != 1:
list.append((s, m, 1))
if s != 2 and m != 2:
list.append((s, m, 2))
return list
result(self, state, action)
行動actionを，そのまま次の状態として扱います．
def result(self, state, action):
return action
is_goal(self, state)
状態stateがGOALと一致すれば目的状態に達したと判断します．
def is_goal(self, state):
return state == GOAL
解の探索
幅優先探索（探索木）breadth_firstを用いて解を探索します．
problem = HanoiProblem(initial_state=START)
result = breadth_first(problem, graph_search=True)
探索が終了したら，最終状態，パス，コストを表示します．
最終状態は(3, 3, 3)となっており目的状態に到達できたことがわかります．
このとき，初期状態から目的状態までのコスト（ステップ数）は7です．
print(result.state)
print(result.path())
print(result.cost)
(3, 3, 3)
[(None, (1, 1, 1)), ((3, 1, 1), (3, 1, 1)), ((3, 2, 1), (3, 2, 1)), ((2, 2, 1), (2, 2, 1)), ((2, 2, 3), (2, 2, 3)), ((1, 2, 3), (1, 2, 3)), ((1, 3, 3), (1, 3, 3)), ((3, 3, 3), (3, 3, 3))]
7
上記の結果は下図と一致します．
