今回は基本的な探索手法である幅優先探索 (breadth-first search) と反復深化 (iterative deeping) を使って 15 パズルで有名なスライドパズルを解いてみましょう。なお、幅優先探索と反復深化の基本は拙作のページ「集合、グラフ、経路の探索」で説明しています。基本的なことは、そのページをお読みください。
参考文献『世界のパズル百科イラストパズルワンダーランド』によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
┌─┬─┬─┬─┐ │１│２│３│４│ ├─┼─┼─┼─┤ │５│６│７│８│ ├─┼─┼─┼─┤ │９│10│11│12│ ├─┼─┼─┼─┤ │13│14│15│ │ └─┴─┴─┴─┘ 図 1 : 15 パズル
15 パズルは上図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。
15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 8 までの数字を並べる「8 パズル」を考えることにします。
┌─┬─┬─┐ ┌─┬─┬─┐
│１│２│３│ │１│２│３│
├─┼─┼─┤ ├─┼─┼─┤
│４│５│６│ │４│５│６│
├─┼─┼─┤ ├─┼─┼─┤
│７│８│ │ │８│７│ │
└─┴─┴─┘ └─┴─┴─┘
（１）完成形 （２）不可能な局面
図 2 : 8 パズル
15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。15 パズルや 8 パズルの場合、参考文献『特集コンピュータパズルへの招待 スライディングブロック編』によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にしか移行できない』 とのことです。
上図 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。このような性質を「偶奇性（パリティ）」といいます。詳しい説明は拙作のページ「Puzzle DE Programming: 偶奇性（パリティ）のお話」をお読みください。8 パズルの場合、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。
それでは、プログラムを作りましょう。下図に示すスタートから完成形 (ゴール) に到達するまでの最短手数を幅優先探索で求めます。
┌─┬─┬─┐ ┌─┬─┬─┐
│８│６│７│ │１│２│３│
├─┼─┼─┤ ├─┼─┼─┤
│２│５│４│ │４│５│６│
├─┼─┼─┤ ├─┼─┼─┤
│３│ │１│ │７│８│ │
└─┴─┴─┘ └─┴─┴─┘
スタート ゴール
図 3 : 8 パズル
8 パズルの盤面は配列 (Python のリスト) を使って表します。盤面の位置と配列の添字の対応は下図を見てください。
┌─┬─┬─┐ ┌─┬─┬─┐
│１│２│３│ │０│１│２│
├─┼─┼─┤ ├─┼─┼─┤
│４│５│６│ │３│４│５│
├─┼─┼─┤ ├─┼─┼─┤
│７│８│ │ │６│７│８│
└─┴─┴─┘ └─┴─┴─┘
盤面:[1, 2, 3, 盤面と配列の対応
4, 5, 6,
7, 8, 0]
図 4 : 8 パズルの盤面
隣接リストの定義は次のようになります。
リスト : 隣接リスト
adjacent = (
(1, 3), # 0
(0, 2, 4), # 1
(1, 5), # 2
(0, 4, 6), # 3
(1, 3, 5, 7), # 4
(2, 4, 8), # 5
(3, 7), # 6
(4, 6, 8), # 7
(5, 7) # 8
)
次は局面を表すクラスを定義します。
リスト : 局面の定義
class State:
def __init__(self, board, space, prev):
self.board = board
self.space = space
self.prev = prev
クラス名は State としました。board は盤面を表す配列、space は空き場所の位置、prev は 1 手前の局面 (State のオブジェクト) を格納します。ゴールに到達したら、prev をたどって手順を表示します。
それでは幅優先探索のプログラムを作りましょう。次のリストを見てください。
リスト : 幅優先探索
def bf_search(start):
q = Queue(SIZE)
q.enqueue(State(start, start.index(0), None))
table = {}
table[tuple(start)] = True
while not q.isEmpty():
a = q.dequeue()
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table: continue
c = State(b, x, a)
if b == GOAL:
print_answer(c)
return
q.enqueue(c)
table[key] = True
# 手順の表示
def print_answer(x):
if x is not None:
print_answer(x.prev)
print(x.board)
プログラムの骨格は拙作のページ「経路の探索」で説明した幅優先探索と同じです。幅優先探索はキューを使うと簡単にプログラムできます。今回はモジュール queue を import してクラス Queue を利用します。キューは循環配列 (リングバッファ) で実装していて、大きさ (SIZE) は 181440 としました。bf_search() の引数 start はスタートの盤面を表す配列です。スタートの局面を State() で生成し、メソッド enqueue でキューに登録します。
変数 table は同一局面をチェックするための辞書 (ハッシュ) を格納します。幅優先探索の場合、手数 を 1 つずつ増やしながら探索を行います。このため、n 手目の移動で作られた局面が n 手以前の局面で出現している場合、n 手より短い手数で到達する移動手順が必ず存在します。最短手順を求めるのであれば、この n 手の手順を探索する必要はありません。table をチェックして新しい局面だけキューに登録します。Python の場合、配列 (Python のリスト) は辞書のキーにならないので、tuple でタプルに変換していることに注意してください。
次の while ループで、ゴール (GOAL) に到達するまで探索を繰り返します。キューが空になり while ループが終了する場合、start は GOAL に到達できない、つまり解くことができなかったことになります。
キューから局面を取り出して変数 a にセットします。そして、駒を動かして新しい局面を生成します。盤面は元の局面 a.board をコピーして変数 b にセットします。動かせる駒の位置は空き場所の隣なので、adjacent[a.space] で求めることができます。あとは、b[a.space] に b[x] の駒をセットし、b[x] に空き場所を表すデータ 0 を書き込みます。
新しい盤面を作ったら、同一局面がないか辞書 table でチェックします。もし、同じ局面があれば continue でループの先頭に戻ります。同一局面がない場合は、State() で新しい局面を生成して変数 c にセットします。このとき、空き場所の位置は x で、1 手前の局面は a になります。そして、b が GOAL に到達したら関数 print_answer() で手順を表示して処理を終了します。そうでなければ、局面 c をキューに登録して、table[key] に True をセットします。
print_answer() は簡単です。局面を表す配列を print() でそのまま出力します。x.prev を順番にたどって出力すると、手順は逆順に表示されてしまいます。そこで、再帰呼び出しを使って最初の状態に戻り、そこから局面を順番に出力させます。
これでプログラムは完成です。それでは実行してみましょう。
>>> bf_search([8, 6, 7, 2, 5, 4, 3, 0, 1]) [8, 6, 7, 2, 5, 4, 3, 0, 1] [8, 6, 7, 2, 0, 4, 3, 5, 1] [8, 0, 7, 2, 6, 4, 3, 5, 1] [0, 8, 7, 2, 6, 4, 3, 5, 1] [2, 8, 7, 0, 6, 4, 3, 5, 1] [2, 8, 7, 3, 6, 4, 0, 5, 1] [2, 8, 7, 3, 6, 4, 5, 0, 1] [2, 8, 7, 3, 6, 4, 5, 1, 0] [2, 8, 7, 3, 6, 0, 5, 1, 4] [2, 8, 0, 3, 6, 7, 5, 1, 4] [2, 0, 8, 3, 6, 7, 5, 1, 4] [2, 6, 8, 3, 0, 7, 5, 1, 4] [2, 6, 8, 0, 3, 7, 5, 1, 4] [2, 6, 8, 5, 3, 7, 0, 1, 4] [2, 6, 8, 5, 3, 7, 1, 0, 4] [2, 6, 8, 5, 3, 7, 1, 4, 0] [2, 6, 8, 5, 3, 0, 1, 4, 7] [2, 6, 0, 5, 3, 8, 1, 4, 7] [2, 0, 6, 5, 3, 8, 1, 4, 7] [2, 3, 6, 5, 0, 8, 1, 4, 7] [2, 3, 6, 0, 5, 8, 1, 4, 7] [2, 3, 6, 1, 5, 8, 0, 4, 7] [2, 3, 6, 1, 5, 8, 4, 0, 7] [2, 3, 6, 1, 5, 8, 4, 7, 0] [2, 3, 6, 1, 5, 0, 4, 7, 8] [2, 3, 0, 1, 5, 6, 4, 7, 8] [2, 0, 3, 1, 5, 6, 4, 7, 8] [0, 2, 3, 1, 5, 6, 4, 7, 8] [1, 2, 3, 0, 5, 6, 4, 7, 8] [1, 2, 3, 4, 5, 6, 0, 7, 8] [1, 2, 3, 4, 5, 6, 7, 0, 8] [1, 2, 3, 4, 5, 6, 7, 8, 0]
31 手で解くことができました。生成した局面は全部で 181440 通りで、実行時間は 1.06 秒 (Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) かかりました。8 パズルの場合、最長手数は 31 手で、下図に示す 2 通りの局面があります。スタートの局面はその一つです。
┌─┬─┬─┐ ┌─┬─┬─┐ │８│６│７│ │６│４│７│ ├─┼─┼─┤ ├─┼─┼─┤ │２│５│４│ │８│５│ │ ├─┼─┼─┤ ├─┼─┼─┤ │３│ │１│ │３│２│１│ └─┴─┴─┘ └─┴─┴─┘ 図 5 : 31 手で解ける局面
最長手数の局面は、幅優先探索を使って求めることができます。これはあとで試してみましょう。
ところで、今回の 8 パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。これを「双方向探索 (bi-directional search)」といいます。
その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。
これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。
生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。
それではプログラムを作りましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。局面を表すクラスに方向を格納するインスタンス変数 dir を追加します。
リスト : 局面の定義 (双方向からの探索)
# 方向を表す定数
FORE = 1
BACK = 0
# 局面の定義
class State0:
def __init__(self, board, space, prev, dir):
self.board = board
self.space = space
self.prev = prev
self.dir = dir
スタートからの探索を FORE で、ゴールからの探索を BACK で表ます。双方向探索のプログラムは次のようになります。
リスト : 双方向探索
def bi_search(start):
q = Queue(SIZE)
table = {}
a = State0(start, start.index(0), None, FORE)
q.enqueue(a)
table[tuple(start)] = a
a = State0(GOAL, GOAL.index(0), None, BACK)
q.enqueue(a)
table[tuple(GOAL)] = a
while not q.isEmpty():
a = q.dequeue()
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table:
c = table[key]
if c.dir != a.dir:
# 発見
print_answer1(a, c)
return
else:
c = State0(b, x, a, a.dir)
q.enqueue(c)
table[key] = c
スタートとゴールの局面を生成してキューにセットします。スタートの局面は FORE をセットし、ゴールの局面は GOAL をセットします。最初に、スタートの状態から 1 手目の局面が生成され、次にゴールの状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。それから、同一局面を見つけたとき、その局面の方向 dir を比較する必要があるので、table には State0 のオブジェクトをセットします。
駒の移動と局面の生成処理は幅優先探索と同じです。同じ局面を見つけたとき、table から State0 のオブジェクトを取り出して変数 c にセットします。そして、a.dir と c.dir を比較して探索方向が異なっていれば、双方向の探索で同一局面に到達したことがわかります。見つけた最短手順を関数 print_answer1() で出力します。同じ探索方向であれば、キューへの追加は行いません。
print_answer1() は簡単なプログラムなので説明は割愛いたします。詳細はプログラムリスト１をお読みください。
さっそく実行してみると、生成された局面数は 16088 個で、実行時間は 0.07 秒 (Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) でした。局面数は約 1 / 11 になり、実行時間も約 15 倍と高速になりました。
今度は最長手数の局面を求めてみましょう。最長手数の求め方ですが、181440 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。
まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。
このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、一つ前の局面を格納するインスタンス変数 prev は削除します。そのかわり、その局面までの手数を格納するインスタンス変数 move を用意します。一つ前の局面の手数を move から求め、それに 1 を足せば現在の局面の手数となります。
それではプログラムを作ります。次のリストを見てください。
リスト : 8 パズルの最長手数を求める
# 局面の定義
class State00:
def __init__(self, board, space, prev, move):
self.board = board
self.space = space
self.prev = prev
self.move = move
def search_longest_move():
buff = [None] * SIZE
a = State00(GOAL, GOAL.index(0), None, 0)
buff[0] = a
front = 0
rear = 1
table = {}
table[tuple(GOAL)] = a
while front < rear:
a = buff[front]
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table: continue
c = State00(b, x, a, a.move + 1)
buff[rear] = c
rear += 1
table[key] = c
front += 1
#
n = SIZE - 1
move = buff[n].move
print('move =', move)
while buff[n].move == move:
print(buff[n].board)
n -= 1
関数 search_longest_move() には GOAL をチェックする処理がないことに注意してください。生成できる局面がなくなるまで、つまりキューにデータがなくなるまで処理を繰り返します。新しい局面を生成するときは、1 手前の局面 a の手数 a.move を +1 します。それから、キューは Queue を使わずに、配列 buff と変数 front, rear で実装しています。enqueue(x) は buff[rear] = x で、dequeue() は buff[front] で実現できます。このあと、rear と front を +1 することをお忘れなく。
rear と front が等しくなるとキューは空になります。while ループを終了して、最長手数とその局面を表示します。buff[SIZE - 1] の局面の手数が最長手数になります。この値を変数 move にセットします。あとは、move と同じ手数の局面を出力するだけです。
これでプログラムは完成です。さっそく実行してみましょう。
move = 31 [8, 6, 7, 2, 5, 4, 3, 0, 1] [6, 4, 7, 8, 5, 0, 3, 2, 1]
最長手数は 31 手で、その配置は全部で 2 通りになります。実行時間は 0.87 秒 (Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) になりました。
次は反復深化で 8 パズルを解いてみましょう。拙作のページ「経路の探索」で説明したように、反復深化は最短手数を求めることができるアルゴリズムです。幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。
ただし、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。実行時間が長くなるといっても、枝刈りを工夫することでパズルを高速に解くことができます。メモリ不足になる場合には、積極的に使ってみたいアルゴリズムといえるでしょう。
幅優先探索では全ての局面を保存しましたが、反復深化ではその必要はありません。盤面は配列で表し、グローバル変数 board に格納します。駒の移動は board を書き換えて、バックトラックする時は元に戻すことにします。動かした駒は配列 move_piece に格納します。動かした駒がわかれば局面を再現できるので、それで移動手順を表すことにしましょう。
それでは、探索を行う関数 id_search() を作ります。次のリストを見てください。
リスト : 単純な反復深化による解法
# 盤面 (最長手数の局面)
board = [8, 6, 7, 2, 5, 4, 3, 0, 1]
# 動かした駒
move_piece = [None] * 32
# 単純な反復深化
def id_search(limit, move, space):
if move == limit:
if board == GOAL:
global count
count += 1
print(move_piece[1:])
else:
for x in adjacent[space]:
p = board[x]
if move_piece[move] == p: continue
# 駒を動かす
board[space] = p
board[x] = 0
move_piece[move + 1] = p
id_search(limit, move + 1, x)
# 元に戻す
board[space] = 0
board[x] = p
id_search() の引数 limit が上限値、move が手数、space が空き場所の位置を表します。手数が上限値に達したら、パズルが解けたかチェックします。GOAL は完成形を表す配列です。完成形に到達したら、解の総数をカウントする変数 count をインクリメントし、print() で手順を表示します。上限値に達していない場合は、駒を移動して新しい局面を作ります。
8 パズルのように、元の局面に戻すことが可能 (可逆) なパズルの場合、単純な深さ優先探索では同じ移動手順を何度も繰り返すことがあります。そうなると、とんでもない解を出力するだけではなく、再帰呼び出しが深くなるとスタックがオーバーフローしてプログラムの実行が停止してしまいます。
このような場合、局面の履歴を保存しておいて同じ局面がないかチェックすることで、解を求めることができるようになります。ただし、同一局面をチェックする分だけ時間が余分にかかりますし、最初に見つかる解が最短手数とは限りません。
反復深化では深さが制限されているため、同一局面のチェックを行わなくてもスタックオーバーフローが発生することはありません。そのかわり、無駄な探索はどうしても避けることができません。8 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。
プログラムでは、配列 move_piece に移動した駒を格納しているので、1 手前と同じ駒は動かさないようにチェックしています。なお、move_piece[0] はダミーデータで None になります。move_piece[1] 以降のデータが実際に動かした駒になります。
次は id_search() を呼び出すプログラムを作ります。
リスト : 反復深化の実行
count = 0
s = time.time()
for x in range(1, 32):
print('move ', x)
id_search(x, 0, board.index(0))
if count > 0: break
e = time.time()
print('{:.3f}'.format(e - s))
変数 x が上限値を表します。x を 1 手ずつ増やして id_search() を呼び出します。グローバル変数 count が 0 より大きくなれば解が見つかったのでループを脱出します。プログラムはこれで完成です。
実際に実行してみると、当然ですが最短手数は 31 手で 40 通りの手順が表示されました。実行時間は 115 秒 (Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) かかりました。2 分近くかかるのですから、やっぱり遅いですね。反復深化の場合、枝刈りを工夫しないと高速に解くことはできません。そこで、反復深化の常套手段である「下限値枝刈り法」を使うことにしましょう。
下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限値が 10 手とすると、あと 5 手だけ動かすことができますね。この時、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。このように、必要となる最低限の手数が明確にわかる場合、この値を「下限値 (Lower Bound)」と呼びます。この下限値を求めることができれば、「今の移動手数＋下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。
さて、下限値を求める方法ですが、これにはいろいろな方法が考えられます。今回は、各駒が正しい位置へ移動するまでの手数 (移動距離) [*1] を下限値として利用することにしましょう。次の図を見てください。
┌─┬─┬─┐ ┌──┬──┬──┐
│１│２│３│ │8(3)│6(2)│7(4)│
├─┼─┼─┤ ├──┼──┼──┤
│４│５│６│ │2(2)│5(0)│4(2)│
├─┼─┼─┤ ├──┼──┼──┤
│７│８│ │ │3(4)│ │1(4)│
└─┴─┴─┘ └──┴──┴──┘
(n) : n は移動距離
(1) 完成形 (2) 初期状態：合計 21
図 6 : 下限値の求め方
たとえば、右下にある 1 の駒を左上の正しい位置に移動するには、最低でも 4 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、4 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数となります。これを下限値として利用することができます。ちなみに、上図 (2) の初期状態の下限値は 21 手になります。
下限値枝刈り法を使う場合、下限値の計算を間違えると正しい解を求めることができなくなります。たとえば、10 手で解ける問題の下限値を 11 手と計算すれば、最短手数を求めることができなくなります。それどころか、10 手の解しかない場合は、答えを求めることすらできなくなります。下限値の計算には十分に注意してください。
それでは、プログラムを作りましょう。下限値の求め方ですが、駒を動かすたびに各駒の移動距離を計算していたのでは時間がかかります。8 パズルの場合、1 回に一つの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけ計算すればいいでしょう。また、駒の移動距離はいちいち計算するのではなく、あらかじめ計算した結果を配列に格納しておきます。この配列を distance とすると、盤面から移動距離を求めるプログラムは次のようになります。
リスト : 移動距離を求める
# 距離
distance = (
(),
(0, 1, 2, 1, 2, 3, 2, 3, 4),
(1, 0, 1, 2, 1, 2, 3, 2, 3),
(2, 1, 0, 3, 2, 1, 4, 3, 2),
(1, 2, 3, 0, 1, 2, 1, 2, 3),
(2, 1, 2, 1, 0, 1, 2, 1, 2),
(3, 2, 1, 2, 1, 0, 3, 2, 1),
(2, 3, 4, 1, 2, 3, 0, 1, 2),
(3, 2, 3, 2, 1, 2, 1, 0, 1)
)
# 移動距離を求める
def get_distance(board):
v = 0
for x in range(9):
p = board[x]
if p == 0: continue
v += distance[p][x]
return v
distance は 2 次元配列 (タプル) で「駒の種類×駒の位置」を表しています。空き場所は関係ないので、distance[0] はダミーとなります。関数 get_distance() は盤面 board にある駒と位置から移動距離を求めます。変数 v を 0 に初期化して、空き場所 (0) 以外の駒の移動距離を distance から求めて v に足し算するだけです。
次は、下限値枝刈り法による反復深化を行う関数 id_lower_search() を作ります。次のリストを見てください。
リスト : 下限値枝刈り法
def id_lower_search(limit, move, space, lower):
if move == limit:
if board == GOAL:
global count
count += 1
print(move_piece[1:])
else:
for x in adjacent[space]:
p = board[x]
if move_piece[move] == p: continue
# 駒を動かす
board[space] = p
board[x] = 0
move_piece[move + 1] = p
new_lower = lower - distance[p][x] + distance[p][space]
# 下限値枝刈り法
if new_lower + move <= limit:
id_lower_search(limit, move + 1, x, new_lower)
# 元に戻す
board[space] = 0
board[x] = p
id_lower_search() の引数 lower は現在の盤面 board の下限値を表しています。駒を動かしたら差分を計算して、新しい下限値 new_lower を求めます。そして、new_lower + move が上限値 limit を越えたら枝刈りを行います。limit 以下であれば id_lower_search() を再帰呼び出しします。追加する処理はこれだけで、あとは反復深化のプログラムと同じです。とても簡単ですね。
最後に id_lower_search() を呼び出す処理を修正します。次のリストを見てください。
リスト : id_lower_search の呼び出し
# 実行
count = 0
s = time.time()
n = get_distance(board)
for x in range(n, 32):
print('move ', x)
id_lower_search(x, 0, board.index(0), n)
if count > 0: break
e = time.time()
print('{:.3f}'.format(e - s))
get_distance() で初期状態の下限値 n を求めます。下限値がわかるのですから、上限値 limit は 1 手からではなく下限値 n からスタートします。あとは id_lower_search() に下限値 n を渡して呼び出すだけです。プログラムの主な修正はこれだけです。
実際に実行してみると、実行時間は 0.18 秒 (Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) でした。約 640 倍という高速化に驚いてしまいました。下限値枝刈り法の効果は極めて高いですね。
#
# queue.py : キュー (RingBuffer による実装)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
class Queue:
def __init__(self, size):
self.size = size
self.buff = [None] * size
self.front = 0
self.rear = 0
self.count = 0
def enqueue(self, x):
if self.count >= self.size: raise 'Queue is full'
self.buff[self.rear] = x
self.rear += 1
self.count += 1
if self.rear == self.size: self.rear = 0
def dequeue(self):
if self.count <= 0: raise 'Queue is empty'
x = self.buff[self.front]
self.front += 1
self.count -= 1
if self.front == self.size: self.front = 0
return x
def isEmpty(self):
return self.count == 0
if __name__ == '__main__':
a = Queue(10)
for x in range(10):
a.enqueue(x)
while not a.isEmpty():
print(a.dequeue())
#
# eight.py : 8 Puzzle (幅優先探索による解法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from queue import *
import time
# 隣接リスト
adjacent = (
(1, 3), # 0
(0, 2, 4), # 1
(1, 5), # 2
(0, 4, 6), # 3
(1, 3, 5, 7), # 4
(2, 4, 8), # 5
(3, 7), # 6
(4, 6, 8), # 7
(5, 7) # 8
)
# 状態数
SIZE = 181440
# ゴールの局面
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
##### 幅優先探索 #####
# 局面の定義
class State:
def __init__(self, board, space, prev):
self.board = board
self.space = space
self.prev = prev
def bf_search(start):
q = Queue(SIZE)
q.enqueue(State(start, start.index(0), None))
table = {}
table[tuple(start)] = True
while not q.isEmpty():
a = q.dequeue()
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table: continue
c = State(b, x, a)
if b == GOAL:
print_answer(c)
return
q.enqueue(c)
table[key] = True
# 表示
def print_answer(x):
if x is not None:
print_answer(x.prev)
print(x.board)
##### 双方向探索 #####
FORE = 1
BACK = 0
# 局面の定義
class State0:
def __init__(self, board, space, prev, dir):
self.board = board
self.space = space
self.prev = prev
self.dir = dir
def bi_search(start):
q = Queue()
table = {}
a = State0(start, start.index(0), None, FORE)
q.enqueue(a)
table[tuple(start)] = a
a = State0(GOAL, GOAL.index(0), None, BACK)
q.enqueue(a)
table[tuple(GOAL)] = a
while not q.isEmpty():
a = q.dequeue()
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table:
c = table[key]
if c.dir != a.dir:
# 発見
print_answer1(a, c)
return
else:
c = State0(b, x, a, a.dir)
q.enqueue(c)
table[key] = c
# 手順の表示
def print_answer_goal(a):
while a is not None:
print(a.board)
a = a.prev
def print_answer1(a, b):
if a.dir == FORE:
print_answer(a)
print_answer_goal(b)
else:
print_answer(b)
print_answer_goal(a)
##### 最長手数の局面を求める #####
# 局面の定義
class State00:
def __init__(self, board, space, prev, move):
self.board = board
self.space = space
self.prev = prev
self.move = move
def search_longest_move():
buff = [None] * SIZE
a = State00(GOAL, GOAL.index(0), None, 0)
buff[0] = a
front = 0
rear = 1
table = {}
table[tuple(GOAL)] = a
while front < rear:
a = buff[front]
for x in adjacent[a.space]:
b = a.board[:]
b[a.space] = b[x]
b[x] = 0
key = tuple(b)
if key in table: continue
c = State00(b, x, a, a.move + 1)
buff[rear] = c
rear += 1
table[key] = c
front += 1
#
n = SIZE - 1
move = buff[n].move
print('move =', move)
while buff[n].move == move:
print(buff[n].board)
n -= 1
#
# eight_id.py : 8 Puzzle (反復深化による解法)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import time
# 隣接リスト
adjacent = (
(1, 3), # 0
(0, 2, 4), # 1
(1, 5), # 2
(0, 4, 6), # 3
(1, 3, 5, 7), # 4
(2, 4, 8), # 5
(3, 7), # 6
(4, 6, 8), # 7
(5, 7) # 8
)
# 距離
distance = (
(),
(0, 1, 2, 1, 2, 3, 2, 3, 4),
(1, 0, 1, 2, 1, 2, 3, 2, 3),
(2, 1, 0, 3, 2, 1, 4, 3, 2),
(1, 2, 3, 0, 1, 2, 1, 2, 3),
(2, 1, 2, 1, 0, 1, 2, 1, 2),
(3, 2, 1, 2, 1, 0, 3, 2, 1),
(2, 3, 4, 1, 2, 3, 0, 1, 2),
(3, 2, 3, 2, 1, 2, 1, 0, 1)
)
# 距離を求める
def get_distance(board):
v = 0
for x in range(9):
p = board[x]
if p == 0: continue
v += distance[p][x]
return v
# ゴールの局面
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
# 盤面
board = [8, 6, 7, 2, 5, 4, 3, 0, 1]
# 動かした駒
move_piece = [None] * 32
# 単純な反復深化
def id_search(limit, move, space):
if move == limit:
if board == GOAL:
global count
count += 1
print(move_piece[1:])
else:
for x in adjacent[space]:
p = board[x]
if move_piece[move] == p: continue
# 駒を動かす
board[space] = p
board[x] = 0
move_piece[move + 1] = p
id_search(limit, move + 1, x)
# 元に戻す
board[space] = 0
board[x] = p
# 下限値枝刈り法
def id_lower_search(limit, move, space, lower):
if move == limit:
if board == GOAL:
global count
count += 1
print(move_piece[1:])
else:
for x in adjacent[space]:
p = board[x]
if move_piece[move] == p: continue
# 駒を動かす
board[space] = p
board[x] = 0
move_piece[move + 1] = p
new_lower = lower - distance[p][x] + distance[p][space]
# 下限値枝刈り法
if new_lower + move <= limit:
id_lower_search(limit, move + 1, x, new_lower)
# 元に戻す
board[space] = 0
board[x] = p
# 実行
count = 0
s = time.time()
n = get_distance(board)
for x in range(n, 32):
print('move ', x)
id_lower_search(x, 0, board.index(0), n)
if count > 0: break
e = time.time()
print('{:.3f}'.format(e - s))