摘要
本发明提供了一种面向多约束问题的行内最优填充单元插入算法，涉及集成电路设计自动化领域，用于在满足多种设计规则的情况下，高效地插入填充单元；获取填充位置信息、填充类型信息和填充约束代价等建模参数，利用这些参数构建一个多层级的解空间树，其中每个叶结点代表一种可能的填充方案；采用动态规划算法自上而下遍历解空间树，并根据填充约束代价进行预剪枝操作，以减少搜索空间；利用回溯算法找到累计违规数量最小的结点，并通过父结点指针回溯到根结点，得到最优填充单元插入方案；利用填充约束代价的局限性进行预剪枝操作，降低了算法的时间复杂度和空间复杂度，提高算法效率。
