ZDDによるN-Queen problemの解法を効率化する話（卒研お勉強枠②）

はじめに
この記事でやること
前回のおさらいと効率化アイディア
共有リスト
その他の効率化ポイント
- マスの添え字を逆順に振る
- 左右反転解を省略する
実験結果
おわりに
参考文献

はじめに

すっごく久しぶりの投稿です。本当はもっと早く投稿するつもりだったのですが、教授っちの指示で【卒研お勉強枠】から【卒研】を通り越して【学会発表】に飛躍したので、投稿を自粛してました。びっくり。

さて、某有名パズルゲームをZDDで解くと前回予告していたのですが、卒研やってるうちに謎に成果が発生してしまったので、2部に分けることになりました。まずは前半として、前回扱ったN-Queen ProblemをZDDでさらに効率的に解く方法を紹介します。

しれっと言ってますが、これがとんでもなく応用の利きそうなアイディアとなります。

この記事でやること

補助データ構造: 共有リスト の導入
ZDDを用いたN-Queen Problemの解法の効率化

ソースコードはGitHubで公開してます。

前回のおさらいと効率化アイディア

N-Queen Problemは、N×Nのチェス盤にN個のクイーンを相互に攻撃が当たらないように置く方法は何通りか？という組合せ問題です。

詳細な解法は前回の記事にて説明しているので省略しますが、上の行から順に演算を組み合わせてZDDを構築していくことで解くことができます。

上の行から順にZDDを構築する ( $\mathcal{P}:$ 暫定のZDD)

上の行から順にZDDを構築する ( $\mathcal{P}:$ 暫定のZDD)

この解法では、クイーンの置き場所を決め打った際に何度もoffset演算を呼び出すことで☒印のマスを含まない組合せ集合を抜き出しています。offset演算の具体的な手続きを思い出すと、offsetしたいマスよりも添え字が小さいマスを表す節点を何度も生成し、それらの節点に対し次のoffsetで再び再帰関数が呼び出されることになります。これ、かなり無駄な動きをしている気がしませんか？

実は、offsetの引数を集合に拡張した演算offset_sを考えると、次のようなメモ化再帰で手続きを記述できます。

    @cache
    def offset_s(self, V:frozenset):
        """
            selfにおいて、各v∊Vを含まない組合せ集合全体をなす部分zddを得る。
            例:
                self := {ac, ab, ad, c}
                のとき
                self.offset({b, c}) = {ad}
        """
        if len(V) == 0 or self is self.zdd.zero_terminal or self is self.zdd.one_terminal:
            return self
        v = min(V, key=lambda v: self.zdd.idx[v])
        if self.top == v:
            return self.zero.offset_s(V-frozenset([v]))
        elif self.zdd.idx[self.top] > self.zdd.idx[v]:
            return self.offset_s(V-frozenset([v]))
        else:
            return self.zdd._get_node(self.top, self.zero.offset_s(V), self.one.offset_s(V))

メモ化する関係上、引数の集合を表すデータ構造としてPythonのfrozensetを用いています。これでは結局、各関数内で時間・空間両方で集合のサイズ分の計算量をかけてしまうため、あまり解決にはなりません*1。この問題を解決する都合の良いデータ構造があればいいのですが…。

共有リスト

前述の再帰関数offset_sを実現するうえで、引数の集合を表すデータ構造が満たすべき要件は以下の通りです：

一致判定（メモ化するため）
添え字が最小のアイテムを除いた新たな集合を生成（再帰呼び出し時に使用）

これらが $\mathcal{O}(1)$ でできれば革命がおきますね。

革命がおきました。

実は意外と簡単で、ZDDから0-枝と0-葉を省くことで得られる単方向連結リストを考えれば、上記要件を満たします。これを、共有リストと呼ぶことにしましょう。

基本的な実装は、ほとんどZDDと変わりません。

ZDD同様ハッシュテーブル上に節点を保存し、節点生成時にget_node関数を挟むことで共有規則を適用します。

また詳細は省きますが、共有リストは和集合や共通部分を取るといった基本的な集合演算もZDDと同様の再帰関数で記述できます。（ただし、メモ化は必要ありません。）

その他の効率化ポイント

マスの添え字を逆順に振る

図の通りです。

実は、前回N=11までしか解けなかったのが、これだけでN=12も解けるようになりました。

左右反転解を省略する

Nが偶数の場合は、1行目のみ左半分にしかクイーンを置けないとすることで左右反転解を省略できます。

Nが奇数の場合は、1行目で真ん中に置き、2行目で左半分に置くパターンを考える必要があります。

実験結果

ソースコード

実装言語: Java SE 11*2
OS: Windows11
CPU: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz 2.30 GHz
メモリ: 8GB

		offset		offset_s
N	解	節点数	解答時間(ms)	節点数	解答時間(ms)
8	92	4,596	9	1,091	4
9	352	18,069	89	4,091	27
10	724	67,534	719	14,735	53
11	2,680	294,397	10,471	61,830	302
12	14,200	1,265,628	312,421	272,413	1,419
13	73,712	-	-	1,343,397	7,650
14	365,596	-	-	6,715,477	71,288

速い！

おわりに

共有リストを導入したことで、集合を引数に取るZDDの演算を効率よくメモ化できるようになりました。今回はoffset演算を拡張しましたが、前回の記事紹介したonset演算やchange演算も同様に拡張できます。

次回は某有名パズルゲームを扱いますが、そこで新たな集合を引数に取る演算が登場します。共有リスト、結構便利。

参考文献

湊真一. Zero-suppressed BDDs for Set Manipulation in Combinational Problems. 30th ACM/IEEE Design Automation Conference,1993.
湊真一. Zero-suppressed BDDs and their applications. Int. J. Softw. Tools Technol. Transf. (STTT), vol. 3, no. 2, pp. 156-170, Springer 2001

<< 前回

次回 >>

*1:実際のところは、ある程度改善されるようです。

*2:いつもはPythonで書いているのですが、この実験に関してはメモリがカツカツでPythonだと実行時間のブレが大きかったので、Javaでの実験結果を載せています。