サーキット・ツアー制約

サーキット・ツアー制約#

ルートやツアーは、従来の経路問題を超えて、さまざまな分野における最適化の課題を解決する上で不可欠です。たとえば、DNA シーケンシングでは、DNA 断片をどの順序で組み立てるかを最適化することが重要であり、科学研究では、実験の再構成を系統的に整理することで、運用コストやダウンタイムを大幅に削減できます。

CP-SAT の add_circuit および add_multiple_circuit 制約を使用すると、さまざまなシナリオを簡単にモデル化できます。これらの制約は、古典的な巡回セールスマン問題 (TSP) を超えて、すべてのノードを訪れる必要がないケースや、複数の独立したサブツアーが求められるシナリオにも対応可能です。この柔軟性により、操作の順序や配置が効率や成果に大きな影響を与える幅広い実用的な問題にとって、極めて有用なものとなっています。

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

サーキット制約#

add_circuit()制約は、有向グラフ内の回路問題を解決するために使用され、ループも許容されます。この制約は (u, v, var) という3つ組のリストを受け取り、u と v はそれぞれ始点と終点の頂点を表し、var はその辺が解に含まれるかどうかを示すブール変数です。

この制約は、True とマークされた辺が単一の回路を形成し、各頂点をちょうど1回ずつ訪れることを保証します。ただし、ループが True に設定されている頂点は例外となります。頂点のインデックスは 0 から始める必要があり、スキップすると回路が成立しなくなるため、頂点の孤立や非実現性を避けるためにも連続した番号で指定する必要があります。

次のグラフを例として、add_circuit()の使い方を説明します。

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

上のグラフには、以下のような辺があります。create_circuit_model()はこれらの辺を利用し、各頂点を1回ずつ訪れる回路を探します。この関数では、edges内の各辺に対してブール変数を作成し、(start, end, variable) のリストを model.add_circuit() に渡します。

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:
        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つの解を求める方法を説明します。各タプルの3番目の要素は、その辺が回路に含まれるかどうかを決定します。

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)]

解を分かりやすくするために、次の get_circuit() で辺の結果を頂点のリストに変換します。また、find_all_circuits() と find_one_circuit() は、全ての回路または1つの回路を求める関数です。

def get_circuit(solution, start=None):
    # 回路の形成に使われる辺のうち、回路に含まれるものを選択し、自己ループは除外
    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):
    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]

特定の辺を回路に必ず含めるためには、(start, end, True) を add_circuit() に渡すか、その辺を表すブール変数を add_bool_and() で 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, 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]
[0, 1, 3]
[0, 1, 3, 2]
[0, 1, 2, 3]
[0, 1, 2]

特定の頂点 src から特定の頂点 dst までのルートを探すためには、辺 (dst, src) を必ず回路に含めるようにします。また、頂点 1 と 2 はルートに含まれなくてもいいので、(1, 1) と (2, 2) を辺リストに追加します。以下のコードは、find_all_paths() 関数を使って、src から dst までのルートを探す方法です。

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]

ナイトツアー問題#

ナイトツアー問題を解くために add_circuit() を使用するコードは非常に適切です。ナイトがすべてのマスを一度ずつ訪れるように回路を作成する方法を示しています。以下に、ナイト・ツアー問題のコードを説明します。

directs にはナイトが一歩で移動できる8つの方向を示すタプルを格納します。
各マスに対して、ナイトが移動可能な隣接するマスを探し、その辺を edges リストに追加します。
find_one_circuit(edges) を呼び出して、ナイトがすべてのマスを一度ずつ訪れる回路を求めます。
解として得られた各ステップを基に、ナイトが通った順番を盤面に埋め込み、solution 配列として表示します。

n = 8
directs = [(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)

edges = []
for (r, c), v in np.ndenumerate(board):
    for dr, dc in directs:
        r2, c2 = r + dr, c + dc
        if 0 <= r2 < n and 0 <= c2 < n:
            v2 = board[r2, c2]
            edges.append((int(v), int(v2)))

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)

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

グレーコード#

グレーコード問題もナイト・ツアー問題と同じく、回路を探す問題として表現できます。ここでは、1ビットしか差がない二つの整数を辺として edges に追加し、find_one_circuit(edges) を使用してグレーコードの解を見つけます。以下にその詳細を説明します。

各整数 i と j に対して、1ビットだけが異なる場合（i ^ j が bits に含まれる場合）に、(i, j) を edges に追加します。
find_one_circuit(edges) を使って、グレーコードに基づいた回路を探します。

n = 4
edges = []

bits = set([2**i for i in range(n)])

for i in range(2**n):
    for j in range(2**n):
        if i != j:
            if 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}")

サーキット・ツアー制約

Contents

サーキット・ツアー制約#

サーキット制約#

ナイトツアー問題#

グレーコード#