4.3 分布式问题求解与 DCOP

4.3 分布式问题求解与 DCOP：力往一处使

摘要：当任务没法切成独立小块分人，问题本身就成为一张牵连的网——分布式问题求解（DPS）与它的现代形态 DCOP（分布式约束优化）为此而生。本节讲 DPS 的三段式（分解、分配、结果共享），把集日排期问题翻译成 DCOP 四元组，实现同步分支定界与 DSA 局部搜索并对比解质量与消息开销。

「把难题拆开分给各家，再把答案拼起来」——这句话说起来轻巧，做起来处处是坑。第 4 章前两节处理的都是"能拆的活"，这一节处理拆不开的：全镇要排一张集日表，每个摊主能去的日子不同，同行摊主还最好错开，酒馆赶集日必须有人在——每家的选择都牵动别家。这类"牵一发动全身"的问题是协作的最深水区，也是市政厅之行的最后一站；它同时收编旧教程"分布式问题求解"一讲的全部内容。

DPS 老三样：分解、分配、结果共享

分布式问题求解是上世纪研究者交出的第一代答案，三段式流程：任务分解（把大问题拆成子问题，尽量切在耦合最少的地方）、子问题分配（按能力与负载派给镇民，第 4.1 节的家什）、结果共享（各家的部分解汇总拼装，矛盾处再协调）。结果共享有三种经典模式：综合模式（中心节点收集全部部分解再拼）、黑板模式（公共墙上贴便签，谁有素材谁贴，谁凑齐谁取）、协商修正模式（部分解之间直接交换意见互相修改）。黑板模式影响深远——现代智能体共享内存、协作文档、甚至大模型智能体的共享上下文本，血脉里都有它。

DPS 的哲学是"为了并行而分布"：问题本身是中心的，只是算力不够才拆开。而 DCOP 的哲学是"为隐私与自治而分布"：信息本来就长在各家（摊主不肯公开自己的全部偏好），必须让求解过程本身分布式进行。

DCOP：把牵连网写成四元组

DCOP 把这类问题写成四件套：变量（每家一个决策——摊主选哪天出摊）、值域（可选的集日）、约束（两家之间的搭配限制——同行错开、酒馆须同日）、成本函数（每种搭配的代价）。每个变量归一个镇民持有，镇民只跟约束网上的邻居通信，目标是让全表总成本最小。它的前身是分布式约束满足（DisCSP，只求可行解），加上优化目标后成为当代协调的主力模型——传感器分配、会议排期、频谱分配都用它。

图 4-2 集日排期问题的约束网（DCOP 因子图）

求解一代：完备算法（同步分支定界）

DCOP 的完备算法保证找到全局最优，代价是指数级消息与内存。同步分支定界（SynchBB）把约束网拍成一条线，变量按序取值：轮到谁，谁在自己的值域里挑当前上下文下最好的值，把部分成本往后传；后面的变量带着"前面已花多少"的账继续挑。找到第一个完整解得到上界，此后部分成本一旦越界立刻剪枝。完备但娇贵——变量一多，回合数与消息量都吃不消。建模时还有条隐蔽的纪律：成本必须非负。"同日佳"的奖励若写成负成本，剪枝会错杀后劲之路（后面的负账还能把总分拉回来）；正确写法是把奖励改记为"异日罚"，下面代码里的约束账本就是这么记的。

DOMAINS = {"菜摊": ["周一", "周三"], "鱼摊": ["周一", "周五"],
           "酒馆": ["周三", "周五"], "布摊": ["周三", "周五"],
           "肉摊": ["周一", "周三"]}

# 二元约束成本：两家搭配情形的加账（全部非负，"同日佳"改记为"异日罚"）
COSTS = {("菜摊", "鱼摊"): {"同": 4, "异": 0},   # 同行宜错开
         ("鱼摊", "酒馆"): {"同": 0, "异": 3},   # 同街同日省运费
         ("菜摊", "布摊"): {"同": 0, "异": 2},   # 相邻摊异味扰邻
         ("鱼摊", "布摊"): {"同": 0, "异": 1},   # 供货同日省一趟车
         ("酒馆", "肉摊"): {"同": 0, "异": 2},   # 配套客流同日佳
         ("布摊", "肉摊"): {"同": 5, "异": 0}}   # 同类摊位竞争

ORDER = list(DOMAINS)

def pair_cost(a, va, b, vb):
    key = (a, b) if (a, b) in COSTS else (b, a)
    if key not in COSTS:
        return 0
    return COSTS[key]["同" if va == vb else "异"]

def total_cost(assign):
    return sum(pair_cost(a, assign[a], b, assign[b])
               for i, a in enumerate(assign) for b in list(assign)[i+1:])

def synch_bb():
    """同步分支定界：按固定顺序逐变量取值，越界剪枝。"""
    best, best_cost = None, float("inf")
    def dfs(i, assign, acc):
        nonlocal best, best_cost
        if acc >= best_cost:               # 剪枝：部分成本已超上界
            return
        if i == len(ORDER):
            best, best_cost = dict(assign), acc
            return
        var = ORDER[i]
        for v in DOMAINS[var]:
            extra = sum(pair_cost(var, v, p, assign[p]) for p in assign)
            assign[var] = v
            dfs(i + 1, assign, acc + extra)
            del assign[var]
    dfs(0, {}, 0)
    return best, best_cost

plan, cost = synch_bb()
print("最优集日表:", plan, "总成本:", cost)
​

跑出来的是全局最优的集日表。注意每个变量只跟约束网上的邻居"算账"——换成多进程版本，就是货真价实的分布式分支定界，只是这里用单进程演示搜索骨架。

求解二代：局部搜索（DSA）

完备算法贵，日常工程多用局部搜索。DSA（分布式随机算法）的循环是：每轮各镇民看邻居的当前取值，若有"能让我跟邻居的总账更便宜"的备选值，就按概率换过去；否则不动。几轮下来系统大多会稳定在某个局部最优。不保证最优，但消息量小、随时可停。

import random

def dsa(rounds=12, p=0.7, seed=1):
    random.seed(seed)
    assign = {v: random.choice(DOMAINS[v]) for v in ORDER}
    messages = 0
    for r in range(rounds):
        changed = False
        for var in ORDER:
            cur = sum(pair_cost(var, assign[var], n, assign[n])
                      for n in ORDER if n != var)
            best_alt, best_alt_cost = assign[var], cur
            for v in DOMAINS[var]:
                if v == assign[var]:
                    continue
                c = sum(pair_cost(var, v, n, assign[n])
                        for n in ORDER if n != var)
                if c < best_alt_cost:
                    best_alt, best_alt_cost = v, c
            if best_alt != assign[var] and random.random() < p:
                assign[var] = best_alt     # 换值：向邻居广播新取值
                messages += len(ORDER) - 1
                changed = True
        if not changed:
            break
    return assign, total_cost(assign), messages, r + 1

assign, cost, msgs, rounds_used = dsa()
print("DSA 局部解:", assign, "总成本:", cost,
      f"消息 {msgs} 条, 用 {rounds_used} 轮")
bb_cost = synch_bb()[1]
print("与最优差:", cost - bb_cost)
​

多次运行你会看到：DSA 有时碰到全局最优，有时停在离最优一两分的局部解上，多跑几轮或调高换值概率能改善但不保证。完备与廉价，工程上常常选择后者再加质检——先 DSA 出方案，人工或定时用完备算法复核关键场景。

⚠️ 常见坑：把 DCOP 当万能协调器。约束网稠密时（家家有牵连）任何算法都吃不消，先做"约束简化"（去掉恒不紧的约束、合并等价变量）再上求解器；值域大时还要考虑值抽象。建模的功夫常比求解的功夫值钱。

💡 关键直觉：DPS 到 DCOP 的演化史，一句话概括——从"把问题分给人"到"把问题变成网，让人变成节点"。前者是工程捷径，后者是理论地基；第 9 章巡礼里的传感器网络与频谱分配，都是这张网上的真实街区。

沙盘推演小结

集日表挂上了公告栏：完备算法夜里跑出最优版存档，日常微调交给 DSA 在线响应摊主的临时变动。市政厅之行至此收官——分工、同心、合力三关都过了。但小镇并不总是温情脉脉：下个月枯水期，水井边的冲突就要压不住了。下一章进调解法庭：抢资源、查冲突、记信用，全是硬碰硬的戏码。