知识卡片
二边重连用代价差评估二变换
布线的解是一条经过所有引脚的闭合回路,记作 π₁, π₂, …, πₙ,d 表示两点间距离。2 变换在回路中选两个位置 μ < v,拆掉边 (π_{μ−1}, π_μ) 和 (πv, π{v+1}),改为连接 (π_{μ−1}, π_v) 和 (πμ, π{v+1}),相当于把 π_μ 到 π_v 这一段倒过来走。
其余边都没变,所以新旧路线的长度差只取决于这四条边:
Δf = [d(π_{μ−1}, π_v) + d(πμ, π{v+1})] − [d(π_{μ−1}, π_μ) + d(πv, π{v+1})]
示例(补充演算):四点坐标为 1(0,0)、2(1,1)、3(1,0)、4(0,1),当前回路 1-2-3-4-1,两条对角线交叉,总长 2 + 2√2 ≈ 4.83。取 μ=2、v=3:拆掉 1-2、3-4(各 √2),新建 1-3、2-4(各 1),Δf = 2 − 2√2 ≈ −0.83 < 0,接受。新回路 1-3-2-4-1 总长为 4,与 4.83 − 0.83 一致。
增量计算让每个候选只需算四条边,不必重算整条回路;Δf 再交给 Metropolis 准则决定是否接受。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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`)
- 结论依据:正文使用k=2变换产生新解;未编号的 image_279.svg 描述目标差,比较重连后的两条边与原有两条边的距离和。式(11-1)在 image_281.svg 中描述 Metropolis 接受概率,不是目标差公式。“倒走一段”是由该公式推出的几何含义;四点坐标演算为依据原书公式补充的教学示例,非书中数据。
- 原始内容:因此,可以在当前解的基础上利用 k 的变换( k =2)来产生新解。
- 公式证据:`_epub-src/EPUB/images/image_279.svg`,SHA-256 `16526ce88147018a6458a6c89c6c858a9ba0e80a4ed434f7f95f5c2b3f64744d`;SVG `<desc>` 核对为两条原边与两条新边长度之差。