幅優先探索のノードにHashable/Comparableな自作クラスを使用する

多分競プロでは使わない

背景

幅優先探索を実装していると、探索点として単純なtupleなどで表すには少し複雑な構造を保持しておきたく、自作クラスを使いたいことがあります。
しかしながら、単にクラスを定義するだけでは「過去に探索した点かどうかの判定」や「探索の終了ノードとの比較」は簡単には行うことができません。

例として8-puzzle問題を考えます。

8-puzzle

3x3の盤面に1から8までの数字の書かれたピースが1つずつ配置され、盤面のうち1マスはピースが配置されていない状態となっています。
あなたは、ピースの配置されていないマスに隣接するマスからピースを1つ選び、それをピースの配置されていないマスに移動させる操作を任意の回数繰り返すことができます。
この操作を繰り返すことにより、以下の最終盤面に到達できるかを判定し、可能な場合は必要な最小の操作の回数と操作内容を出力しなさい。（最小の操作回数で到達可能な手順が複数ある場合、いずれを出力しても構いません。）
　
[最終盤面（1以上の数字はそれぞれ数字の書かれたピース、0は空きマスを表す）]

1 2 3
4 5 6
7 8 0

入力

入力は以下の形式で与えられます。

$a_{1}$ $a_{2}$ $a_{3}$
$a_{4}$ $a_{5}$ $a_{6}$
$a_{7}$ $a_{8}$ $a_{9}$

ただし、$0 \le a_i \le 8 (1 \le i \le 9, ai \neq a_j \text{ if } i\neq j)$であり、各$a_i$は3x3のマス目に配置されたピースの番号もしくはピースが配置されていない（0）ことを表します。

出力

初期盤面から最終盤面に到達可能な場合、最小回数$N$および最小回数で最終盤面に到達する操作の手順を、各操作にて動かすピースの番号をスペース区切りで出力しなさい。

$N$
$q_1$ $q_2$ ... $q_N$

初期盤面から最終盤面に到達できない場合は-1を出力しなさい。

入力例1

1 2 3
4 5 6
0 7 8

出力例1

2
7 8

入力例2

1 2 3
4 5 6
8 7 0

出力例2

-1

入力例3

4 5 1
2 6 0
7 3 8

出力例3

15
6 3 8 6 3 5 1 3 5 2 4 1 2 5 6

8-puzzleの状態を保持するclassの作成

この問題は初期盤面から最終盤面に到達できるかどうかが分からないため、最悪のケースでは全探索が必要です。
そこで、到達可能な盤面の全てを幅優先探索で探索することを考えます。
まずは盤面の情報を保持するclassを作成します。

from copy import deepcopy


class SlidingPuzzle():
    def __init__(self, board, route, pos0):
        """
        board = [a1, a2, a3, ... , a9]
        """
        self.board = board
        self.route = route
        self.pos0 = pos0
        return

    def slide(self):
        slide_result = []
        if self.pos0 % 3 != 0:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0-1] = sp.board[self.pos0-1], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 -= 1
            slide_result.append(sp)
        if self.pos0 % 3 != 2:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0+1] = sp.board[self.pos0+1], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 += 1
            slide_result.append(sp)
        if self.pos0 // 3 != 0:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0-3] = sp.board[self.pos0-3], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 -= 3
            slide_result.append(sp)
        if self.pos0 // 3 != 2:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0+3] = sp.board[self.pos0+3], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 += 3
            slide_result.append(sp)
        return slide_result

探索と同値性判定

探索は以下の方針で行います。

1. 初期盤面をキューの先頭に配置
2. キューの先頭が最終盤面であれば、探索をやめ結果を返す。そうでない場合、先頭の盤面から1手進めた盤面で未探索のものを全てキューに追加する。
3. キューが空になった場合、-1を出力し終了する

ここで、キューの先頭が最終盤面であればという比較があるので、以下のようなコードを実行してみます。

goalboard = [1, 2, 3, 4, 5, 6, 7, 8, 0]
goal = SlidingPuzzle(goalboard, [], 8)
start = SlidingPuzzle(goalboard, [], 8)
print(goal == start)  # False

goalとstartは同じ盤面なのでTrueが返ってほしいですが、Falseが返されました。
これは、SlidePuzzleクラスの比較時に呼び出される__eq__メソッドはobjectクラスのメソッドをオーバーライドしており、これは各インスタンスのobject IDを比較していて盤面の同値性を判定している訳ではないためです。

そこで、盤面が同じ2つのインスタンスは同じであるということを表すたに、__eq__メソッドをSlidingPuzzleクラスに実装します。

class SlidingPuzzle():
    ...
    def __eq__(self, __o):
        return __o.board == self.board

今回は盤面が同じであれば良いので、2つのインスタンス間で盤面を比較して同じであればTrueを返します。

先ほどと同じコードをもう一度実行してみます。

goalboard = [1, 2, 3, 4, 5, 6, 7, 8, 0]
goal = SlidingPuzzle(goalboard, [], 8)
start = SlidingPuzzle(goalboard, [], 8)
print(goal == start)  # True

期待通りTrueが返ることが分かります。

未探索判定

幅優先探索のアルゴリズムを実装する際、各キューアイテムの処理においてその盤面がすでに探索済みか判定する処理が入ります。
これは、探索済みのインスタンスを全て保持しておいて件別に比較することで実装することができます。
一度ざっくり実装してみます。

board = []
for _ in range(3):
    board.extend([int(i) for i in input().split()])

goalboard = [1, 2, 3, 4, 5, 6, 7, 8, 0]
goal = SlidingPuzzle(goalboard, [], 8)
sp = SlidingPuzzle(board, [], board.index(0))

q = deque([sp])
visited = []
while q:
    top = q.pop()
    if top == goal:
        print(len(top.route))
        print(*top.route)
        break
    for spi in top.slide():
        # 探索済みの点かどうかを判定
        if not spi in visited:
            q.appendleft(spi)
            visited.append(spi)
else:
    print(-1)

ところが、上のコードを実行してみると最終盤面までの手数が15ステップくらいから急激で実行時間が遅くなり、17ステップを超えるあたりからまともに動作しなくなることが分かります。
（手元の環境で15ステップの探索に10秒程度、17ステップでは1分半以上かかりました。）

これは、探索済みの点かどうかの判定にListへのin演算子を使用していますが、これはListのサイズNに対してO(N)の判定のため、この問題のように探索対象の盤面が非常に多くなる（最大$9! / 2 \simeq 1.8 \times 10^5$）ような問題では、実行時間の観点で採用できません。
このため、より工夫した実装が求められます。

ここで、そういえばSetへのin演算はO(1)であった、ということを思い出して、上のコードでリストにしている部分をSetに置き換えてみます。

...
visited = set([])
while q:
    top = q.pop()
    if top == goal:
        print(len(top.route))
        print(*top.route)
        break
    for spi in top.slide():
        # 探索済みの点かどうかを判定
        if not spi in visited:  # TypeError: unhashable type: 'SlidingPuzzle'
            q.appendleft(spi)
            visited.append(spi)
else:
    print(-1)

visitedへの判定を行うところで、SlidingPuzzleクラスがunhashableであるとしてエラーになってしまいました。
これは、SetはHashtableとして値を保持するため、hashableでないオブジェクトのin演算を行うことができないためです。
そのため、このclassに対して__hash__メソッドを定義することにします。^{1 2}

class SlidingPuzzle():
    ...
    def __hash__(self):
        return hash(tuple(self.board))

今回、このクラスの同一性を判定するためにはboardだけが重要なので、インスタンス変数boardのみからhash値を生成します。

ここまでをまとめると全体で以下のようなコードになります。
手元の環境で実行し、最悪ケース（最終盤面に到達できない場合）でおよそ15秒ほどの実行時間でした。なお、最終盤面に到達できなるかどうかはとても高速に判定することが可能なので、事前に到達できないケースを弾いておくとで、最も遅いケースは回避できます。
私はまだPythonの高速化を十分に理解できていないので、もっと早くできる方教えてください。。。

from copy import deepcopy
from collections import deque


class SlidingPuzzle():
    def __init__(self, board, route, pos0):
        self.board = board
        self.route = route
        self.pos0 = pos0
        return

    def slide(self):
        slide_result = []
        if self.pos0 % 3 != 0:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0-1] = sp.board[self.pos0-1], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 -= 1
            slide_result.append(sp)
        if self.pos0 % 3 != 2:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0+1] = sp.board[self.pos0+1], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 += 1
            slide_result.append(sp)
        if self.pos0 // 3 != 0:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0-3] = sp.board[self.pos0-3], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 -= 3
            slide_result.append(sp)
        if self.pos0 // 3 != 2:
            sp = deepcopy(self)
            sp.board[self.pos0], sp.board[self.pos0+3] = sp.board[self.pos0+3], sp.board[self.pos0]
            sp.route.append(sp.board[sp.pos0])
            sp.pos0 += 3
            slide_result.append(sp)
        return slide_result

    def __eq__(self, __o):
        return __o.board == self.board

    def __hash__(self):
        return hash(tuple(self.board))

board = []
for _ in range(3):
    board.extend([int(i) for i in input().split()])

goalboard = [1, 2, 3, 4, 5, 6, 7, 8, 0]
goal = SlidingPuzzle(goalboard, [], 8)
sp = SlidingPuzzle(board, [], board.index(0))

q = deque([sp])
visited = set([])
while q:
    top = q.pop()
    if top == goal:
        print(len(top.route))
        print(*top.route)
        break
    for spi in top.slide():
        if not spi in visited:
            q.appendleft(spi)
            visited.add(spi)
else:
    print(-1)

まとめ

• 自作class同士の同値性判定を行う場合は__eq__メソッドを実装する
• 自作classをSetやdictionaryのキーとして設定する場合は__hash__メソッドを実装する

1. この問題の場合は、classインスタンス自体をsetに含めるのではなく、単にboardをtupleにキャストしてsetに保持しておけば未探索点の判定においては十分ワークします。classのインスタンス自体をhashableにしてsetに入れたい、というやり方が本当に必要となるケースは非常に少ないと思う（というかぱっと思いつかない）です。 ↩

2. 今回SlidingPuzzleクラスはmutableなオブジェクトを含むクラスのため、__hash__メソッドの呼ばれるタイミングによって返す値が変わってしまうことがあり得ます。今回のケースに限れば一度Setに格納したあとインスタンスを操作しないので問題とはなりませんが、そもそもインスタンスの実装側でそんなことを意識しないといけないクラスの実装は良くないです。そのため、hashableなクラスの作成時には、原則クラスはImmutableとして定義すべきでしょう。 ↩