幅優先探索・双方向探索（Python編）

8パズルを題材にして、基本アルゴリズムの幅優先探索と双方向探索を実装

幅優先探索

手順

1. 開始パズルを生成
2. 開始パズルをキューに格納
3. キューの先頭からパズルを取得
4. パズルを上下左右に移動させたときのパズルを新規作成
5. そのパズルのパネル配置がゴールなら終了
6. そのパズルのパネル配置が出現済みか確認
7. 既に出現していれば、次の方角のパズルに対して5から繰り返す
8. まだ出現していなければ、キューにパズルを格納
9. 5 から 8 までを、各方角のパズルに対して繰り返す
10. 3 から 9 までを、キューが空になるまで続ける

ポイント

• 出現済みのパネル配置を記録しておくこと
• パズルオブジェクトに、自身が通過してきたパネル配置を保持しておくこと

class Queue:
    '''
    パズルオブジェクトを格納するキュークラス
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    # パズルをリストの末端に追加
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    # パズルをリストの先頭から取得
    def dequeue(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

    # パネルの0を左右上下に移動させたときのパネル配置を返すジェネレーター
    def gene_next_panel(self, puzzle):
        zero_pos = puzzle.panel_list.index(0)

        col = zero_pos // self.size
        raw = zero_pos % self.size

        def __get_next_panel():
            panel_list = puzzle.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            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 breadth_first(size, goal, panel_list):
    puzzle = Puzzle(panel_list, [], size)
    queue = Queue(puzzle)
    checked_dict = {}

    while queue.is_empty() is False:
        puzzle = queue.dequeue()

        for next_panel in puzzle.gene_next_panel(puzzle):
            next_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size)

            if next_panel in checked_dict:
                continue

            if list(next_panel) == goal:
                return next_puzzle

            # 出現済みのパネル配置を記録
            checked_dict[next_panel] = True
            queue.enqueue(next_puzzle)

if __name__ == '__main__':
    size = 3
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]

    puzzle = breadth_first(size, goal, panel_list)

    puzzle.result_print()

双方向探索

手順

1. 開始パズルを生成
2. 開始パズルをキューに格納
3. ゴールパズルを生成
4. ゴールパズルをキューに格納
5. キューの先頭からパズルを取得
6. パズルを上下左右に移動させたときのパネル配置を生成
7. パネル配置が出現済みか確認
8. 既に出現していれば、過去にそのパネル配置を保持していたパズルとチェック中のパズルの向きを確認
9. パズルの向きが一致しなければゴール
10. まだ出現していなければ、確認用辞書とキューにパズルを格納
11. 5 から 8 までを、生成した各方角のパネル配置に対して実施
12. 5 から 10 までを、キューが空になるまで続ける

ポイント

• 確認用辞書にパズルオブジェクトを格納しておくこと
• 過去に同じパネル配置が出現した際、そのパネル配置を所持していたパズルオブジェクトの通過記録を確認することができる

class Queue:
    '''
    パズルオブジェクトを格納するキュークラス
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    # パズルをリストの末端に追加
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    # パズルをリストの先頭から取得
    def dequeue(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, direction):
        self.panel_list = panel_list
        self.state_list = state_list
        self.state_list.append(panel_list)
        self.size = size
        self.direction = direction

    def gene_next_panel(self, puzzle):
        zero_pos = puzzle.panel_list.index(0)

        col = zero_pos // self.size
        raw = zero_pos % self.size

        def __get_next_panel():
            panel_list = puzzle.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            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 back_result_print(self):

        for s in self.state_list[::-1]:
            print(s)

def bidirectional_search(size, goal, panel_list):
    start_puzzle = Puzzle(panel_list, [], size, 'S')
    queue = Queue(start_puzzle)
    goal_puzzle = Puzzle(goal, [], size, 'G')
    queue.enqueue(goal_puzzle)

    checked_dict = {}
    checked_dict[tuple(panel_list)] = start_puzzle
    checked_dict[tuple(goal)] = goal_puzzle

    while queue.is_empty() is False:
        puzzle = queue.dequeue()

        for next_panel in puzzle.gene_next_panel(puzzle):

            if next_panel in checked_dict:
                checked_puzzle = checked_dict[next_panel]

                if checked_puzzle.direction != puzzle.direction:
                    return puzzle, checked_puzzle

            else:
                new_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size, puzzle.direction)
                # 確認用辞書にパズルを格納
                checked_dict[next_panel] = new_puzzle
                queue.enqueue(new_puzzle)

if __name__ == '__main__':
    size = 3
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]

    front_puzzle, back_puzzle = bidirectional_search(size, goal, panel_list)

    front_puzzle.result_print()
    back_puzzle.back_result_print()

参照

• Algorithms with Python / 幅優先探索と反復深化