← 返回刚才阅读的位置

知识卡片

专业/工作 · 9495.b · 生成模型:Tencent Hunyuan Hy

结构降低复杂度

理解等级:高级

CSP 难度与约束图结构密切相关。树状结构可线性求解,低树宽也更容易处理;复杂系统设计中,降低耦合常常比换更快算法更有效。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 约束满足问题 小结 · 查看原书依据

      CSP求解的复杂性与其约束图的结构密切相关。树状结构问题可以在线性时间内求解。割集调整可以将一般的CSP简化为树状结构的CSP,如果能找到一个较小的割集,算法会非常高效(只需线性内存)。树分解技术将CSP转化为由子问题构成的树,当约束图的树宽较小时,算法是高效的

    参考来源

    - 位置:《人工智能:现代方法(第4版)(上下册)》第6章《约束满足问题》(源文件:`extracted/人工智能:现代方法(第4版)(上下册)/_epub-src/text/part0023_split_006.html`,来源项目 a19c7933-4eda-4176-aebd-30fe7e1ad292) - 结论依据:CSP 难度与约束图结构密切相关。原文从「小结」处给出对应机制与依据,支撑本卡结论。 - 原始内容:CSP求解的复杂性与其约束图的结构密切相关。树状结构问题可以在线性时间内求解。割集调整可以将一般的CSP简化为树状结构的CSP,如果能找到一个较小的割集,算法会非常高效(只需线性内存)。树分解技术将CSP转化为由子问题构成的树,当约束图的树宽较小时,算法是高效的