はじめに
この記事は、以前公開した「最適化② - イラストロジックをortoolsで解いてみる」の続編です。
前回はNoOverlap制約を用いてイラストロジックを解くモデルを構築しました。この方法は正しく動作するものの、Colab上で大きめの問題（159x159）を解かせたところ、約292秒（約5分）と、かなりの計算時間を要していました。
今回は、CP-SATソルバーが提供する、AddAutomatonに着目し、これを用いることで、同じ問題が約6秒で解けるようになったので記事にしてみました。
Colab環境
前回の記事投稿から時間が経過しているため、まずは最新のColab環境を構築します。
Colabのデフォルト環境へ最新のortoolsをインストールする場合、protobufのバージョンも更新が必要でした。
前回記事と比べ、pipを以下のように変更しています。
!pip install --upgrade ortools protobuf
インストール後のバージョン情報は以下の通りです。
Python3.12
ortools9.14
前回記事のパフォーマンス確認
最新のColab環境で、前回記事の最適化を動かした結果は以下の通りでした。
OPTIMAL or FEASIBLE
CpSolverResponse summary:
status: OPTIMAL
objective: 0
best_bound: 0
integers: 127433
booleans: 300349
conflicts: 118178
branches: 1114116
propagations: 159091443
integer_propagations: 64837073
restarts: 100456
lp_iterations: 0
walltime: 292.271
usertime: 292.271
deterministic_time: 64.2908
gap_integral: 0
solution_fingerprint: 0x35b37a457d34fb79
前回の手法では、最新環境でも実行速度に大きな変化は見られませんでした。
今回のアプローチ
必要最低限の概要をここに記します。
各行・各列を正規表現で制約出来たら変数を大幅に減らせるんじゃないか？！
↓
正規表現そのものを渡すのはできないか・・・
↓
automatonか！
詳しくは以下。
考え方
NoOverlapが「ブロック（区間）を重ならないように配置する」という考え方だったのに対し、「ある一列が、許容されるパターンの文法に従っているか」を検証するアプローチをとってみました。
プログラマーの私にとってわかりやすい言葉にすると「各行・各列を正規表現で制約してしまおう」ということです。
各行・各列を「0（白マス）」と「1（黒マス）」で構成される一つの「文字列」と見なします。そして、その文字列がヒント数字のパターンに合致するよう制約します。
例えば、ヒントが [2, 1] の場合、以下のような正規表現 0*110+10* にマッチするパターンのみを許可する、といった具合です。（0*は0個以上の空白、0+は1個以上の空白）
このアプローチの利点は以下の通りです。
-
モデルの簡素化:
IntervalVar（区間変数）や、それを解答盤に転写するための中間変数が不要になり、モデルが非常にシンプルになります。 - 効率的な伝播: ソルバーは行全体の「文法」を一つの制約として全体的に理解するため、一つのマスの値が決まった際の制約伝播が非常に効率的になります。
AddAutomatonの仕組み
正規表現でのアプローチと説明しましたが、ortoolsのCP-SATソルバーに正規表現の文字列そのもの（例：0*110+）を直接渡すことはできません。
しかし、正規表現の理論的な概念として使われる有限オートマトン（Finite Automaton） と呼ばれる、状態で遷移するマシン（状態遷移図）が実装されています。
今回はこれを使って制約を定義します。
AddAutomatonの引数
有限オートマトンの制約追加は、CP_SATのAddAutomatonを用います。
まず、model.AddAutomaton()がどのような情報（引数）を必要とするかを見ていきましょう。
model.AddAutomaton(①対象の変数リスト, ②初期状態, ③終了状態のリスト, ④遷移のリスト)
-
① 対象の変数リスト:
チェック対象となる「文字列」です。今回のモデルでは、ある一行（または一列）のマスに対応する変数のリスト（例:[マス1, マス2, ...]）がこれにあたります。 -
② 初期状態 (The "Start"):
ルールブックを読み始める際の 「開始地点」 です。「チェックは必ずこの状態から始めなさい」という状態番号（整数）を一つ指定します。 -
③ 終了状態のリスト (The "Valid Endpoints"):
文字列を最後まで読み終えたときに、「この状態で終了したらパターンに合致したと見なす」という状態番号のリストです。 -
④ 遷移のリスト (The "Rulebook"):
これがオートマトンの本体である 「ルールブック」 です。許される全ての「状態遷移」が(現在の状態, 入力文字, 次の状態)というタプルのリストとして定義されています。例えば、(10, 1, 11)という遷移は、「もし今『状態10』にいて、入力として『1（黒マス）』を読んだら、次は『状態11』に移動する」という意味のルールです。
以降で説明するbuild_automaton_transitions関数は、④の「ルールブック」を動的に生成する役割を担っています。
build_automaton_transitionsの処理の流れ
この関数は、AddAutomatonが必要とする上記の3つの引数（初期状態、終了状態、遷移リスト）を、ヒント数字から自動生成します。
人間が分かりやすいように「名前」を付けるための工夫として関数内でタプルを使い、
状態の名前を (ブロックのインデックス, ブロック内のカウント) という形で管理しています。
-
(0, 0): 最初のブロック(インデックス0)が来る前の空白を読んでいる状態 -
(0, 1): 最初のブロックの1マス目を読んだ状態 -
(1, 0): 1番目のブロックが終わり、次のブロックとの間の空白を読んでいる状態
AddAutomatonは整数しか受け付けないため、関数内部で以下のステップを踏んでデータを作成します。
-
状態の名前（タプル）を全てリストアップする:
あるヒントに対して発生しうる全ての状態名をsetとして洗い出します。 -
状態の名前に「番号」を振る（タプル → 整数へ）:
洗い出したタプル状態に、{ (0,0): 0, (0,1): 1, ... }のように、辞書を使ってユニークな整数IDを割り振ります。 -
遷移ルールを「名前」ベースで作成する:
((0,0), 0, (0,0))のように、人間が分かりやすい「名前」を使って遷移ルールのリストを一旦作成します。これは「『開始前空白』状態で0(白)を読んだら、次も『開始前空白』状態」という意味です。 -
遷移ルールを「番号」に翻訳する:
手順3で作成したルールリストを、手順2の対応表（辞書）を使って、AddAutomatonが解釈できる整数のタプル(0, 0, 0)のリストに変換します。これが最終的な「ルールブック」となります。 -
初期状態と終了状態を「番号」で指定する:
同様に、開始状態の名前(0,0)や、終了として認められる状態名のリストも、対応表を使って整数（または整数のリスト）に変換して返します。
このように、正規表現を、コンピュータが処理できる「状態遷移のルールセット」に変換する形で実現しています。
ロジックパズルではこのオートマトン制約は、1行（または1列）分のヒントリストを元に作成します。
build_automaton_transitionsでは、clues引数にこの1行（または1列）分のヒントリストを受け取ります。
以下がその関数のコードです。
def build_automaton_transitions(clues):
"""ヒントのリストから有限オートマトンの遷移を構築します。"""
if not clues or (len(clues) == 1 and clues[0] == 0):
# 空のヒントを処理：スペースのみが許可されます。
initial_state = 0
final_states = [0]
transitions = [(0, 0, 0)]
return initial_state, final_states, transitions
num_clues = len(clues)
# 状態はタプルで表現されます: (ヒントのインデックス, ブロック内のカウント)
# まず、すべての一意の状態を生成します
all_states = set()
# 開始前の空白状態
all_states.add((0, 0))
# 末尾の空白状態
all_states.add((num_clues, 0))
for i, block_size in enumerate(clues):
# ブロック内の状態
for j in range(1, block_size + 1):
all_states.add((i, j))
# ブロック間の空白の状態
if i + 1 < num_clues:
all_states.add((i + 1, 0))
# タプル状態から整数へのマッピングを作成します
state_to_int = {state: i for i, state in enumerate(all_states)}
transitions_tuple = []
# 開始前の空白状態
transitions_tuple.append(( (0, 0), 0, (0, 0) ))
# 最初のブロックを開始
transitions_tuple.append(( (0, 0), 1, (0, 1) ))
for i, block_size in enumerate(clues):
# ブロック内での遷移
for j in range(1, block_size):
transitions_tuple.append(( (i, j), 1, (i, j + 1) ))
# ブロック終了後の遷移
if i + 1 < num_clues:
# ブロック間には空白が必須
transitions_tuple.append(( (i, block_size), 0, (i + 1, 0) ))
# ブロック間の空白状態
transitions_tuple.append(( (i + 1, 0), 0, (i + 1, 0) ))
# 次のブロックを開始
transitions_tuple.append(( (i + 1, 0), 1, (i + 1, 1) ))
else:
# 最後のブロックの後、末尾の空白状態に遷移
transitions_tuple.append(( (i, block_size), 0, (num_clues, 0) ))
# 末尾の空白状態
transitions_tuple.append(( (num_clues, 0), 0, (num_clues, 0) ))
# タプル遷移を整数遷移に変換します
transitions = [
(state_to_int[t[0]], t[1], state_to_int[t[2]]) for t in transitions_tuple
]
initial_state = state_to_int[(0, 0)]
# 空でないヒントの場合、行は2つの状況でのみ終了できます:
# 1. 最後のブロックの終わりでぴったり終了
# 2. 最後のブロックの後の末尾の空白状態で終了
final_states_tuple = [
(num_clues - 1, clues[num_clues - 1]), # Case 1
(num_clues, 0) # Case 2
]
final_states = [state_to_int[s] for s in set(final_states_tuple) if s in state_to_int]
return initial_state, final_states, transitions
制約の追加
行・列それぞれの制約適用は、関数化したことで、このbuild_automaton_transitionsを呼び出し、作成したルールを各行（各列）に紐づけるようAddAutomatonに渡すだけのシンプルなコードに置き換わりました。
※answer変数やrow_problem等の問題定義は、前回の記事で作成したものを使用します。
行の制約
answerから1行ずつ取り出したrow_varsを作成し、build_automaton_transitionsに作ってもらった制約をAddAutomatonに渡していきます。
# 行側条件の制約を作成する(Automaton方式)
for i in range(r_cnt):
row_vars = [answer[(i, j)] for j in range(c_cnt)]
initial_state, final_states, transitions = build_automaton_transitions(row_problem[i])
model.AddAutomaton(row_vars, initial_state, final_states, transitions)
列の制約
列側も同様に制約します。
# 列側も同様に作成する。(Automaton方式)
for j in range(c_cnt):
col_vars = [answer[(i, j)] for i in range(r_cnt)]
initial_state, final_states, transitions = build_automaton_transitions(col_problem[j])
model.AddAutomaton(col_vars, initial_state, final_states, transitions)
結果とまとめ
以下がautomatonを用いて最適化した際の結果ステータスになります。
OPTIMAL or FEASIBLE
CpSolverResponse summary:
status: OPTIMAL
objective: 0
best_bound: 0
integers: 0
booleans: 4537
conflicts: 171
branches: 54170
propagations: 5386272
integer_propagations: 0
restarts: 22767
lp_iterations: 0
walltime: 5.70424
usertime: 5.70424
deterministic_time: 1.84704
gap_integral: 0
solution_fingerprint: 0xa53d8d03930ededc
NoOverlapからAddAutomatonにモデルを書き換えたことで、Colab上で同じ159x159の問題を解いた際の実行時間は、約292秒から約6秒へと劇的に短縮されました。
転写用変数など、多くを省けたことが寄与したように感じています。
AddAutomatonは、オートマトンの理論や状態遷移の定義などが必要で複雑だと感じました。しかし、イラストロジックのような固定化されたルールであれば、ヘルパー関数の作成は可能で、これを実装してしまえば、モデル本体は非常にクリーンになり、ソルバーの性能を最大限に引き出すことができました。
シーケンス（順序）が重要な制約を持つ問題に対して、AddAutomatonは極めて強力な選択肢の一つであると言えるでしょう。
また、ortoolsの実装上、Automaton制約と他の制約を独立したものとして考えて組み合わせるのは比較的容易でもあります。実務上必要とされる複雑な問題に対して、Automatonを採用する箇所が上手に切り出せるのであれば活躍の機会が多いと感じました。
一方で、他の制約の都合で結局変数の数が増えてしまうようなケースでは、複雑さの割にメリットは少ない可能性もあります。使いこなせれば大きな武器となりそうなのですが、そこまでにいくつかのハードルを越える必要はありそうです。