D3第 6 / 6 节 · 约 45 分钟

约束求解与路线整合:满足要求还是优化目标

本节目标
  • 把布置要求转成变量、取值与约束
  • 区分无解、可行解和最优解并组合适当路线

不是所有问题都要预测答案

星河玩具展要把纸船、木方块和玻璃星球放到甲、乙、丙三个展台,每台只放一件。纸船不能放甲台,玻璃星球必须在带软垫的乙台,木方块不要与纸船挤在同一台。这些要求可以直接写成约束满足问题,而不必训练一个模型猜布置。变量是三件玩具各自的展台位置,取值范围是允许的展台,约束限制哪些组合合法。先把条件表达清楚,再用枚举或专门求解方法寻找满足全部硬要求的组合。

逐步缩小可能组合

玻璃星球固定在乙台,其他玩具不能再选乙;纸船不能选甲,因此只剩丙;木方块只能放甲。这样的推导称为约束传播的直觉形式:确定或缩小某变量范围后,再影响其他变量。较复杂问题中可能需要尝试一项选择,发现矛盾后回溯换另一项。求解器能在给定变量、范围与条件下查找方案,但若条件漏写,就可能返回人们不满意的合法组合。合法是相对于模型定义,不是对现实全部要求的自动保证。

硬约束和软目标别混淆

必须有软垫、每台容量不超过一件属于硬约束,不允许违反。希望同系列玩具靠近或搬运步骤少可以写成软偏好或优化目标,在多个可行方案中比较好坏。找到可行解只证明某组要求被满足,不证明目标最好;证明最优需要适当搜索条件、界限或算法支持。若突然规定玻璃星球也不能放乙,就与必须放乙冲突,问题无解。应解释冲突条件并请求修改,不偷偷牺牲硬约束来装作成功。

把六条路线摆到合适位置

展览可先用知识图谱整理玩具系列与当前位置,用规则推导哪些玩具需要软垫,用约束求解分配展台,再用规划安排清理和搬运顺序。材质不确定时可用概率表示证据强弱,而不是直接当事实;若要判断提示牌能否改善访问,需要因果设计而非仅搜索。不同方法共享数据时,要保持来源、未知值与时间一致。生成式模型可以协助把要求写成草稿,但正式约束仍需核对,流畅表达不是满足条件的证明。

综合作品应展示验证过程

工坊把最终分配、动作前提和未知事项分别列出,逐条检查硬要求,再解释优化偏好是否被满足。若模型给出文字方案,可独立核对每件玩具恰好一个位置、每台容量和软垫条件,不能只相信看起来合理的叙述。练习规模很小,纸笔即可;大规模问题的计算复杂度可能很高,需要限定规模或接受近似,但近似优化也不意味着硬要求可以随意违反。选择路线的标准是问题结构与可验证性,而不是把所有模块都堆进去。

本节要点

  • 约束满足找合法组合,优化在合法组合中比较目标
  • 无解应报告冲突,不能悄悄违反硬要求
  • 知识组织、规则、约束与规划可以合作但各有明确职责

动手练习:解出布置方案并解释一次无解

  1. 设纸船、木方块、玻璃星球的位置为变量,取值甲乙丙,列出全部硬约束
  2. 推出玻璃星球乙、纸船丙、木方块甲,并逐条检查
  3. 加入玻璃星球不能放乙的要求,指出最小直观冲突并说明应怎样请求澄清

自查清单

  • 变量、范围与互不相同约束完整
  • 方案逐条满足原始硬条件
  • 无解解释直接指出冲突且不私自放松要求
先自己做,再查看参考答案

变量分别为三件玩具的展台,范围甲、乙、丙,每个变量只能取一个值,三个值互不相同;玻璃星球必须乙,纸船不能甲。由玻璃星球占乙,纸船不能乙且不能甲,只能丙,木方块因此为甲,每台一件的要求也满足。纸船与木方块不同台已被互不相同约束覆盖。加入玻璃星球不能乙后,它既必须乙又禁止乙,单就这两条已直接矛盾,任何完整分配都无法满足。应报告这组冲突,询问是否增加另一个带软垫展台或修改禁止条件,不擅自把玻璃星球放无垫处。此处得到的是可行方案,若没有定义其他目标,就无需虚构最优分数。

本节自测

学完了吗?

标记后会记录在本机浏览器,课程首页显示你的进度。