8パズル，15パズル：最短経路探索A*（A-Star，エースター）アルゴリズム
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
実際に動く Python ソースコードがあります。ドラッグして PyScripter, Eclipse などの開発環境にコピペすればそのまま動きます。
◆◆8パズル◆◆
3×3 の枠に 1 から 8 のピースをあてはめて，1つの空ピースに四方の隣接ピースをスライドして，左上から 1 から順にピースを並べる。
1 から 6 まで揃っても 7 と 8 が入れ替わっていると順に並び替えることができないことが証明されている。
1 から 6 まで揃っても 7 と 8 が入れ替わっていると順に並び替えることができないことが証明されている。
◆◆15パズル◆◆
4×4 の枠に 1 から 15 のピースをあてはめて，1つの空ピースに四方の隣接ピースをスライドして，左上から 1 から順にピースを並べる。
1 から 13 まで揃っても 14 と 15 が入れ替わっていると順に並び替えることができないことが証明されている。
1 から 13 まで揃っても 14 と 15 が入れ替わっていると順に並び替えることができないことが証明されている。
（2023-12-23）Python3.10で動作確認済み
手数はイニシャル盤面を数えないことした。
fifteen_puzzle3X.pyをrunさせたところ，
53手で，41.5秒でした（別記事で確認したところ最短手は51手でした）
eight_puzzle3X.pyをrunさせたところ，
35手で，0.05秒でした
（CPU : Intel Core i7-1260P 2.10GHz）
◆◆最短経路探索 A*（A-Star，エースター）アルゴリズム◆◆
経路探索アルゴリズムは主なものだけでも10種類ほどあるそうですが，その中で最良優先探索（best-first search）が特に探索回数が少なくて済むアルゴリズムらしい。最良優先探索はいくつか種類があるらしいが最も有名なのが A*（A-Star，エースター）アルゴリズムである。次に有名なダイクストラアルゴリズムは A*アルゴリズムに含まれています。
ソースコードは巻末に掲載してあります。ソースファイルは左上隅からダウンロードできます。
A*アルゴリズムをPythonで実装するとなぜこうなるのかを詳細に知りたい方は次のサイトを参照してください。8パズルの例です。ヒープを自作しているのでヒープの中身まで理解できます。
http://www.nct9.ne.jp/m_hiroi/light/pyalgo28.html
『Algorithms with Python - ヒューリスティック探索』（2023-12-23 修正）
このWebのプログラムは上のサイトのプログラムと考え方は同じですが実装がかなり違います。私のプログラムはもちろん私のオリジナルですが，上のサイトのプログラムの1行ごとにコメントを入れながら理解したからこそ自分のプログラムが書けたと思います。感謝しています。
実はこのWebの15パズルは探索回数が何百万回を超えメモリ不足のエラーになりました。そこである工夫をしてとにかく解を出すようにしました。同時に上のサイトの双方向A*アルゴリズムのプログラムを15パズルに改造して初期盤面を同じにして比べてみました。私のものが53手，上のWebのものが57手です。
本サイトの別記事で私も双方向A*アルゴリズムの15パズルのプログラムをつくりました。結果，最短解は51手でした。これもある工夫をしてあります。
◆◆盤面の局面の記録はクラスで実現◆◆
debug を先にやったのは，eight_puzzle2X.py ですが，説明は，fifteen_puzzle3X.py でやります（ソースコードを巻末に掲載）。もし，これを debug したいときは，112行目の係数を10くらいにしてください。最短ではないですがきちんとものすごく速くゴールに着きます。この係数を1.0にしたとき最短経路の解が得られませんでした。そのへんの事情を後で解説します。
A*アルゴリズムのプログラムは本サイトの別記事のマイクロマウスの迷路探索とほとんど同じです（それしかできないという声も）。
大きく違うのは盤面の局面の記録はクラスにしました（10行目）。37行目で初期盤面を，38行目でゴール盤面を，68行目で探索盤面をインスタンス化しています。クラスがインスタンス化されると，12行目のコンストラクタで盤面の状態が記録されます。
つまりオブジェクト指向プログラミングしているわけです。狭義のオブジェクトとインスタンスは完全に同じ意味です。米国人には，オブジェクトは生活用語，インスタンスは技術用語に聞こえるというわけでインスタンスの方を使います。
インスタンス化するとその記録してあるすべての属性が1つの変数で呼び出せます。つまり面倒くさい配列から卒業できるわけです。
◆◆評価関数◆◆
A*アルゴリズムの評価関数の定義はこのアルゴリズムの最大の特徴である。ソースの16行目のクラスのコンストラクタにあります。それは，
self.cost = self.distance + self.heuristic
である。
distance は今の探索盤面までの手数であり，68行目のインスタンス化のときに親 node つまり1手前の盤面の distance に1を加えていてそれが引数によって自動的に記録されます。
初期盤面とゴール盤面の distance はそれぞれのインスタンス化（37, 38行目）のときに固定値を記録しています。
heuristic は92行目の関数であり，今の探索盤面からゴール盤面までの手数の予測値である。16行目で distance と heuristic が上の式で足されて cost 予測値になります。
heuristic は今の探索盤面からゴール盤面までの手数の予測値であるが，理論上，必ず実際の手数よりも小さくなければならない。heuristic はこのルールを遵守すればどんな関数でもかまわない。ルールを遵守しなければ最適解（つまり，最良，最短）が得られないことが証明されているそうだ。
92行目の関数 calc_heuristic()では，ゴール盤面と一致しないピースの数と個々のピースがゴール盤面へ移動するときのマンハッタン距離の和を heuristic としている。どこかのWebにあったものを採用している。
debug すると判るのだが，same を除いて manhattan だけにしたものが最短解をだす。same を加えると速くなるのだが最短解ではない。 まさに上の理論通りであり heuristic が最短の手数を超えていると考えられる。
最短の手数の解を得るには heuristic の式を慎重に選び実際の手数を超えてはならない。逆に heuristic を大きくすれば最短解は得られないけれどかなり速くなる。きちんとゴールには到達するので役には立つ。
実はダイクストラアルゴリズムはこの heuristic を 0 にするつまり削除するだけで実装できるのである。
◆◆ヒープ◆◆
アルゴリズムと関係ないがプログラミング技法としてのヒープを理解しないとプログラムが読めない。
ヒープは使う側からみると，1次元の配列みたいなスタックである。ただ1番上にはいつもデータのうち最小値がいる。つまりいつもソートしているので特別な構造をしているわけである。しかしこの特別な構造をしらなくてもヒープは使うことができる。知っておかなければならないのは，最上位は最小値ということだけである。
特別なデータ構造とソートアルゴリズムを知る必要はまったくないが，なぜそんなことができるのかを知ることはおもしろい。
これはツリーというデータ構造である。ツリーが10段あれば最下段は1024コのデータが並ぶ。
ある特別なアルゴリズムで枝を渡っていくとする。
ツリーからデータを探すのに最大10回の操作ですむ。
データを加えてツリーのしかるべき位置におさまるのに
最大10回の操作ですむ。
1次元配列で1000コの要素があれば1つのデータを探すのに平均500回の操作が必要である。データを1つ加えてそれを正しい位置までソートするのにもまた平均500回の操作が必要である。ヒープではそれが10回の操作ですむ。
くどいようだがヒープは使う側からみると，1次元の配列みたいなスタックである。中身をみても上のツリーのようにはなっていない。あくまでも配列のソートの考え方だけのことである。
◆◆A*（エースター）アルゴリズムの詳細◆◆
さまざまな探索において状態や局面のことを node といい，継続 node をすべて生成した状態を close といい，生成してない継続 node が残っている状態を open という。
これは航空路や物流などのグラフ理論で地点を node というのとニュアンスが違うので注意してほしい。8パズルや15パズル，または詰め将棋や詰め碁でもよいがある盤状態・局面を最短経路探索では node という。つまり 1手先はツリーが枝分かれして新しい node となる。
ある盤面の処理が終了した時点でその局面が親 node となり close になる。空ピースの位置に隣接ピースが入った盤面が枝分かれした子 node となり open となる。
探索では open-node を待ち行列にに登録して，適当な順序で取り出して継続 node を展開することを繰り返す。待ち行列を open-list と呼ぶこともある。 close-node も close-list に登録しておくのが普通である。
探索プログラムでは80行目で継続 node つまり次の盤面を open-list に追加する。このプログラムでは close-list は用意してなく，74行目以降で訪問済みの盤面とコストを記録している。 close-list を持つ例もある。迷路探索と違うのは親 node を登録しているところである。
ここまではさまざまな探索において共通の一般論である。
A*アルゴリズムの特徴の1つは open-list に priority queue （優先度付き待ち行列）を採用すること，もう1つは優先度を決める評価関数である。
評価関数は以前の項で述べたように，初期盤面から現盤面までの最短経路のコスト（手数）とゴール盤面までのコスト（手数）予測値の和である。open-node についてつまり探索途中の盤面についてコストと共に open-list に登録されている。A*アルゴリズムを実現するために open-list は前項で述べたヒープを採用している（heapq の heappush, heappop を使う）。
待ち行列 open-list から探索途中経路 open-node を取り出し探索を繰り返すところを詳しくみてみよう。
43行目の while 文は待ち行列がある限り探索を続ける。 while 文を抜けたら探索は失敗である。
ループの最初に待ち行列の中の最小コストの盤面（最初のタプルの要素[1]）を取り出す（46, 47行目）。その盤面がゴール盤面か判断して（48行目），ゴール盤面でなければ 空ピースの位置へ入る隣接ピースがあるだけ（63行目）試行する。隣接ピースは114行目の関数 coord_next()でその座標を確認している。
試行した盤面が訪問済みならばコスト（手数）小さいときだけ待ち行列 open-list に登録する。訪問済みでないならばこの盤面を待ち行列 open-list に登録する。登録はこの盤面をインスタンス化（68行目）して属性を登録する。
新しい待ち行列 open-list ができたので while文を繰り返す。
close-list を持っているプログラムでは，ループの最初で取り出された open-node は while文の最後で子 node （次の盤面）の待ち行列 open-list への登録が終わり close になるので close-list に登録する。訪問済みの盤面も close-list に登録されているはずなので上のようにコストで再評価されて open-list に登録されたときは close-list から抹消する。
このプログラムは close-list がなくても A*アルゴリズムはきちんと動くが，応用する場合は close-list の要不要を検討しなければならない。
53行目はdebugしているときに探索回数が膨大になっても強制的に停止させるためにある。debugが終了したらコメントアウトすればよい。
◆◆8パズル◆◆
書き換えたのは，144～147行目の4行だけである。実は8パズルと15パズルの両方に使えるように慎重に作られている
しかし，この15パズルは巻頭にも書いたが，探索回数が何百万回を簡単に超え，メモリ不足のエラーとなってしまった。
アルゴリズムを変えられなければ，変えられるのはただ1つ heuristic だけである。このプログラムでは heuristic は今の探索盤面のピース1つ1つがゴール盤面へ移動するときのマンハッタン距離である。これが理論的に実際の手数より小さくないと最短解が得られないことが証明されている。
一方で， heuristic を大きくすれば解を出すのが速くなる。そこで，とんでもない思い付き（heuristic）で解を出すことができた。112行目のように heuristic を大きくするのである。
巻頭に書いたようにこの解は最短解ではなかった。しかし，巻頭のWebのプログラムよりも4手も短い手数の解だったのである。十分に良い発見（heuristic）であると考えられる。
◆◆ソースコード◆◆
このWebの左上隅からダウンロードできます。
ソースファイルは2つです。
・eight_puzzle3X.py；8パズルの解法
・fifteen_puzzle3X.py；15パズルの解法
以上
【fifteen_puzzle3X.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
15-puzzle path search by A* algorithim
"""
from heapq import heappush, heappop
from random import shuffle
import time
time.clock = time.time
class sBoard():
def __init__(self, board_list, distance, parent):
self._array = board_list
self.heuristic = calc_heuristic(self._array)
self.distance = distance
self.cost = self.distance + self.heuristic
self.parent = parent
self.hashvalue = hash(tuple(self._array))
def _getsBoard(self):
return self._array
def __hash__(self):
return self.hashvalue
def __eq__(self,other):
return self._array == other._array
def __lt__(self, other):
return self._array < other._array
def astar():
queue = [] # 待ち行列
dist_dic = {} # 初期盤面からの手数
visited = {} # 訪問済みnode；過去の盤面
# インスタンス化
start = sBoard(init_board, 0, None)
end = sBoard(goal_board, 99, None) # 15
# open-listのstart-node（コストとインスタンスを登録）
heappush(queue, (start.cost, start))
No = 0 # debug
# ゴールに到達するまで新しい盤面を探索する
while len(queue) > 0:
No += 1 # debug
# open-listからコスト最小の探索済みnode（盤面）を取り出す
now_tuple = heappop(queue)
now_board = now_tuple[1]
if now_board._array == goal_board or now_board._array == goal_board2:
# ゴールを発見
end = now_board
break
"""debug
if No > 100000:
end = now_board
break
"""
# ピースのない位置へ入ることのできる隣接座標
index = now_board._array.index(0)
x, y = XY_coord(index)
coord_next_OK = coord_next(x, y)
# 次のnodeを探索；ピースのない位置へスライドを試行
for coord in coord_next_OK:
next_board = now_board._array[:]
next_index = coord[0]*No_XY + coord[1]
next_board[index],next_board[next_index] = next_board[next_index],next_board[index]
# インスタンス化
new_sboard = sBoard(next_board, now_board.distance+1, now_board)
new_distance = new_sboard.cost
if tuple(new_sboard._array) not in visited or \
new_distance < dist_dic[new_sboard]:
# 未訪問ならばor訪問済みで今回のコストのほうが小さいならば
# start nodeからの距離（コスト）を登録
dist_dic[new_sboard] = new_distance
# 訪問済みリストに登録
visited[tuple(new_sboard._array)] = new_sboard
# 親nodeを登録
new_sboard.parent = now_board
# 待ち行列に登録
heappush(queue, (new_sboard.cost, new_sboard))
var = end
sol = []
while var != start:
sol = sol + [var._getsBoard()]
var = var.parent
sol = sol + [var._getsBoard()]
sol.reverse()
#print(sol)
# print(len(sol), No)
return sol, No
def calc_heuristic(array):
"""現局面からゴールまでのコスト予測値
"""
board_list = array
same = 0
manhattan = 0
for var in board_list:
"""ゴール盤面と一致しないピースの数"""
x, y = XY_coord(var)
if goal_board.index(var) != board_list.index(var):
same += 1
"""ゴール盤面へ移動するときのマンハッタン距離"""
pos = goal_board.index(var)
goal_board_x, goal_board_y = XY_coord(pos)
x, y = XY_coord(board_list.index(var))
manhattan += abs(x-goal_board_x) + abs(y-goal_board_y)
# print(same, manhattan) # debug
# heuristic = same + manhattan
heuristic = manhattan # debug
# heuristic = same # debug
return 1.9 * heuristic
def coord_next(x, y):
"""ピースのない位置へスライドできる隣接マスのXY座標のリストを返す
"""
coord_next_OK = [[x, y]]
# right
if(x+1 < No_XY):
coord_next_OK.append([x+1, y])
# left
if(x-1 >= 0):
coord_next_OK.append([x-1, y])
# down
if(y-1 >= 0):
coord_next_OK.append([x, y-1])
# up
if(y+1 < No_XY):
coord_next_OK.append([x, y+1])
return coord_next_OK
def XY_coord(index):
"""盤面配列のインデックスからXY座標を返す
"""
x = index // No_XY
y = index % No_XY
return x, y
def main():
global init_board, goal_board, goal_board2, No_XY
No_XY = 4 # 15
goal_board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0] # 15
goal_board2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0] # 15
init_board = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12] # 15
# shuffle(init_board) # init_boardをシャッフルする
sol, visit = astar()
return sol, visit
if __name__ == '__main__':
s = time.clock()
sol, visit = main()
e = time.clock()
print(sol)
print(len(sol), visit, "%.3f" % (e - s))