巡回路约束：用一条闭合回路来决定访问顺序

巡回路约束：用一条闭合回路来决定访问顺序#

本章的内容#

CP-SAT 的 add_circuit() 用来构造一条把全部顶点各经过一次的闭合回路，凡是决定路径与顺序的问题，都可以用它写出整个模型。

add_circuit() 的用法，即边与布尔变量组成的列表
可以不经过的顶点，用自环 (i, i) 表示
必须经过某条边、只省掉某些顶点、寻找 src → dst 的路径
把骑士巡游与格雷码当作回路来解

什么是 `add_circuit()`#

决定路径与巡回路线的问题，会出现在 DNA 片段的连接顺序、实验的排列顺序这类场合，而 add_circuit() 正是为这类问题准备的。这些问题的共同点是每个顶点只被用到一次，并且首尾相接。

add_circuit() 接收 (起点, 终点, 布尔变量) 的列表，保证在只使用变量为真的边时，形成一条把全部顶点各经过一次的闭合回路。

顶点要按 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

求出一条回路#

用 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):
    """从为真的边取出顶点的顺序"""
    # 去掉自环（不经过的顶点）
    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]

必须经过指定的边#

把边传给 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]

例：骑士巡游问题#

骑士巡游问题要求把每一格都访问一次，因此它本身就是一条回路。把国际象棋的骑士一步能够到达的格之间连成边即可。8×8 的棋盘有 64 个顶点，每个顶点最多有 8 条边。

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)

# 把骑士一步能走到的格子连成边
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)

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

例：格雷码#

格雷码要求把只差一位的数依次排开，因此也可以用回路表示。把只差一位的整数之间连成边即可。4 位时顶点是 0 到 15，边连接二进制只差一位的那些数。

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 开始连续编号
自环表示不使用这个顶点
骑士巡游与格雷码这类依次各访问一次的问题，都可以翻译成回路