← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3762.b

总体布线可转成斯坦纳树问题

理解等级:高级

把布线区域作图的顶点、区域间连通的电路作图的边后,一个线网要把若干引脚连通,就是在图上找一棵连通这些点、总长尽量短的树。这正是斯坦纳树问题:用最短的总连线把指定的若干点连通,必要时可以经过不属于这些点的中间点(例如线网途经的其他区域)。

与只连两个点的最短路径不同,多点连通时“经过哪些中间点”的组合数随规模急剧增长。斯坦纳树问题是 NP-hard 的,没有已知的高效方法能保证找到最优结果,所以工程方案通常要在布线质量与计算预算之间取舍。难解性只说明精确求解代价高,不能据此断言某个启发式必然更优。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 1 . 3 . 1 集 成 电 路 布 线 · 查看原书依据

      总体布线算法将区域定义为图的顶点,区域之间连通的电路定义为图的边,这样总体布线问题就转化为图论中的斯坦纳树(Steiner tree)问题。然而,所有的斯坦纳树问题都是NP-hard问题,没有高效的办法找到最优的结果[27]。

    参考来源

    - 位置:《智能算法导论》第11章《1 1 . 3 . 1 集 成 电 路 布 线》(源文件:`_epub-src/EPUB/xhtml/chapter11_0007.xhtml`) - 结论依据:正文将区域抽象为顶点、区域间的连通电路抽象为边,进而把总体布线转化为斯坦纳树问题,并说明该问题NP-hard且没有高效的最优求解办法。 - 原始内容:总体布线算法将区域定义为图的顶点,区域之间连通的电路定义为图的边,这样总体布线问题就转化为图论中的斯坦纳树(Steiner tree)问题。然而,所有的斯坦纳树问题都是NP-hard问题,没有高效的办法找到最优的结果