← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3762.d

布线循环排列最小化总线长

理解等级:中级

该退火布线模型把 n 个待连接引脚看成点,解是访问全部点再回到起点的循环排列:πᵢ = j 表示第 i 个访问的点是 j。用距离矩阵 D 把相邻点的距离加总,目标是总路径最短。新解由当前回路做 2 变换产生,再用 Metropolis 准则决定是否接受。这是为搜索构造的简化模型;实际芯片还需同时满足可布通、层数和电学等约束。

补充教学示例(非书中数据)。四点 1(0,0)、2(1,0)、3(1,1)、4(0,1),回路 1-2-3-4-1 的边长都是 1,总长 4;回路 1-2-4-3-1 含两条对角线,总长 2+2√2 ≈ 4.83,更长。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 1 . 3 . 2 优 化 目 标 · 查看原书依据

      首先,假设布线的引脚的个数为n,解空间S={(π,π,…,πn)}表示点{1,2,…,n}的所有循环排列,其中每一个循环排列会遍历n个点形成一条回路,πi=j表示第i个访问的点是j点,且要求πn=π,因此,可以在当前解的基础上利用k的变换(k=2)来产生新解。

    参考来源

    - 位置:《智能算法导论》第11章《1 1 . 3 . 2 优 化 目 标》(源文件:`_epub-src/EPUB/xhtml/chapter11_0008.xhtml`) - 结论依据:正文把布线表示为遍历 n 个引脚的循环排列,以距离矩阵计算路径长度并以总长最小为目标。四点坐标演算为依据该模型补充的教学示例,非书中数据。 - 原始内容:解空间 S ={( π , π ,…, π n )}表示点{1,2,…, n }的所有循环排列,其中每一个循环排列会遍历 n 个点形成一条回路, π i = j 表示第 i 个访问的点是 j 点,且要求 π n = π ,因此,可以在当前解的基础上利用 k 的变换( k =2)来产生新解。