文档介绍：A题大规模集成电路中模块的定位问题
将n个模块置入一个正方形集成电路板C中,每个模块有几个接线端,这些接线端要与另外的某些模块的接线端连接,或者和C的周界上的输入/输出(I/O)端口连接,输入/输出端口的位置是固定的并且已知。可假设C={(x,y) | -1£x£1, -1£y£1}, 我们需要确定这些模块(假设不考虑模块的大小,即将其看作点)在C中的位置,使连接线路的总长最小。图1给出了一个3个模块,6条连线,4个输入/输出端口的例子。
图1 正方形电路板中的3个模块和6条连线
就以下几种情况建立相应的确定n个模块位置的数学模型。
用模块间的欧几里得距离l2作为其连线的长度;
用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度;

用模块间的修正曼哈顿距离d作为其连线的长度;
其中h为一个分段线性函数,h(z)=max{z,-z, g}, g是正常数
h(z) 的函数图如图2所示。
图2 分段函数h(z)
如果用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度,但不是最小化总长度,而是最小化最长连线的长度。
另外,为简便起见,考虑一维的情况,即将模块置入区间[-1, 1]. 。在data1中给出了实例1:50个模块,150条连线的数据,data2中给出了实例2:100个模块,300条连线的数据,两个实例中任选一个给出上述四个模型的解,并进行比较。要求
· 分别画出每个解中n个模块的位置的直方图。
· 分别画出连线长度的直方图。
· 计算四个模型得到的解的总长度和最长连线的长度
· 前面均未考虑模块的大小,实际上,我们必须考虑模块间的重叠,,就认为两模块重叠。对四个模型得到的解分别计算其有多少对模块重叠以及占总对数n(n-1)/2的百分比。
进一步,考虑使连线的总长度和模块的重叠数均要尽可能小的问题。
讲义:
对于有一定规模的题,一般情况是先求解小规模的题目,其目的在于:能较快的理解题目意思,发现解决问题的关键,计算简单,易于验证方法的正确性。只要有可能,大家尽可能的先减少问题的规模。
对于本题,尽管题目没有要求解决三个点的布置问题,但是你应当从三个点的问题开始。
为书写方便,不妨将边界上的点记为(ai,bi),i=1,2,3,4。对应与几个问题,可以列出模型分别为:
1,用模块间的欧几里得距离l2作为其连线的长度;

问题为一个无约束问题,可以利用任意一种优化软件进行求解。
2,用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度;

用模块间的修正曼哈顿距离d作为其连线的长度;
目标函数类似,这里省略。
4,如果用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度,但不是最小化总长度,而是最小化最长连线的长度。
。
总结起来,就是求一个无约束问题的极小值。