求助.急!谢谢了...
将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条连线的数据，两个实例中任选一个给出上述四个模型的解，并进行比较。要求
· 分别画出每个解中n个模块的位置的直方图。
· 分别画出连线长度 的直方图。
· 计算四个模型得到的解的总长度和最长连线的长度
· 前面均未考虑模块的大小，实际上，我们必须考虑模块间的重叠，假设当模块间的距离小于0.01时，就认为两模块重叠。对四个模型得到的解分别计算其有多少对模块重叠以及占总对数n(n-1)/2的百分比。
进一步，考虑使连线的总长度和模块的重叠数尽可能小的问题。 |
发表于 2007-5-31 09:57:15
楼主