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

数字电路与系统的计算机辅助设计之六
概述

数字CAD技术的研究背景
数字电路CAD的设计流程
CAD的市场现状
功耗问题
互连问题
数字电路CAD问题举例
NP问题
完全优化方法
非完全优化方法
 非完全优化算法

经典算法从搜索的角度可以分两类：
n 完全优化算法
可以保证在解的所有空间中进行搜索，可以找到全
局最优解
一般只适合求解小规模问题
n 非完全优化算法
在解的部分空间中进行搜索，无法保证在解的所有
空间中进行搜索，一般只能得到局部最优解或者近
似解
一般用于对于大规模问题的求解
 非完全优化算法

近似方法
n 构造法
随机方法
n 基于局部搜索策略的普通迭代法
启发式方法
n 禁忌搜索法
n 模拟退火法
n 遗传算法
 启发式方法

是指一种技术：使得在可接受的计算代价内去寻
找最好的解

但并不能保证每次都能找到较好的解 ,更不能保证
找到最优解，甚至在多数情况下无法阐述所得解
同最优解的近似程度

大量的实验数据反映出算法的实际计算性能较好 ,
但理论上并不能证明该算法具有优良的解题性能
 非完全优化算法

构造法（Constructive algorithm）
普通迭代法（Iterative algorithm）
n 局部搜索算法（local search algorithm）
改进迭代法（Iterative improvement）
n 回溯迭代法（backtracking iterative improvement )
n 禁忌搜索法（Tabu search）
n 模拟退火法（Simulated annea