前回に引き続き、8パズルを題材にして、基本アルゴリズムの深さ優先探索を、下限値枝刈り法を使って実装
手順
- 開始パズルを生成
- 開始パズルをスタックに格納
- スタックの先頭からパズルを取得
- パズルのパネル配置がゴールなら終了
- ゴール以外なら、パズルを上下左右に移動させたときのパズルを新規作成
- そのパズルのパネル配置の「マンハッタン距離 + 履歴手数」が下限値31以内であるか確認
- 下限値以上であれば次の方角で5から繰り返す
- そのパズルのパネル配置が出現済みかどうかと履歴手数を確認
- 出現済みかつ、そのパズルの履歴手数の方が大きければ、別の方角のパズルで5から繰り返す
- スタックにパズルを格納し、履歴リストに履歴を格納
- 5 から 10 までを、各方角のパズルに対して繰り返す
- 3 から 11 までを、スタックが空になるまで続ける
ポイント
- スタックを使用する
- マンハッタン距離の枝刈りで高速化
class Stack:
def __init__(self, puzzle):
self.puzzle_list = []
self.puzzle_list.append(puzzle)
def push(self, puzzle):
self.puzzle_list.insert(0, puzzle)
def pop(self):
return self.puzzle_list.pop(0)
def is_empty(self):
return len(self.puzzle_list) == 0
class Puzzle():
def __init__(self, panel_list, state_list, size):
self.panel_list = panel_list
self.state_list = state_list
self.state_list.append(panel_list)
self.size = size
self.distance = 0
def manhattan():
for d, panel in enumerate(self.panel_list):
if panel > 0:
self.distance += abs((panel - 1) // 3 - d // 3 + (panel - 1) % 3 - d % 3)
manhattan()
def gene_next_panel(self):
zero_pos = self.panel_list.index(0)
col = zero_pos // self.size
raw = zero_pos % self.size
def get_next_panel():
panel_list = self.panel_list[:]
n = panel_list[next_pos]
panel_list[next_pos] = 0
panel_list[zero_pos] = n
# 移動距離の差分を計算
self.distance += zero_pos // 3 - next_pos // 3 + zero_pos % 3 - next_pos % 3
return panel_list
if self.size > col + 1:
next_pos = (col + 1) * self.size + raw
panel_list = get_next_panel()
yield tuple(panel_list)
if col - 1 >= 0:
next_pos = (col - 1) * self.size + raw
panel_list = get_next_panel()
yield tuple(panel_list)
if self.size > raw + 1:
next_pos = col * self.size + raw + 1
panel_list = get_next_panel()
yield tuple(panel_list)
if raw - 1 >= 0:
next_pos = col * self.size + raw - 1
panel_list = get_next_panel()
yield tuple(panel_list)
def result_print(self):
for s in self.state_list:
print(s)
def depth_first(panel_list, goal, size):
puzzle = Puzzle(panel_list, [], size)
stack = Stack(puzzle)
checked_dict = {}
cnt = 0
while stack.is_empty() is False:
next_puzzle = stack.pop()
if next_panel.panel_list == goal:
return next_puzzle
for new_panel in next_puzzle.gene_next_panel():
new_puzzle = Puzzle(list(new_panel), next_puzzle.state_list[:], size)
# 下限枝刈り法にマンハッタン距離を使用
# 現在のパネル配置と履歴手数の合計が最長手数31以内かチェック
# -2 はスタートとゴールのパネル配置が state_list に含まれているため減算
if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
continue
# 過去に出現したパネル配置の場合、その配置を保持するパズルとチェック中のパズルの手数を比較
if new_panel in checked_dict and len(new_puzzle.state_list) > checked_dict[new_panel]:
continue
checked_dict[new_panel] = len(new_puzzle.state_list)
stack.push(new_puzzle)
return False
if __name__ == '__main__':
panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
size = 3
puzzle = depth_first(panel_list, goal, size)
if puzzle is not False:
puzzle.result_print()