サーキット・ツアー制約 ― 1本のループで順番を決める

サーキット・ツアー制約 ― 1本のループで順番を決める#

この章で学ぶこと#

CP-SAT の add_circuit() は、すべての頂点を1回ずつ通る1本のループを作る制約です。経路や順番を決める問題は、これ1つで書けます。

add_circuit() の使い方（辺のリストとブール変数）
通らなくてよい頂点を、自己ループ (i, i) で表す
特定の辺を必ず通す、特定の頂点だけ省く、src → dst の経路を探す
ナイトツアーとグレーコードを、回路として解く

`add_circuit()` とは#

経路やツアーを決める問題は、DNA の断片をどの順でつなぐか、実験の順番をどう組むか、といった場面で出てきます。

add_circuit() は (始点, 終点, ブール変数) のリストを受け取り、変数が真の辺だけを使ったときに、すべての頂点をちょうど1回ずつ通る1本の閉路になることを保証します。

頂点は 0 から連番で指定する（抜けがあると回路が作れない）
(i, i, var) の自己ループを入れると、その頂点を回路から外せる

まず、次の無向グラフで試します。

        graph
0 <--> 1
0 <--> 2
0 <--> 3
1 --> 2
1 <--> 3
2 <--> 3

from ortools.sat.python import cp_model
from helper.ortools import get_all_solutions
import numpy as np

# 無向グラフを、両方向の有向辺にする
edges = [(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3),
         (2, 0), (2, 3), (3, 0), (3, 1), (3, 2)]


def create_circuit_model(edges, include_edges=[]):
    """辺のリストから、回路を探すモデルを作る"""
    edges = set(edges)
    model = cp_model.CpModel()
    if include_edges:
        for edge in include_edges:
            if edge not in edges:
                edges.add(edge)

    variables = {key: model.new_bool_var(str(key)) for key in edges}
    if include_edges:
        # 必ず通す辺は True に固定する
        model.add_bool_and([variables[edge] for edge in include_edges])

    model.add_circuit([(s, e, v) for (s, e), v in variables.items()])
    return model, variables

1つの回路を求める#

solver.solve() で解き、各辺のブール変数の値を取り出します。

model, variables = create_circuit_model(edges)
solver = cp_model.CpSolver()
solver.solve(model)
[(s, e, solver.value(v)) for (s, e), v in variables.items()]

[(0, 1, 0),
 (1, 2, 0),
 (3, 1, 1),
 (0, 3, 0),
 (2, 0, 0),
 (3, 0, 0),
 (2, 3, 1),
 (0, 2, 1),
 (1, 0, 1),
 (3, 2, 0),
 (1, 3, 0)]

True の辺だけを見ると、回路になっているはずです。ただ、この形では読みにくいので、頂点の並びに変換する関数を用意します。

def get_circuit(solution, start=None):
    """True の辺から、頂点の順番を取り出す"""
    # 自己ループ（通らない頂点）は除く
    solution = {s: e for (s, e), v in solution.items() if v and s != e}
    if start is None:
        start = next(iter(solution.keys()))
    path = [start]
    while True:
        if start not in solution:
            break
        start = solution[start]
        if start in path:
            break
        path.append(start)
    return path


def find_all_circuits(edges, include_edges=[], start=None):
    """すべての回路を求める"""
    model, variables = create_circuit_model(edges, include_edges)
    solutions = get_all_solutions(model, variables)
    return [get_circuit(sol, start) for sol in solutions]


def find_one_circuit(edges, include_edges=[], start=None):
    """1つの回路を求める"""
    model, variables = create_circuit_model(edges, include_edges)
    solver = cp_model.CpSolver()
    solver.solve(model)
    sol = {key: solver.value(v) for key, v in variables.items()}
    return get_circuit(sol, start)

すべての回路を表示します。

for circuit in find_all_circuits(edges):
    print(circuit)

[3, 1, 0, 2]
[1, 2, 0, 3]
[0, 1, 3, 2]
[0, 1, 2, 3]

特定の辺を必ず通す#

include_edges に辺を渡すと、その辺を True に固定します。以下は、必ず辺 (2, 1) を通る回路です。

for circuit in find_all_circuits(edges, include_edges=[(2, 1)]):
    print(circuit)

[2, 1, 3, 0]
[2, 1, 0, 3]

頂点を通らなくてよいことにする#

(n, n) という自己ループを辺のリストに足すと、その頂点を回路から外せます。以下は、頂点2と3を省略できるようにした例です。

for circuit in find_all_circuits(edges + [(2, 2), (3, 3)]):
    print(circuit)

[3, 1, 0]
[3, 1, 0, 2]
[1, 2, 0, 3]
[0, 1, 3]
[0, 1, 3, 2]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]

`src` から `dst` への経路を探す#

src から dst への経路は、「dst → src の辺を必ず通る回路」として求められます。経由しない頂点には自己ループを足しておきます。

def find_all_paths(edges, src, dst):
    return find_all_circuits(edges, include_edges=[(dst, src)], start=src)


for path in find_all_paths(edges + [(1, 1), (2, 2)], 0, 3):
    print(path)

[0, 2, 3]
[0, 3]
[0, 1, 3]
[0, 1, 2, 3]

例：ナイトツアー問題#

ナイトツアー問題は「すべてのマスを1回ずつ訪れる」問題なので、回路そのものです。チェスのナイトが1歩で移動できるマス同士を辺にします。

n = 8
moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (-2, 1), (1, -2), (-1, -2), (-2, -1)]
board = np.arange(0, n ** 2).reshape(n, n)

# ナイトが1歩で行けるマスを辺にする
edges = []
for (r, c), v in np.ndenumerate(board):
    for dr, dc in moves:
        r2, c2 = r + dr, c + dc
        if 0 <= r2 < n and 0 <= c2 < n:
            edges.append((int(v), int(board[r2, c2])))

steps = find_one_circuit(edges)

# 何番目に訪れたかを盤面に書き込む
solution = np.zeros((n, n), np.uint8)
for i, step in enumerate(steps):
    r, c = step // n, step % n
    solution[r, c] = i
print(solution)

[[18 39 20 57 16 53  2 55]
 [41 58 17 52 21 56 45  4]
 [38 19 40 15 44  3 54  1]
 [59 42 27 22 51 46  5 10]
 [26 37 60 43 14  9  0 47]
 [31 28 33 50 23  6 11  8]
 [36 25 30 61 34 13 48 63]
 [29 32 35 24 49 62  7 12]]

例：グレーコード#

グレーコードも「1ビットだけ違う数を順に並べる」問題なので、回路で表せます。1ビットだけ違う整数同士を辺にします。

n = 4
bits = {2 ** i for i in range(n)}

edges = []
for i in range(2 ** n):
    for j in range(2 ** n):
        if i != j and (i ^ j) in bits:
            edges.append((i, j))

codes = find_one_circuit(edges, start=0)
for code in codes:
    print(f"{code:0{n}b}")

まとめ#

やりたいこと	書き方
すべての頂点を通る回路	`add_circuit([(u, v, var), ...])`
特定の辺を必ず通す	その辺の変数を `add_bool_and` で `True` に固定（`include_edges`）
頂点を通らなくてよい	自己ループ `(i, i, var)` を足す
`src` から `dst` への経路	`(dst, src)` を必ず通す回路にする
ツアーの順番を取り出す	真の辺をたどる（`get_circuit()`）

頂点は 0 から連番で指定する
自己ループは「その頂点を使わない」という意味になる
ナイトツアーやグレーコードのように、「順番に1回ずつ」という問題は回路に翻訳できる