将n个模块置入一个正方形集成电路板C中，每个模块有几个接线端，这些接线端要与另外的某些模块的接线端连接，或者和C的周界上的输入/输出（I/O）端口连接，输入/输出端口的位置是固定的并且已知。可假设C={(x,y) | -1£x£1, -1£y£1}, 我们需要确定这些模块（假设不考虑模块的大小，即将其看作点）在C中的位置，使连接线路的总长最小。
就以下几种情况建立相应的确定n个模块位置的数学模型。
1．
用模块间的欧几里得距离l2作为其连线的长度； 2．
用模块间的曼哈顿距离l1（直折线距离）作为其连线的长度； 3．
用模块间的修正曼哈顿距离d作为其连线的长度； 其中h为一个分段线性函数，h(z)=max{z,-z, g},
g是正常数 4.如果用模块间的曼哈顿距离l1（直折线距离）作为其连线的长度，但不是最小化总长度，而是最小化最长连线的长度。 g取为0.02。在Adata1.txt中给出了实例1：50个模块，150条连线的数据，Adata2.txt中给出了实例2：100个模块，300条连线的数据，两个实例中任选一个给出上述四个模型的解，并进行比较。要求 · 前面均未考虑模块的大小，实际上，我们必须考虑模块间的重叠，假设当模块间的距离小于0.01时，就认为两模块重叠。对四个模型得到的解分别计算其有多少对模块重叠以及占总对数n(n-1)/2的百分比。 | 
发表于 2007-5-31 23:18:31
楼主