今回は, 『Python計算機科学新教本』3章 制約充足問題 の 3.6 回路レイアウト を書いてみたので備忘録として残しておきます。本書の原著は『Classic Computer Science Problems in Python』です。
環境は Python 3.7 です。
3章 制約充足問題
制約充足問題 (Constraint Satisfaction Problem; CSP) は変数の集合 (variables)、変数の取り得る値の集合である領域 (domains)、変数間の制約 (constraints) の3つの要素で構成される。全ての制約を満たすように変数に領域に属する値を割り当てることを, 制約充足問題を解くという。また, 解を探索するプログラムを制約ソルバー (Constraint Solver) という。制約充足問題の例として, 地図の塗り分け問題, N クイーン問題, スケジューリングなどがある。
本書の制約充足問題では Constraint クラスと CSP クラスを共通のフレームワークとして使う。
Constraint クラスは抽象基底クラスで, 制約を受ける変数の list である variables と制約を満たしているかチェックする satisfied メソッドを持つ。
CSP クラスは変数, 領域, 制約をまとめるクラスで, add_constraint メソッドは制約に関する変数に新たに制約を追加する。
consistent メソッドは変数の全制約を調べて, その assignment (変数とその領域の辞書) で制約を満たしているかチェックし, 全制約を満たしている場合は True を返す。 backtracking_search メソッドは名前の通り, バックトラック探索 (深さ優先探索) を行う。 各変数について unassigned を調べ、unassigned の変数の領域について assignment を再帰的に試していく。
from typing import Generic, TypeVar, Dict, List, Optional
from abc import ABC, abstractmethod
V = TypeVar("V")
D = TypeVar("D")
class Constraint(Generic[V, D], ABC):
def __init__(self, variables: List[V]) -> None:
self.variables = variables
@abstractmethod
def satisfied(self, assignment: Dict[V, D]) -> bool:
...
class CSP(Generic[V, D]):
def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None:
self.variables: List[V] = variables
self.domains: Dict[V, List[D]] = domains
self.constraints: Dict[V, List[Constraint[V, D]]] = {}
for variable in self.variables:
self.constraints[variable] = []
if variable not in self.domains:
raise LookupError("Every variable should have a domain assigned to it.")
def add_constraint(self, constraint: Constraint[V, D]) -> None:
for variable in constraint.variables:
if variable not in self.variables:
raise LookupError("Variable in contraint not in CSP")
else:
self.constraints[variable].append(constraint)
def consistent(self, variable: V, assignment: Dict[V, D]) -> bool:
for constraint in self.constraints[variable]:
if not constraint.satisfied(assignment):
return False
return True
def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:
if len(assignment) == len(self.variables):
return assignment
unassigned: List[V] = [v for v in self.variables if v not in assignment]
first: V = unassigned[0]
for value in self.domains[first]:
local_assignment = assignment.copy()
local_assignment[first] = value
if self.consistent(first, local_assignment):
result: Optional[Dict[V, D]] = self.backtracking_search(
local_assignment
)
if result is not None:
return result
return None
3.4 単語探し
3.4 単語探しでは, (m, n) の長方形の各位置に文字を配置して, その中に隠れている単語を, 行, 列, 対角方向に探し出す単語探しパズルを生成する word_search.py が掲載されている。
word_search.py を実行すると以下が出力され, “MATTHEW”, “JOE”, “MARY”, “SARAH”, “SALLY” といった単語を見つけることができる。
$ python word_search.py
LWEHTTAMU
MARYIASHE
WYBZKHAEO
FBCVFALSJ
VGHRLRLYV
GPSWSAYWT
CJIZOSJKN
YZJRFFKUR
NZFBETALC
3.6 回路レイアウト
3.6 回路レイアウトでは, 長方形のプリント基板にサイズの異なる回路部品を配置できるかという回路基板レイアウト問題を考える。言い換えると「異なるサイズの複数の長方形を, 大きな長方形の内部に収まるように配置する」という問題である。
前述の単語探し問題と回路基盤レイアウト問題は似ているが, 単語探し問題では (1, n) の単語を扱ったが, 回路基盤レイアウト問題では (m, n) の部品を扱う点が異なるというヒントが与えられる。
早速, word_search.py をベースとしてコードを変更する。
from typing import NamedTuple, List, Dict, Optional, Tuple
from itertools import product
from csp import CSP, Constraint
Grid = List[List[str]]
class GridLocation(NamedTuple):
row: int
column: int
def generate_grid(rows: int, columns: int) -> Grid:
return [["." for c in range(columns)] for r in range(rows)]
def display_grid(grid: Grid) -> None:
for row in grid:
print("".join(row))
def generate_domain(component: List[str], grid: Grid) -> List[List[GridLocation]]:
domain: List[List[GridLocation]] = []
height: int = len(grid)
width: int = len(grid[0])
comp_height, comp_width = component_to_size(component)
for row in range(height):
for col in range(width):
if col + comp_width < width and row + comp_height < height:
columns: range = range(col, col + comp_width)
rows: range = range(row, row + comp_height)
grid_set = list(product([r for r in rows], [c for c in columns]))
rectangle: List = [GridLocation(r, c) for r, c in grid_set]
domain.append(rectangle)
return domain
def component_to_size(key: str) -> List[Tuple[int]]:
component_size = {"A": (4, 3), "B": (2, 6), "C": (1, 7), "D": (7, 2), "E": (2, 3)}
return component_size[key]
class CircuitBoardLayoutConstraint(Constraint[str, List[GridLocation]]):
def __init__(self, words: List[str]) -> None:
super().__init__(words)
self.components: List[str] = components
def satisfied(self, assignment: Dict[str, List[GridLocation]]) -> bool:
all_locations = [locs for values in assignment.values() for locs in values]
return len(set(all_locations)) == len(all_locations)
if __name__ == "__main__":
grid: Grid = generate_grid(9, 9)
components: List[str] = ["A", "B", "C", "D", "E"]
locations: Dict[List[str], List[List[GridLocation]]] = {}
for component in components:
locations[component] = generate_domain(component, grid)
csp: CSP[List[List[str]], List[GridLocation]] = CSP(components, locations)
csp.add_constraint(CircuitBoardLayoutConstraint(components))
solution: Optional[Dict[str, List[GridLocation]]] = csp.backtracking_search()
if solution is None:
print("No solution found")
else:
for component, grid_locations in solution.items():
comp_height, comp_width = component_to_size(component)
for index, letter in enumerate(component * (comp_height * comp_width)):
(row, col) = (grid_locations[index].row, grid_locations[index].column)
grid[row][col] = letter
display_grid(grid)
最初に generate_grid() で Grid 内を適当な文字 “.” で埋める初期化を行う。generate_domain() は Grid に収まる範囲で部品を配置可能な座標のリスト (i.e. 領域) を生成する。単語は文字列から長さの情報を得られるが, 部品のサイズは二次元となるため component_to_size() で部品の識別子をサイズにマップする。
CircuitBoardLayoutConstraint は Constraint クラスを override したクラスで, satisfied メソッドは部品が占める部分が他の部品と重ならないかの制約を set を使ってチェックする。
コードを実行すると以下が出力される。
$ python circuit_board_layout.py
AAAEEEDD.
AAAEEEDD.
AAA...DD.
AAA...DD.
BBBBBBDD.
BBBBBBDD.
......DD.
CCCCCCC..
.........
[1] Classic Computer Science Problems in Python
[2] davecom/ClassicComputerScienceProblemsInPython
[3] 情報基礎特論: 制約プログラミング入門