厳密被覆問題
Abstract
厳密被覆問題 (exact cover problem) はNP完全のため, 解くためには全探索するしかない. Dancing Linksと呼ばれるデータ構造を利用したKnuthのAlgorithm X (DLX) により, 効率よく全探索することができる.
Explanation
TODO 書く.
Implementation
DLX クラスでは, Dancing Linksと呼ばれるデータ構造を利用している. これは, 4方向連結リストであり, 各ノード DLNode は,
DLNode.left
DLNode.right
DLNode.up
DLNode.down
の4方向のポインタをもつ. 第 i 番目の部分集合の要素 j は, DLNode(i, j) で表現される.
ノードの中には, 集合の要素を表すノードの他にヘッダ (Header) とルートと呼ばれる特殊なノードがある.
ヘッダは, 全体集合の各要素 j について用意されている (Header(j)).
要素 j を含む部分集合がいくつあるかが Header(j).size に記録される.
Header.left, Header.right は, 常にヘッダかルートを指す.
Header(j).up, Header(j).down は, 要素 j をもつ部分集合の要素 j に対応するノードを指す.
ルート Header(-1) は, ヘッダのヘッダである.
Header(-1).left, Header(-1).right は, 常にヘッダか自分自身を指す.
Header(-1).up, Header(-1).down は, 常に自分自身を指す (利用しない).
構築
Input
全体集合の要素数 n_columns
全体集合は, [0, 1, ..., n_columns] であると考える.
部分集合からなる空でないイテラブル rows
各部分集合は空でないイテラブル (i.e., 空集合は許容されない).
Output
イテラブルの要素を格納したDancing Links DLX(n_columns, rows)
Time complexity
全体集合の要素数を$ N, 部分集合の数を$ Mとし, 各部分集合を$ S_i ~ (i = 1, \dots, M)とすると, $ O(N M)time.
厳密被覆の列挙
Input
なし.
Output
全体集合の厳密被覆からなるリスト DLX.exact_covers()
Time complexity
不明.
code:python
class DLNode:
def __init__(self, row, column):
self.row, self.column = row, column
self.up = self.down = self.left = self.right = self
def __repr__(self): return 'DLNode({}, {})'.format(self.row, self.column)
class Header(DLNode):
def __init__(self, column):
super(Header, self).__init__(-1, column)
self.size = 0
def __repr__(self): return 'Header({}; size={})'.format(self.column, self.size)
class DLX:
def __init__(self, n_columns, rows):
self.n_rows, self.n_columns = len(rows), n_columns
self.root = Header(-1)
self.headers = []
self.rows = rows
for j in range(n_columns): self._insert_header(j)
self._construct(rows)
def _insert_header(self, j):
r = self.root
header = Header(j)
header.left, header.right = r.left, r
r.left.right = r.left = header
self.headers.append(header)
def _construct(self, rows):
for i, row in enumerate(rows):
row_header = DLNode(i, row0) self._insert_to_column(row0, row_header) node = DLNode(i, j)
self._insert_to_column(j, node)
self._insert_to_row(row_header, node)
def _insert_to_column(self, j, node):
column_header = self.headersj node.up, node.down = column_header.up, column_header
column_header.up.down = column_header.up = node
column_header.size += 1
def _insert_to_row(self, row_header, node):
node.left, node.right = row_header.left, row_header
row_header.left.right = row_header.left = node
def _cover(self, j): # cover the j-th column
headers = self.headers
# remove the j-th header from the linked list of headers
header.left.right, header.right.left = header.right, header.left
node = header.down
while node is not header:
row_node = node.right
while row_node is not node:
row_node.up.down, row_node.down.up = row_node.down, row_node.up
row_node = row_node.right
node = node.down
def _uncover(self, j): # uncover the j-th column
headers = self.headers
node = header.up
while node is not header:
row_node = node.left
while row_node is not node:
row_node.up.down = row_node.down.up = row_node
row_node = row_node.left
node = node.up
# re-link the j-th header to the linked list of headers
header.left.right = header.right.left = header
def _choose_column(self):
r = self.root
col_header, min_size = r, float('inf')
h = r.right
while h is not r:
if h.size < min_size: col_header, min_size = h, h.size
h = h.right
return col_header, min_size
def exact_covers(self):
r, rows = self.root, self.rows
result = []
stack = [([], None, -1, 0)] # (cover, row, col_idx, status)
while stack:
cover, row, col_idx, st = stack.pop()
if st == 0:
if row is None:
col_header, min_size = self._choose_column()
if col_header is r: result.append([rowsi for i in cover]); continue # feasible elif min_size == 0: continue # infeasible
self._cover(col_header.column)
stack.append((cover, None, col_header.column, 1))
node = col_header.down
while node is not col_header:
stack.append((cover, node, -1, 1))
stack.append((cover + node.row, node, -1, 0)) node = node.down
else:
node = row.right
while node is not row:
self._cover(node.column)
node = node.right
stack.append((cover, None, -1, 0))
else:
if row is not None:
node = row.left
while node is not row:
self._uncover(node.column)
node = node.left
else: self._uncover(col_idx)
return result
Verification
一応きちんと動きはすることは確認したが, 正しい保証はない.
References