知识卡片
结构降低复杂度
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转化为由子问题构成的树,当约束图的树宽较小时,算法是高效的