Upd: 代码来了 https://github.com/laekov/rbrrm
来 mark 一下我的 oop 组队大作业中窝肝的部分.
姚氏大作业果然有趣.
大概问题是这样的.
现在一个 pcb 上面有 (n*n) 的元件矩阵(忽略元件面积). 然后你要布线让每个元件都单独连着一条通往边界的电线, 我们管它叫这个点的 escape 路线. (最边上的就直接算作逃出去了)
然后电线只能横竖沿着格线走. 显然直接走是走不出去的. 所以你要找一个最小的 ( w ), 把原来的每行每列的中间都插上(w)条格线, 然后找一个总长最小 (或者如果你有其它的 feature 的话可以是尽量小) 的方案.
官方的的范围是 ( 80 ), 然后我算出来的 (80) 对应的 (w) 是 (23). 这个范围直接二分建图跑网络流已经非常吃力了. (或者直说要跑几天才跑得出来).
一个比较小的例子如图.
这个问题的标题叫作_rule based regular routing path_, 也就是说有某种直接用规则布线就可以了?
然后窝的第一个想法是神贪心, 然而在和大树讨论了很久之后也没有找到一种能让我们两个觉得靠谱且简洁优美的贪心.
然后窝就在想网络流是否有救. 在和 czr 讨论了一阵以及 czr 帮窝去 ieee 找了几篇 paper (btw, 校内网可以免费直接下 ieee 的论文不能更赞) 后发现了这么一个结论. 对于每个 ( w*w ) 的格子, 它的承载上限 (也就是说穿过这个格子的线的条数) 是 ( w ).
而且没毛病的话没有线会从这个格子的某条边进来又出去. 如果有的话那么这条边的另外一边也应该是同样的情况. 这时两边都有进有出了, 怎么办? 那当然是选择消圈啦. 消掉圈之后不会对解产生影响.
大概每个格子都会长成这个样子.
其中只有四周的红点是有电子原件的, 而紫色的点是新建的 ( w * w ) 的格子的边界.
然后下一个问题是相邻的格子怎么连起来呢? 如果跑出 ( w ) 之后直接搜的话可能能搜出比较短的路, 但是感觉巨麻烦, 而且不一定能满足所有点都能逃出去.
于是窝找到了一个比较_rule based_ 的方法. 就是上面那张图.
对于每个格子, 我们已经知道从每条边进来 / 出去多少个线头了. 于是我们约定对这个格子的边界顺时针走. 从正方形的四个顶点开始连续地给线头. 而它的上下左右的四个格子就逆时针, 然后上下左右的上下左右再顺时针, 就像一个国际象棋的棋盘一样, 黑格子顺, 白格子逆这样. 这个方案是肯定可以保证(w)根线头都接上的.
然后每个格子里再暴跑一个网络流不就好了嘛? 然后就有了下面这玩意.
那个突出来的玩意是什么鬼!?
然后发现 dinic 在退流的时候会留下一些环流. 于是输出方案的时候要记得重新 BFS 一遍.
下一个问题是这些顶点. 它们好像既不属于边也不属于点. 它们怎么进来图里啊 qwq.
显然它必需要上下左右走, 于是会走到一条边上, 然后从这条边拐进每个格子. 所以直接把它向它的上下左右的边连个线就好喽?
然后就出现了下面这一幕.
它它它, 断了!?
这个 (w=4)的格子确实满足入和出都不超过四个. 但是它居然不能成功地布线!?
那天晚上hja的内心是绝望的.
这个问题就出在左下那个元件, 因为它多占用了这条边的第一个位置, 但是在上面这个格子并不知道这条信息, 所以它还天真地认为任意 (w) 个线头都能完美地通过它. 然而它已经被别了.
hja一度十分绝望. 然后hja发现一个奇妙的性质. 出现上面的情况仅当这个点的接入点是从某个顶点开始的一串线头的第一个. 因为它会导致这个格子里后面的线头都依次向中间移动一格, 从而导致移不出去.
那么强行让每个顶点连出去的线都是最后一个可不可以呢? 因为上面那个奇怪的接线方式 (顺逆时针交替), 不难发现每个格子要么是上下的起点, 要么是左右的起点, 所以总有一个方向是一串线的尾巴的方向. 那么让这个点只能从这个方向进格子就可以了?
实验了一下发现是可以的. 想了一下道理是这样的. 考虑一个顶点( (0, 0) )要进到( (1, 1) ). 不管它走( (1, 0) )还是( (0, 1) ), 另外一个格子都是废掉的. 所以只从上下 / 左右中的一个方向进格子是完全不影响答案的.
所以就成功地找到了一种合法且(w)最小的布线方案.
然而这种方案好像巨浪费.
拿张 (80)的图感受一下 .
还有 (120)的. (可能会导致设备卡)
因为那个旋转式的布线, 导致在比较稀疏的地方会有类似方便面一样拐来拐去的东西, 然后长度巨长.
但是比较密集的地方就没有问题.
所以它到底有多浪费?
用费用流跑到(26)就再也跑不动了. 然后结果大概是这样的.
(发现之前统计的时候统计错了)
n rule best ratio
2 3 3 100.000%
3 12 12 100.000%
4 29 29 100.000%
5 58 56 103.571%
6 162 131 123.664%
7 248 208 119.231%
8 362 322 112.422%
9 718 560 128.214%
10 955 779 122.593%
11 1259 1076 117.007%
12 2096 1621 129.303%
13 2591 2100 123.381%
14 3244 2737 118.524%
15 3980 3552 112.050%
16 5813 4672 124.422%
17 6912 5824 118.681%
18 8198 7237 113.279%
19 11294 9112 123.946%
20 13160 11009 119.539%
21 15271 13244 115.305%
22 17682 15857 111.509%
23 22788 19048 119.635%
24 25967 22394 115.955%
25 29563 26224 112.733%
(n)大了之后会导致图片没法输出. (100k分辨率的图片画面太美)
所以窝造了一个不显示细节而是以颜色深度表示线的密度的输出方式.
然后花了四十分钟跑了一个(200200)的东西, 顺便制造了2.3GB的边输出文件, 总共有大概(1.1310^8)的长度.
效果如图.
大概窝就能做这些了. 其实可以再造一个能缩放的图形界面, 动态加载细节的.
不过懒得做了.
大概就这样了吧.
大概也是有个千行代码的.
窝好菜啊qwq.
等ddl过了再把代码放出来.
队友: 于是泥就是造了个壁纸生成嚣嘛.
放送一张2k的壁纸. 价值2h.
