知识卡片
组合爆炸限制搜索
组合优化需要在大量可能方案中寻找符合目标的方案,例如安排生产计划或选择路线。随着选择规模增长,候选方案可能急剧增加,逐一搜索的时间和空间成本随之变大;启发式方法可用于寻找较好的方案,但不自动保证全局最优。书中将组合优化一概称为 NP 完全并断言必需指数时间,这一表述过于笼统,不能作为复杂性定理。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第1章 绪论
原书出处 · 1 处
- 绪论 · 查看原书依据
当面对大规模的组合优化问题时,会遇到一个严重的困难,即组合爆炸。
参考来源
- 位置:《现代人工智能技术》第1章《绪论》(来源项目:book-source;源文件:extracted/现代人工智能技术/_epub-src/EPUB/xhtml/chapter3.xhtml)
- 结论依据:原文给出路径、调度等例子,并描述方案数增长造成的搜索成本;卡片对书中复杂性概括保留限制。
- 原始内容:当面对大规模的组合优化问题时,会遇到一个严重的困难,即组合爆炸。这就是说,求解程序所需的时间和空间或者步骤会随着可能性的增加而急剧上升。