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

数字电路与系统的计算机辅助设计之六概述数字CAD技术的研究背景数字电路CAD的设计流程CAD的市场现状功耗问题互连问题数字电路CAD问题举例NP问题完全优化方法非完全优化方法非完全优化算法经典算法从搜索的角度可以分两类：n完全优化算法可以保证在解的所有空间中进行搜索，可以找到全局最优解一般只适合求解小规模问题n非完全优化算法在解的部分空间中进行搜索，无法保证在解的所有空间中进行搜索，一般只能得到局部最优解或者近似解一般用于对于大规模问题的求解非完全优化算法近似方法n构造法随机方法n基于局部搜索策略的普通迭代法启发式方法n禁忌搜索法n模拟退火法n遗传算法启发式方法是指一种技术：使得在可接受的计算代价内去寻找最好的解但并不能保证每次都能找到较好的解,更不能保证找到最优解，甚至在多数情况下无法阐述所得解同最优解的近似程度大量的实验数据反映出算法的实际计算性能较好,但理论上并不能证明该算法具有优良的解题性能非完全优化算法构造法（Constructivealgorithm）普通迭代法（Iterativealgorithm）n局部搜索算法（localsearchalgorithm）改进迭代法（Iterativeimprovement）n回溯迭代法（backtrackingiterativeimprovement)n禁忌搜索法（Tabusearch）n模拟退火法（Simulatedannea