文档介绍：2007年A题评讲
温罗生
题目回顾
题目:大规模集成电路中模块的定位问题
将n个模块置入一个正方形集成电路板C中,每个模块有几个接线端,这些接线端要与另外的某些模块的接线端连接,或者和C的周界上的输入/输出(I/O)端口连接,输入/输出端口的位置是固定的并且已知。可假设C={(x,y) | -1x1, -1y1}, 我们需要确定这些模块(假设不考虑模块的大小,即将其看作点)在C中的位置,使连接线路的总长最小。图1给出了一个3个模块,6条连线,4个输入/输出端口的例子。
图1 正方形电路板中的3个模块和6条连线
就以下几种情况建立相应的确定n个模块位置的数学模型。
1,用模块间的欧几里得距离l2作为其连线的长度;
2,用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度;
3,用模块间的修正曼哈顿距离d作为其连线的长度;其中h为一个分段线性函数,h(z)=max{z,-z, }, 是正常数
4,如果用模块间的曼哈顿距离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(直折线距离)作为其连线的长度;
3,用模块间的修正曼哈顿距离d作为其连线的长度;
目标函数类似,这里省略。
4,如果用模块间的曼哈顿距离l1(直折线距离)作为其连线的长度,但不是最小化总长度,而是最小化最长连线的长度。
总结起来,就是求一个无约束问题的极小值。直接求解上面的问题,只要会使用任何一种优化软件,都能顺利的解决。
特点分析:目标函数连续但是不可微,书写复杂。特别是随问题的规模增大,输入变得无法忍受。
对题目的修改
本人认为,题目所给出的数据不是很合适,为使题目更有意义,后面部分做如下的修改:对端口进行编号,在给出每个端口的坐标位置(类似与三个模块四个端口的数据)。其他条件不变。
Matlab的方法
要解决本题,你至少应该以一个你认为比较简单的问开始,并先以少量数据进行实验,并且在编程时注意模型的可扩展性。这里以欧氏距离为例说明问题。
第一步:数据
类似与DATA中的数据格式,如下给出数据。