数字电路与系统的计算机辅助设计之四

数字电路与系统的计算机辅助设计之四
概述
数字CAD技术的研究背景
数字电路CAD的设计流程
CAD的市场现状
功耗问题
互连问题
数字电路CAD问题举例
NP问题
完全优化方法
非完全优化方法



2004-09-30 2
 完全优化(complete optimization)算法

对全部解空间进行搜索
只要有最优解存在，就一定能找到
对于一些问题，求解可能很慢
比较容易理解时间复杂度




2004-09-30 3
 完全优化算法
穷举法（Enumeration)
分枝定界法（Branch and bound）
动态规划法（Dynamic programming）
整数线性规划法（Integer-linear programming ）




2004-09-30 4
 完全优化算法
穷举法（Enumeration)
分枝定界法（Branch and bound）
动态规划法（Dynamic programming）
整数线性规划法（Integer-linear programming ）




2004-09-30 5
 穷举法

列出所有可能的解
当问题规模n很大时，非常慢
当问题规模n很小时，或许是不错的选择




2004-09-30 6