2024年第五届“华数杯”全国大学生数学建模竞赛B赛题解析

本次华数杯B题第一问是根据附件1提供的信息，设计一个与电路单元连线接口坐标相关的线长评估模型，使估计线长尽可能与对应的RSMT线长相近，并可应用于评估附件1中的总连接线长。

假设附件1中的每条连线接口都有两个端点，电路单元的长和宽分别为和W

这样计算出来的线长与RSMT线长差值就比较小，也比较容易计算。

第二个问题：根据问题1构建的线长评估模型，结合附件1和附件2提供的信息，建立数学模型，目标为最小化总连接线长，并满足单元密度约束。请仅仅回答第二个问题，并提供详细LaTeX数学公式：

根据题目的要求，应该在设计的时候同时满足两个目标，即最小化总连接线长和满足单元密度约束。因此，我们可以通过加入一个惩罚项来实现对单元密度的约束。根据题目中给出的信息，我们可以知道，单元密度的计算公式为：

import numpy as np
import matplotlib.pyplot as plt

# 导入数据

data1 = np.loadtxt("附件1.txt", dtype=str, delimiter=",", skiprows=1)
data2 = np.loadtxt("附件2.txt", dtype=int, delimiter=",", skiprows=1)

# 将数据转换为字典形式

dic1 = {}
dic2 = {}
for i in range(len(data1)):
    dic1[data1[i, 0]] = [int(data1[i, 2]), int(data1[i, 3])]
for i in range(len(data2)):
    dic2[data2[i, 0]] = [data2[i, 1], data2[i, 2], data2[i, 3], data2[i, 4], data2[i, 5], data2[i, 6]]

# 计算连线长度

def cal_length(dic2):
    length = 0
    for key in dic2:
        for i in range(1, 5):
            if dic2[key][i] == 1:
                length += abs(dic1[key][0]-dic1[key][2*i-1])+abs(dic1[key][1]-dic1[key][2*i])
    return length

# 计算单元密度

def cal_density(dic1, dic2, size, grid, threshold):
    num = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
    return num/(size[0]*size[1])

# 计算网格布线密度

def cal_max_density(dic1, dic2, size, grid):
    max_density = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            num = 0
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
            if num > max_density:
                max_density = num
    return max_density/(grid**2)

# 修正模型

def revised_model(dic1, dic2, size, grid, threshold):
    # 初始化温度和迭代次数
    T = 100
    max_iter = 100
    # 随机生成初始布局
    for key in dic1:
        dic1[key][0] = np.random.randint(grid, size[0]-grid)
        dic1[key][1] = np.random.randint(grid, size[1]-grid)
    # 计算初始布局下的总连线长度
    old_length = cal_length(dic2)
    # 开始迭代
    for k in range(max_iter):
        # 随机选择一个电路单元
        key = np.random.choice(list(dic1.keys()))
        # 随机选择一个方向
        direction = np.random.choice([-1, 1, -grid, grid])
        # 计算新布局下的总连线长度
        dic1[key][0] += direction
        new_length = cal_length(dic2)
        # 计算温度
        T = 0.99*T
        # 判断是否接受新布局
        if np.exp((old_length-new_length)/T) > np.random.rand():
            old_length = new_length
        else:
            dic1[key][0] -= direction
    # 计算最终布局下的总连线长度
    new_length = cal_length(dic2)
    return dic1, new_length

# 计算平均布线密度

def cal_avg_density(dic1, dic2, size, grid):
    num = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
    return num/len(dic1)

# 计算改进后布线密度模型

def improved_model(dic1, dic2, size, grid, threshold):
    # 初始化温度和迭代次数
    T = 100
    max_iter = 100
    # 随机生成初始布局
    for key in dic1:
        dic1[key][0] = np.random.randint(grid, size[0]-grid)
        dic1[key][1] = np.random.randint(grid, size[1]-grid)
    # 计算初始布局下的总连线长度和最大网格布线密度
    old_length = cal_length(dic2)
    old_max_density = cal_max_density(dic1, dic2, size, grid)
    # 开始迭代
    for k in range(max_iter):
        # 随机选择一个电路单元
        key = np.random.choice(list(dic1.keys()))
        # 随机选择一个方向
        direction = np.random.choice([-1, 1, -grid, grid])
        # 计算新布局下的总连线长度和最大网格布线密度
        dic1[key][0] += direction
        new_length = cal_length(dic2)
        new_max_density = cal_max_density(dic1, dic2, size, grid)
        # 计算温度
        T = 0.99*T
        # 判断是否接受新布局
        if np.exp((old_length-new_length)/T) > np.random.rand() and new_max_density < old_max_density:
            old_length = new_length
            old_max_density = new_max_density
        else:
            dic1[key][0] -= direction
    # 计算最终布局下的总连线长度和平均网格布线密度
    new_length = cal_length(dic2)
    new_avg_density = cal_avg_density(dic1, dic2, size, grid)
    return dic1, new_length, new_avg_density

# 保存修正后的尺寸和网格划分粒度

new_size = [500, 500]
new_grid = 50

# 修正后的布局

new_dic1, new_length, new_avg_density = improved_model(dic1, dic2, new_size, new_grid, threshold=0.7)

# 输出最终布局结果

print("修正后的总连接线长：", new_length)
print("修正后的平均布线密度：", new_avg_density)

# 可视化布局结果

plt.figure(figsize=(10, 10))
for key in new_dic1:
    plt.scatter(new_dic1[key][0], new_dic1[key][1], c="r")
    plt.annotate(key, (new_dic1[key][0], new_dic1[key][1]))
plt.xticks(np.arange(0, new_size[0], new_grid))
plt.yticks(np.arange(0, new_size[1], new_grid))
plt.grid(linestyle="--")
plt.show()

# 计算并可视化网格布线密度

density_map = np.zeros((new_size[0]//new_grid, new_size[1]//new_grid))
for i in range(0, new_size[0], new_grid):
    for j in range(0, new_size[1], new_grid):
        for key in new_dic1:
            if new_dic1[key][0] >= i and new_dic1[key][0] < i+new_grid and new_dic1[key][1] >= j and new_dic1[key][1] < j+new_grid:
                density_map[i//new_grid, j//new_grid

第三个问题：除了连接线长和单元密度，布线密度也是衡量布局质量的重要指标之一。分析图 4 所示的网格布线密度计算模型， 找出其存在的问题。针对发现的问题，提出改进方案。应用改进后的布线密度模型，计算问题2中更新后的全局布局结果的布线密度，并对结果（网格布线密度）进行可视化。

问题重述：根据提供的附件1和附件2，电路单元的自动布局问题可以分为全局布局和详细布局两个步骤。其中，全局布局旨在最小化总连接线长，并保证单元密度不超过设定阈值。在此前提下，本文提出了一个与连线接口坐标相关的线长评估模型，以及一个与电路单元坐标相关的网格密度评估模型。最后，根据改进后的模型，计算并可视化了全局布局的结果。

数学建模：根据提供的附件1和附件2，根据数据特征，本文建立的数学模型如下：

1. 线长评估模型

 

针对上述问题，可以提出如下改进方案：

(1) 考虑每个网格内单元的位置和连线接口位置，设计一种更加精确的布线密度计算方法。可以根据电路单元的重叠面积和连线接口的距离，来确定每个网格的布线密度，从而更加准确地反映出布局的实际情况。

(2) 为单元面积和连线接口数量设置不同的权重，使连线接口数量对布线密度的影响更大。可以根据实际情况，通过数据分析或者实验来确定不同权重的取值，从而更加准确地计算出布线密度。

改进后的布线密度计算模型如下所示：

1）首先根据给定的网格划分粒度，建立一个网格矩阵，将布局区域划分为若干个网格。

2）对于每个网格，计算出网格内的单元面积总和，并将其除以网格的面积，得到单元面积占比。

3）对于每个网格，计算出网格内的连线接口数量，并将其除以网格的面积，得到连线接口数量占比。

4）根据单元面积占比和连线接口数量占比，计算出网格的布线密度，可以根据具体情况，设置不同的权重。

5）对所有网格的布线密度进行求和，得到布线密度值。

对应的python代码如下所示：

# 定义计算布线密度的函数，输入参数为网格矩阵、网格划分粒度、每个网格内的单元面积总和和连线接口数量
def calc_density(grid_matrix, grid_size, cell_area, interface_num):
    # 初始化布线密度值
    density = 0
    # 遍历网格矩阵中的每个网格
    for row in range(grid_matrix.shape[0]):
        for col in range(grid_matrix.shape[1]):
            # 计算网格的面积
            grid_area = grid_size ** 2
            # 计算单元面积占比
            cell_density = cell_area[row, col] / grid_area
            # 计算连线接口数量占比
            interface_density = interface_num[row, col] / grid_area
            # 根据单元面积占比和连线接口数量占比，计算出网格的布线密度
            density += cell_density + interface_density
    # 返回布线密度值
    return density

这样改进后的布线密度计算模型，可以更加准确地反映出布局的实际情况，从而更加有效地评估布局的质量。

第四个问题：在问题三的基础上，修正问题二中建立的数学模型，使得网格布线密度的最大值越小越好。根据附件一和附件二提供的信息，应用修正后的模型完成全局布局，输出总连接线长（HPWL），并可视化结果（电路单元的位置和网格布线密度）。

第四个问题：在问题三的基础上，修正问题二中建立的数学模型，使得网格布线密度的最大值越小越好。根据附件一和附件二提供的信息，应用修正后的模型完成全局布局，输出总连接线长（HPWL），并可视化结果（电路单元的位置和网格布线密度）。题目需要建立一个数学模型，使网格布线密度的最大值越小越好。该模型应满足：（1）最小化总连接线长；（2）满足单元密度约束；（3）使网格布线密度的最大值越小越好。根据附件1和附件2提供的信息，应用此模型完成全局布局，输出总连接线长（HPWL），并可视化结果（电路单元的位置和网格布线密度）。

如图 5 所示，为这些电路单元提供了一个示例布局，其中矩形代表电路单元，数字代表网格布线密度。这些电路单元的设计要求如下：

（1）所有电路单元中，A和D相连，B和E相连，C和F相连；

（2）布局区域尺寸为20×20，网格划分粒度为2×2，密度阈值为0.5

（3）电路单元大小（长×宽）分别为2×3、1×3、1×2、2×2、3×1、3×2；

（4）每个电路单元均有四个连线接口，分别位于矩形的左上、左下、右上和右下角处，连线接口宽度均为0.2，如图 6 所示。

图 5：示例布局示意图。（图片内容：展示了一种可能的解决方案，其中矩形代表电路单元，数字代表网格布线密度。）

图 6：示例电路单元连线接口示意图。（图片内容：展示了如何定义电路单元的连线接口。）

思考过程：

1、问题一：线长的评估模型

根据题目的描述，考虑到HPWL和RSMT线长的优点，综合考虑的线长评估模型如下：

给定电路单元的坐标，计算两两电路单元的连线接口，并确定连线接口之间的连接关系。对于连线接口相连的两个电路单元，计算两者的连线接口矩形的外接矩形的周长，将所有这样的周长相加，得到总的HPWL线长。再对每一组有连接关系的电路单元计算RSMT线长，并将所有的RSMT线长进行汇总。综合考虑这两者的结果，得到线长评估模型。

2、问题二：总连接线长的最小化

在问题一的基础上，综合考虑总连接线长和单元密度约束，建立数学模型。假设所有的网格均是正方形，假设有N个电路单元。考虑到单元密度约束，可以将布局的区域内部划分为M个网格，其中M比N要大很多。

由于需要最小化总连接线长，因此可以建立目标函数：

min HPWL + α·RSMT

其中，HPWL和RSMT分别为两种线长的估计结果。α为一个系数，用于平衡这两项。

为了满足单元密度约束，可以建立约束条件：

∑ N 1 M ≤ d

其中，N1为布局区域内每个网格内的电路单元数目，d为单元密度的阈值。

3、问题三：布线密度

问题三的要求在问题二的基础上，增加了一个评价指标。按照题目的要求，需要先建立计算网格布线密度的方法。假设网格为正方形，可以建立如下的评价指标：

max N 1 M × 1 S × 1 S

其中，S为网格的划分粒度。

4、问题四：布线密度的最大值越小越好

为了让布线密度的最大值越小越好，可以调整目标函数，让目标函数中考虑到与网格划分粒度相关的一个指标，即：

min HPWL + α·RSMT + β·N 1 M × 1 S × 1 S

其中，β为一个系数，用于平衡这三项。为了让网格布线密度的最大值越小越好，可以令β的值更大一些。

在数学模型设计中，我们将每个网格的布线密度设为
 

 

\end{document}

import numpy as np
import matplotlib.pyplot as plt

# 导入数据

data1 = np.loadtxt("附件1.txt", dtype=str, delimiter=",", skiprows=1)
data2 = np.loadtxt("附件2.txt", dtype=int, delimiter=",", skiprows=1)

# 将数据转换为字典形式

dic1 = {}
dic2 = {}
for i in range(len(data1)):
    dic1[data1[i, 0]] = [int(data1[i, 2]), int(data1[i, 3])]
for i in range(len(data2)):
    dic2[data2[i, 0]] = [data2[i, 1], data2[i, 2], data2[i, 3], data2[i, 4], data2[i, 5], data2[i, 6]]

# 计算连线长度

def cal_length(dic2):
    length = 0
    for key in dic2:
        for i in range(1, 5):
            if dic2[key][i] == 1:
                length += abs(dic1[key][0]-dic1[key][2*i-1])+abs(dic1[key][1]-dic1[key][2*i])
    return length

# 计算单元密度

def cal_density(dic1, dic2, size, grid, threshold):
    num = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
    return num/(size[0]*size[1])

# 计算网格布线密度

def cal_max_density(dic1, dic2, size, grid):
    max_density = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            num = 0
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
            if num > max_density:
                max_density = num
    return max_density/(grid**2)

# 修正模型

def revised_model(dic1, dic2, size, grid, threshold):
    # 初始化温度和迭代次数
    T = 100
    max_iter = 100
    # 随机生成初始布局
    for key in dic1:
        dic1[key][0] = np.random.randint(grid, size[0]-grid)
        dic1[key][1] = np.random.randint(grid, size[1]-grid)
    # 计算初始布局下的总连线长度
    old_length = cal_length(dic2)
    # 开始迭代
    for k in range(max_iter):
        # 随机选择一个电路单元
        key = np.random.choice(list(dic1.keys()))
        # 随机选择一个方向
        direction = np.random.choice([-1, 1, -grid, grid])
        # 计算新布局下的总连线长度
        dic1[key][0] += direction
        new_length = cal_length(dic2)
        # 计算温度
        T = 0.99*T
        # 判断是否接受新布局
        if np.exp((old_length-new_length)/T) > np.random.rand():
            old_length = new_length
        else:
            dic1[key][0] -= direction
    # 计算最终布局下的总连线长度
    new_length = cal_length(dic2)
    return dic1, new_length

# 计算平均布线密度

def cal_avg_density(dic1, dic2, size, grid):
    num = 0
    for i in range(0, size[0], grid):
        for j in range(0, size[1], grid):
            for key in dic1:
                if dic1[key][0] >= i and dic1[key][0] < i+grid and dic1[key][1] >= j and dic1[key][1] < j+grid:
                    num += dic2[key][4]*dic2[key][5]
    return num/len(dic1)

# 计算改进后布线密度模型

def improved_model(dic1, dic2, size, grid, threshold):
    # 初始化温度和迭代次数
    T = 100
    max_iter = 100
    # 随机生成初始布局
    for key in dic1:
        dic1[key][0] = np.random.randint(grid, size[0]-grid)
        dic1[key][1] = np.random.randint(grid, size[1]-grid)
    # 计算初始布局下的总连线长度和最大网格布线密度
    old_length = cal_length(dic2)
    old_max_density = cal_max_density(dic1, dic2, size, grid)
    # 开始迭代
    for k in range(max_iter):
        # 随机选择一个电路单元
        key = np.random.choice(list(dic1.keys()))
        # 随机选择一个方向
        direction = np.random.choice([-1, 1, -grid, grid])
        # 计算新布局下的总连线长度和最大网格布线密度
        dic1[key][0] += direction
        new_length = cal_length(dic2)
        new_max_density = cal_max_density(dic1, dic2, size, grid)
        # 计算温度
        T = 0.99*T
        # 判断是否接受新布局
        if np.exp((old_length-new_length)/T) > np.random.rand() and new_max_density < old_max_density:
            old_length = new_length
            old_max_density = new_max_density
        else:
            dic1[key][0] -= direction
    # 计算最终布局下的总连线长度和平均网格布线密度
    new_length = cal_length(dic2)
    new_avg_density = cal_avg_density(dic1, dic2, size, grid)
    return dic1, new_length, new_avg_density

# 保存修正后的尺寸和网格划分粒度

new_size = [500, 500]
new_grid = 50

# 修正后的布局

new_dic1, new_length, new_avg_density = improved_model(dic1, dic2, new_size, new_grid, threshold=0.7)

# 输出最终布局结果

print("修正后的总连接线长：", new_length)
print("修正后的平均布线密度：", new_avg_density)

# 可视化布局结果

plt.figure(figsize=(10, 10))
for key in new_dic1:
    plt.scatter(new_dic1[key][0], new_dic1[key][1], c="r")
    plt.annotate(key, (new_dic1[key][0], new_dic1[key][1]))
plt.xticks(np.arange(0, new_size[0], new_grid))
plt.yticks(np.arange(0, new_size[1], new_grid))
plt.grid(linestyle="--")
plt.show()

# 计算并可视化网格布线密度

density_map = np.zeros((new_size[0]//new_grid, new_size[1]//new_grid))
for i in range(0, new_size[0], new_grid):
    for j in range(0, new_size[1], new_grid):
        for key in new_dic1:
            if new_dic1[key][0] >= i and new_dic1[key][0] < i+new_grid and new_dic1[key][1] >= j and new_dic1[key][1] < j+new_grid:
                density_map[i//new_grid, j//new_grid

 获取更加完整的思路详细见下方名片。